DjangoBB LoFi version

Полная версия: Работа со словарем, какой вариант быстрее?

Начало » Python для новичков » Работа со словарем, какой вариант быстрее?

1 2

o7412369815963

Окт. 25, 2011 21:52:35

Enchantner
o7412369815963
1) Сравните поиск по ключу в словаре из 5М элементов, и выборка из листа в 2 элемента.
Товарищ, вы знаете, что такое O(1)? Это значит, что выборка из контейнера в общем случае не зависит от количества элементов в нём. В основе списка лежит массив, выборка по индексу (указателю). В основе словаря - хэш-таблица, в которой выборка может затормаживаться коллизиями, которые вряд ли присутствуют в наборе из нескольких элементов.

Знаю, но в основе списка (list) лежит список а не массив, на форуме где тема была с разборкой этого, поэтому в худшем случае там будет не О(1).
А вот от dict.iteritems() я ожидал выдачу элементов, подрят, без поиска, т.е. выдачу соседних элементов. а оно похоже просто берет очередной ключ и выбирает значение.

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

Окт. 25, 2011 22:07:41

o7412369815963, list хранит элементы таки в массиве.
Смотрите Objects/listobject.c: PyList_GetItem
dict тоже идет по соседним узлам:
Objects/dictobject.c: dictiter_iternextitem

Enchantner

Окт. 25, 2011 22:13:59

o7412369815963
http://wiki.python.org/moin/TimeComplexity
в помощь

o7412369815963

Окт. 26, 2011 02:17:28

> list хранит элементы таки в массиве.

Практика этого не подтверждает:

#-*- coding: UTF-8 -*-

def test1(d):
    for x in xrange(100000):
        d.index(50, 0)

import timeit

print timeit.timeit('test(d)', 'from __main__ import test1 as test; d = range(100)', number = 1)
print timeit.timeit('test(d)', 'from __main__ import test1 as test; d = range(10**7)', number = 1)

результат:

0.115697860718
0.118525028229

в документации написано: Insert O(n), тогда O(50000) не должно было быть равным по времени O(10**7),

o7412369815963

Окт. 26, 2011 02:40:22

Андрей Светлов
dict тоже идет по соседним узлам:

#-*- coding: UTF-8 -*-

di = dict([ (i, 0) for i in xrange(10**7) ])

def test1(d):
    for k, v in d.iteritems():
        pass

def test2(d):
    for k in d:
        v = d[k]

def test3(d):
    for k in d:
        v = 0

import timeit

print timeit.timeit('test(d)', 'from __main__ import test1 as test, di as d', number = 1)
print timeit.timeit('test(d)', 'from __main__ import test2 as test, di as d', number = 1)
print timeit.timeit('test(d)', 'from __main__ import test3 as test, di as d', number = 1)

результат

0.514173984528
0.560081005096
0.30243396759

т.е. перебор ключей + отдельно выборка = interitems, если бы шло по соседним узлам то результат должен был быть примерно как test3 ( т.е. на поиск, преобразование ключа в хеш и прочее время бы не тратилось т.к. соседний узел под рукой )

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

Окт. 26, 2011 02:48:30

o7412369815963, вы исходники читать умеете? Или предпочитаете гадание?

К слову, а что тест должен показать? Не вижу никаких противоречий…

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

Окт. 26, 2011 02:52:20

iteritems создает tuple — вот время и вырастает

o7412369815963

Окт. 26, 2011 11:35:19

Андрей Светлов
К слову, а что тест должен показать? Не вижу никаких противоречий…

В исходниках идет вставка в массив, вот смещение массива с конца до места вставки:

    for (i = n; --i >= where; )
        items[i+1] = items[i];

вот на это тратиться O(n),
в 1 тесте этих перемещений примерно: 10**5 / 2 = 50k
во 2-м: 10**7 * 10**5 + 10**5 / 2 = 10**12,
у меня отдельно этот цикл на gcc занимает 11мин, поэтому непонятно, как питон умудряется делать это мгновенно.

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

Окт. 26, 2011 13:20:55

Да, но в тесте создается list один раз, параметр setup у timeit не учитывается в подсчете времени.
А потом простая итерация на 50 элементов.

o7412369815963

Окт. 26, 2011 14:57:50

Андрей Светлов
Да, но в тесте создается list один раз, параметр setup у timeit не учитывается в подсчете времени.
А потом простая итерация на 50 элементов.

мдя, я в тесте опечатался, автодополнитель мне index вместо insert подставил, я все это время считал что там insert… 8-\