Структуры данных в Python

Ответ 1

Python предоставляет вам мощные высоко оптимизированные структуры данных, как встроенные, так и как часть нескольких модулей стандартной библиотеки (listи dict s, конечно, но также и tuple s, set s, array в модуле array и некоторые другие контейнеры в модуле collections).

Комбинации этих структур данных (и, возможно, некоторые из функций из вспомогательных модулей, таких как heapq и bisect), как правило, достаточны для реализации наиболее богатых структур, которые могут потребоваться в реальном программировании; однако, это не всегда случай.

Когда вам нужно что-то большее, чем богатая библиотека, обратите внимание на то, что атрибуты объекта (и элементы в коллекциях) по существу являются "указателями" на другие объекты (без арифметики указателей), т.е. "сменные ссылки", в Python как в Java. В Python вы обычно используете значение None в атрибуте или элементе для представления того, что означает NULL в С++ или NULL, в Java.

Итак, например, вы можете реализовать двоичные деревья через, например:

class Node(object):

  __slots__ = 'payload', 'left', 'right'

  def __init__(self, payload=None, left=None, right=None):
    self.payload = payload
    self.left = left
    self.right = right

плюс методы или функции для обхода и аналогичных операций (атрибут __slots__ class является необязательным - в основном оптимизация памяти, чтобы избежать того, чтобы каждый экземпляр Node имел свой собственный __dict__), который был бы значительно больше трех необходимые атрибуты/ссылки).

Другие примеры структур данных, которые лучше всего могут быть представлены выделенными классами Python, а не прямым составом других существующих структур Python, включают tries (см., например, здесь) и graphs (см., например, здесь).

Ответ 2

Для некоторых простых структур данных (например, для стека) вы можете просто использовать встроенный список, чтобы выполнить свою работу. С более сложными структурами (например, цветным фильтром) вам придется реализовать их самостоятельно, используя примитивы, поддерживаемые языком.

Вы должны использовать встроенные функции, если они действительно служат вашей цели, поскольку они долгое время отлаживаются и оптимизируются ордой людей. Выполнение этого с нуля самостоятельно, вероятно, приведет к ухудшению структуры данных.

Если, однако, вам нужно что-то недоступное в качестве примитива или если примитив не работает достаточно хорошо, вам придется реализовать свой собственный тип.

Детали, такие как управление указателями и т.д., являются просто разговорами по внедрению и не ограничивают возможности самого языка.

Ответ 3

Книги структуры данных C/С++ только пытаются научить вас основополагающим принципам, лежащим в основе различных структур - они, как правило, не советуют вам фактически выходить и повторно изобретать колесо, создавая собственную библиотеку стеков и списков.

Независимо от того, используете ли вы Python, С++, С#, Java, вы всегда должны сначала искать встроенные структуры данных. Они, как правило, будут реализованы с использованием тех же системных примитивов, которые вам придется использовать, делая это самостоятельно, но с тем преимуществом, что были опробованы и протестированы.

Только когда предоставленные структуры данных не позволят вам выполнить то, что вам нужно, и нет альтернативной и надежной библиотеки, доступной вам, вы должны смотреть на создание чего-то с нуля (или расширение того, что предусмотрено).

Ответ 4

Как Python обрабатывает объекты на низком уровне, все равно не слишком странно. Этот документ должен слегка устранить его; это в основном вся логика указателя, с которой вы уже знакомы.

Ответ 5

С Python у вас есть доступ к обширному набору библиотечных модулей, написанных и отлаженных другими людьми. Коэффициенты очень хорошие, что где-то там есть модуль, который делает хотя бы часть того, что вы хотите, и шансы даже хороши, что он может быть реализован в C для производительности.

Например, если вам нужно выполнить математическую математику, вы можете использовать NumPy, который был написан на C и Fortran.

Python достаточно медленный, чтобы вы не были счастливы, если попытаетесь написать какой-то действительно вычислительно-интенсивный код (например, быстрое преобразование Фурье) в родном Python. С другой стороны, вы можете получить C-кодированное преобразование Фурье как часть SciPy и просто использовать его.

У меня никогда не было ситуации, когда я хотел решить проблему на Python и сказал "черт, я просто не могу выразить структуру данных, в которой я нуждаюсь".

Если вы пионер, и вы делаете что-то в Python, для которого там нет никакого библиотечного модуля, вы можете попробовать написать его в чистом Python. Если это достаточно быстро, все готово. Если он слишком медленный, вы можете его профилировать, выяснить, где находятся медленные части, и переписать их на C с помощью API Python C. Мне никогда не нужно было это делать.

Ответ 6

Невозможно реализовать что-то вроде С++-вектора в Python, так как у вас нет примитивов массивов, как это делает C/С++. Тем не менее, что-то более сложное может быть реализовано (эффективно) поверх него, включая, но не ограничиваясь: связанные списки, хеш-таблицы, мультимножества, фильтры цветения и т.д.