DjangoBB LoFi version

Полная версия: Почему скорость доступа к элементам list выше чем к tuple ?

Начало » Python для экспертов » Почему скорость доступа к элементам list выше чем к tuple ?

1 2

Isem

Июль 25, 2011 09:44:04

o7412369815963
У меня результаты прежние, лист всех обгоняет

А попробуй тогда поменять местами tuple и list в инициализации ‘a’ (с сохранением тех же чисел 100000 и 10):

a = (tuple(range(COUNT)), list(range(COUNT)), 
     array.array('l', list(range(COUNT))),
      numpy.zeros(COUNT))

После такой перестановки у меня чудным образом характеристики tuple и list меняются местами.

Isem

Июль 25, 2011 10:02:02

Ну а если инициализацию сделать прозрачной, то как и получалось у меня, array обгоняет всех, а tuple и list становятся одинаковыми.

data_list = list(range(COUNT))
random.shuffle( data_list )

a = (tuple(data_list), list(data_list), 
     array.array('l', list(data_list)),
      numpy.zeros(COUNT))

o7412369815963

Июль 25, 2011 11:08:15

> А попробуй тогда поменять местами tuple и list в инициализации ‘a’ (с сохранением тех же чисел 100000 и 10):
Да, какая-то мистика, результат не должен меняться т.к. тесты выбираются случайно:

col = random.choice(a)

В моем тесте (1 пост) результат не меняется от перестановки.

Вообщем к чему была поднята тема - одной из самых важных особенностей разных типов данных является скорость обработки, как известно скорость доступа к элементам равна:
массив = O(1)
лист = O(n) #(лист в обычной реализации)

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

kachayev

Июль 25, 2011 11:24:40

o7412369815963
Вообщем к чему была поднята тема - одной из самых важных особенностей разных типов данных является скорость обработки, как известно скорость доступа к элементам равна:
массив = O(1)
лист = O(n) #(лист в обычной реализации)

На самом деле, это не совсем скорость. Это алгоритмическая сложность. И она указывает нам на то, что скорость указанных операций с массивом не будет зависит от его размера, а для list - будет увеличиватся пропорционального количеству элементов в нем. Поэтому преимущество в скорости может проявится на очень больших набор данных.

Isem

Июль 25, 2011 11:29:43

o7412369815963
В моем тесте (1 пост) результат не меняется от перестановки.

Так и надо писать тесты.

o7412369815963
оказалось в питоне заменив лист на массив мы не выиграем времени - 1 важный фактор массивов (tuple, array) отсутствует.

В питоне list - это и есть массив, это не список в классическом понимании этого слова.

o7412369815963
в итоге у array остается только 1? отличительная особенность - оптимальный расход памяти.

Это верно, ведь array хранит сами значения фиксированной длины последовательно в памяти, а list - указатели (так же последовательно в памяти) на объекты (речь, конечно, идет только о питоне).
Так что, что list, что tuple, что array - доступ к элементу происходит со скоростью O(1).

Isem

Июль 25, 2011 11:32:02

kachayev
На самом деле, это не совсем скорость. Это алгоритмическая сложность. И она указывает нам на то, что скорость указанных операций с массивом не будет зависит от его размера, а для list - будет увеличиватся пропорционального количеству элементов в нем. Поэтому преимущество в скорости может проявится на очень больших набор данных.

Твое сообщение появилось пока я писал ответ :)

Isem
В питоне list - это и есть массив, это не список в классическом понимании этого слова.

o7412369815963

Июль 25, 2011 12:45:43

Isem
В питоне list - это и есть массив, это не список в классическом понимании этого слова.

Похоже на то, время вставки элемента (insert) увеличивается пропорционально увеличению размера.

Тогда такой вопрос, где настоящий лист, со сложностью вставки O(1) ?

o7412369815963

Июль 25, 2011 12:52:05

o7412369815963
Тогда такой вопрос, где настоящий лист, со сложностью вставки O(1) ?

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

Андрей Светлов

Июль 25, 2011 13:39:35

Классических списков не припомню. Есть http://pypi.python.org/pypi/blist/ — сложность вставки логарифмическая.