Python-сообщество

Вновь о питоновском аналоге массива

Из темы http://python.su/forum/viewtopic.php?id=1792 я вынес точку зрения, что аналогом массива считается список (list).

Но просветите, пожалуйста, кто-нибудь, как организован этот самый list внутри?
Как связный список с последовательным доступом, или как красно-чёрное дерево, или на самом деле список именно как массив и организован, и т.д.?

Какова ассимпотическая оценка операции “квадратные скобки”? Например, чтобы фрагмент кода с при i==17127 нашёл этот самый элемент №17127, будут просматриваться все предыдущие 17126, или без каких-либо просмотров будет выбран сразу нужный, или просмотр будет, но речь идёт не о десятках тысяч узлов, а о просто десятках?

Какова ассимптотическая оценка операции del a, т.е “удалить несколько элементов из НАЧАЛА списка”? То есть, будут просто переброшены несколько указателей, или весь хвост списка будет реально перемещаться из одного участка памяти в другой, или произойдёт максимум несколько поворотов дерева?
Особо интересует ситуация, когда действие del a придётся выполнять многократно, для изначально очень большого списка и относительно мАлых i.

Я новичок в python, но ВОВСЕ НЕ новичок в программировании вообще (особенно алгоритмике). Прошу отвечать, исходя из этого – не грузить сложными узко-питоновскими заморочками, но и не тратить время на элементарные вещи, общие для всех языков программирования.

IlyaCk
Я новичок в python, но ВОВСЕ НЕ новичок в программировании вообще (особенно алгоритмике)

Эх, почему у нас нету раздела “Юмор”… :-)

Ах да, про какой питон идет речь?

IlyaCk, из вашего поста на 99% уверен, что Python вам не подойдет, используйте C/C++, pascal, delphi, или, если интересует что-то новое, то язык D, или Go.

P.S.
Насчет Python, то тут оценка алгоритмической сложности осложнена тем, что ВСЕ в питоне, будь-то число, метод, строка, список является объектами классов, поэтому говорить об операции 1+1 в C и об этой же операции в Python - говорить о совершенно разных вещах

Отредактировано (Дек. 27, 2009 20:43:55)

Ребята, ну что вы, право слово. Алгоритмическая сложность не зависит от языка программирования. И кардинально list не менялся от двойки к тройке - хотя предложение было.

Наглядней всего начать с http://www.python.org/dev/peps/pep-3128/
Там есть сравнительная табличка стандартного питоновского списка и B-tree based (доступен как сторонняя библиотека blist).
Принятое решение оптимизированно для относительно небольших списков и наиболее часто встречающихся операций. То же самое можно сказать о dict (отдельно учитывайте, что dict используется для хранения namespace модуля, класса, инстанции и т.д.)

Отредактировано (Дек. 27, 2009 22:09:58)

У каждого свой опыт, свои знания. Отсюда и терминология. Если говорить в терминологии C++, то по учебникам и по ссылке я понял так: list - динамический массив, содержащий указатели некоторого базового абстрактного класса. Эти указатели могут ссылаться на объект любого типа.

То есть что-то типа stl::vector из C++, содержащий описанные выше указатели.

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

Kogrom
Вы поняли правильно питоновский список “в душе” - массив.
Добавление стоит O(1) именно из-за того, что память выделяется “с запасом”.
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
*/
Кстати, примерно то же самое происходит с std::vector. .capacity() >= .size()

почему вы не читаете документы… ? смотри тут в параметрах СПИСКИ

>>> a = ['qqqq','wwww', 123]
>>> i = 1
>>> a[i:i+1] = []
>>> a
['qqqq', 123]

Отредактировано (Дек. 29, 2009 10:52:53)

так же совет regall вполне актуален

Уважаемый sypper-pit.
Признаюсь, не уловил связи между примером с приложенным линком - и темой разговора.
Равно как и совет regall в моих глазах наглядно демонстрирует прискорбное смешивание двух не эквивалентных понятий: производительность и алгоритмическая сложность.