Структуры данных составляют основу большинства программ, хотя программисты на языке Python могут зачастую совсем не беспокоиться об этом. Их спокойствие оправданно, потому что Python предоставляет богатый набор встроенных и оптимизированных типов, облегчающих работу со структурированными данными: списки, строки, кортежи, словари, множества и другие. В простых системах этих типов обычно достаточно. Словари, например, делают многие классические алгоритмы поиска ненужными в Python, а списки избавляют от большой части работы, необходимой для поддержки коллекций в языках более низкого уровня. Теми и другими настолько просто пользоваться, что обычно не приходится задумываться над ними.
Но в более сложных приложениях может потребоваться вводить собственные, более сложные типы, чтобы справиться с дополнительными требованиями или особыми ситуациями. В этой главе мы рассмотрим несколько реализаций более сложных структур данных: множеств, стеков, графов и других. Как будет показано, структуры данных принимают в Python вид новых типов объектов, интегрированных в модель типов языка. То есть объекты, которые создаются на языке Python, становятся законченными типами данных — для использующих их сценариев они выглядят точно так же, как списки, числа и словари.
Хотя примеры в этой главе иллюстрируют более сложную технику программирования, в них также подчеркнута поддержка в Python создания по втор но ис поль зуе мо го программного обеспечения. Реализации объектов, написанные с помощью классов и модулей, естественным образом становятся полезными компонентами и могут быть использованы в любой импортирующей их программе. В сущности, мы будем создавать библио те ки инструментов для работы со структурами данных, даже не планируя этого делать.
Кроме того, большинство примеров в этой главе представляют собой чистый программный код на языке Python (и, по крайней мере, для тех, кто читал все по порядку, некоторые из них могут показаться относительно простыми в сравнении с примерами из предыдущих глав), однако они также представляют собой основу для обсуждения проблем производительности и могут служить подсказками к главе 20. С самой общей точки зрения новые объекты Python могут быть реализованы на Python или интегрированном языке, таком как C. При определении типов в языке C используются шаблоны, похожие на используемые здесь.
Наконец, мы также увидим, что зачастую вместо частных решений в этой области могут использоваться встроенные возможности Python. Хотя реализация собственных структур данных иногда бывает просто необходима и они могут обеспечивать определенные удобства с точки зрения сопровождения программного кода и его развития, тем не менее в языке Python они могут не играть такой доминирующей роли, как в языках, менее дружественных по отношению к программистам.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
