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

Enchantner

o7412369815963
1) Сравните поиск по ключу в словаре из 5М элементов, и выборка из листа в 2 элемента.

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

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

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

> 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

Отредактировано (Окт. 26, 2011 02:19:37)

Андрей Светлов
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

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

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

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

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

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

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

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