Структуры данных в Python
Все книги, которые я прочитал на структурах данных до сих пор, кажется, используют C/C++ и делают интенсивное использование из "ручного" управления указателем, которое они предлагают. Так как Python скрывает такое управление памятью, и сборка "мусора" от пользователя - это даже возможный реализовать эффективные структуры данных на этом языке и является там какой-либо причиной сделать так вместо того, чтобы использовать созданный-ins?
6 ответов
Python предоставляет вам несколько мощных, высоко оптимизированных структур данных, как встроенных, так и в составе нескольких модулей в стандартной библиотеке ( list s и dict s, конечно, но также tuple s, set s, array s в модуле array и некоторые другие контейнеры в модуле коллекции ).
Комбинации этих структур данных (и, возможно, некоторых функций из вспомогательных модулей, таких как heapq и bisect ), как правило, достаточно для реализации наиболее богатых структур, которые могут потребоваться в реальной жизни. -жизненное программирование; однако это не всегда так.
Если вам нужно что-то большее, чем предоставляет богатая библиотека, примите во внимание тот факт, что атрибуты объекта (и элементы в коллекциях) по сути являются «указателями» на другие объекты (без арифметики указателей), то есть «повторно устанавливаемыми ссылками» в Python прямо как в Java. В Python вы обычно используете значение None в атрибуте или элементе, чтобы представить, что NULL будет означать в C ++ или 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 __ не является обязательным - в основном это оптимизация памяти, чтобы избегайте каждого экземпляра узла , несущего свой собственный __ dict __ , который будет значительно больше, чем три необходимых атрибута / ссылки).
Другие примеры структур данных, которые могут быть лучше всего представлены выделенными классами Python, а не прямым составом других существующих структур Python, включают попытки (см., Например, здесь ) и графов (см., Например, здесь ).
Для некоторых простых структур данных (например, стека), вы можете просто использовать список встроенных данных, чтобы выполнить свою работу. С более сложными структурами (например, фильтр цветения), Вам придется реализовать их самостоятельно, используя примитивы, поддерживаемые языком.
Вы должны использовать сборки, если они действительно служат вашей цели, так как они отлаживаются и оптимизируются ордой людей в течение долгого времени. Сделав это с нуля самостоятельно, Вы, вероятно, получите более низкую структуру данных.
Если, однако, вам нужно что-то, что недоступно в качестве примитива, или если примитив работает недостаточно хорошо, вам придётся реализовать свой собственный тип.
Такие детали, как управление указателями и т.д., являются лишь разговорами о реализации и на самом деле не ограничивают возможности самого языка.
Книги структур данных на C/C++ только пытаются научить вас основным принципам, лежащим в основе различных структур - они обычно не советуют вам на самом деле выходить и заново изобретать колесо, создавая свою собственную библиотеку стеков и списков.
Независимо от того, используете ли вы Python, C++, C#, Java, что бы то ни было, вы всегда должны сначала посмотреть на встроенные структуры данных. Обычно они будут реализованы с использованием тех же системных примитивов, которые вы должны будете использовать, делая это самостоятельно, но с тем преимуществом, что они были опробованы и проверены.
Только когда предоставленные структуры данных не позволяют вам выполнить то, что вам нужно, и нет альтернативной и надежной библиотеки, если вы смотрите на сборку чего-то с нуля (или расширение того, что предоставлено).
.То, как Python обращается с объектами на низком уровне, все равно не слишком странно. Этот документ должен немного расшифровать его; это практически вся логика указателей, с которой вы уже знакомы.
Невозможно реализовать что-то вроде вектора Си++ на Python, так как у вас нет примитивов массива, как у Си/Си++. Тем не менее, все более сложное может быть реализовано (эффективно) поверх него, включая, но не ограничиваясь: связанные списки, хэш-таблицы, мультисеты, фильтры цветения и т.д.
.С Python вы имеете доступ к огромному ассортименту библиотечных модулей, написанных и отлаженных другими людьми. Очень хорошо, что где-то там есть модуль, который хотя бы частично выполняет то, что вы хотите, и даже хорошо, что он может быть реализован на C для производительности.
Например, если вам нужно сделать матричную математику, вы можете использовать NumPy, который был написан на C и Fortran.
Python достаточно медленный, и вы не будете счастливы, если попробуете написать какой-нибудь действительно вычислительный код (например, быстрое преобразование Фурье) на родном Python. С другой стороны, вы можете получить закодированное на C преобразование Фурье в рамках SciPy и просто использовать его.
У меня никогда не было ситуации, когда я хотел бы решить проблему на Python и сказал: "Чёрт, я просто не могу выразить нужную мне структуру данных"
Если вы пионер, и вы делаете что-то на Python, для чего просто нет модуля библиотеки, тогда вы можете попробовать написать это на чистом Python. Если это достаточно быстро, то вам конец. Если он слишком медленный, вы можете профилировать его, выяснить, где находятся медленные части, и переписать их на C, используя Python C API. Мне никогда не приходилось этого делать.