Найти - Пользователи
Полная версия: list -- аналог массивов ??? А какая там ассимптотика?
Начало » Python для новичков » list -- аналог массивов ??? А какая там ассимптотика?
1 2
IlyaCk
Вновь о питоновском аналоге массива

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

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

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

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

Я новичок в python, но ВОВСЕ НЕ новичок в программировании вообще (особенно алгоритмике). Прошу отвечать, исходя из этого – не грузить сложными узко-питоновскими заморочками, но и не тратить время на элементарные вещи, общие для всех языков программирования.
regall
IlyaCk
Я новичок в python, но ВОВСЕ НЕ новичок в программировании вообще (особенно алгоритмике)
Качаем исходники Python на C/C++ -> смотрим -> узнаем
Александр Кошелев
Эх, почему у нас нету раздела “Юмор”… :-)

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

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

Наглядней всего начать с http://www.python.org/dev/peps/pep-3128/
Там есть сравнительная табличка стандартного питоновского списка и B-tree based (доступен как сторонняя библиотека blist).
Принятое решение оптимизированно для относительно небольших списков и наиболее часто встречающихся операций. То же самое можно сказать о dict (отдельно учитывайте, что dict используется для хранения namespace модуля, класса, инстанции и т.д.)
Kogrom
У каждого свой опыт, свои знания. Отсюда и терминология. Если говорить в терминологии 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()
sypper-pit
почему вы не читаете документы… ? смотри тут в параметрах СПИСКИ

>>> a = ['qqqq','wwww', 123]
>>> i = 1
>>> a[i:i+1] = []
>>> a
['qqqq', 123]
sypper-pit
так же совет regall вполне актуален
Андрей Светлов
Уважаемый sypper-pit.
Признаюсь, не уловил связи между примером с приложенным линком - и темой разговора.
Равно как и совет regall в моих глазах наглядно демонстрирует прискорбное смешивание двух не эквивалентных понятий: производительность и алгоритмическая сложность.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB