Поиск в списке быстрее, чем в кортеже? - PullRequest
Новая
       26

Поиск в списке быстрее, чем в кортеже?

21 голосов
/ 11 апреля 2011

В прошлом, когда мне требовались массивные индексные поиски в узком цикле, я обычно использовал кортежи, поскольку они, как правило, чрезвычайно производительны (близки к использованию только n-го числа переменных). Однако сегодня я решил поставить под сомнение это предположение и получил неожиданные результаты: 

In [102]: l = range(1000)
In [103]: t = tuple(range(1000))
In [107]: timeit(lambda : l[500], number = 10000000)
Out[107]: 2.465047836303711
In [108]: timeit(lambda : t[500], number = 10000000)
Out[108]: 2.8896381855010986

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

In [101]: dis.dis(lambda : l[5])
  1           0 LOAD_GLOBAL              0 (l)
              3 LOAD_CONST               1 (5)
              6 BINARY_SUBSCR       
              7 RETURN_VALUE

Для справки, типичный поиск / возврат глобальной переменной в 10 000 000 занимает 2,2 с. Кроме того, я запустил его без лямбд, знаете, на всякий случай (обратите внимание, что число = 100 000 000, а не 10 000 000). 

In [126]: timeit('t[500]', 't=range(1000)', number=100000000)
Out[126]: 6.972800970077515
In [127]: timeit('t[500]', 't=tuple(range(1000))', number=100000000)
Out[127]: 9.411366939544678

Здесь поиск кортежей занимает на 35% больше времени. Что тут происходит? Для очень плотных петель это на самом деле кажется существенным расхождением. Что может быть причиной этого?

Обратите внимание, что для разложения на переменные (например, x, y = t) кортежи немного быстрее (~ 6% в моих нескольких тестах меньше времени), а для построения из фиксированного числа аргументов кортежи быстрее сумасшедшие (~ 83 % меньше времени). Не принимайте эти результаты как общие правила; Я только что выполнил несколько мини-концертов, которые будут бессмысленными для большинства проектов. 

In [169]: print(sys.version)
2.7.1 (r271:86882M, Nov 30 2010, 09:39:13) 
[GCC 4.0.1 (Apple Inc. build 5494)]

Ответы [ 2 ]

23 голосов
/ 11 апреля 2011

Кортежи в основном быстрее для построения списков , а не для доступа к ним.

Кортежи должны быть немного быстрее, чтобы получить к ним доступ: они требуют одного косвенного обращения. Тем не менее, я считаю, что главное преимущество заключается в том, что они не требуют второго распределения при построении списка.

Списки причин для поиска немного быстрее, потому что движок Python имеет специальную оптимизацию: 

case BINARY_SUBSCR:
    w = POP();
    v = TOP();
    if (PyList_CheckExact(v) && PyInt_CheckExact(w)) {
        /* INLINE: list[int] */
        Py_ssize_t i = PyInt_AsSsize_t(w);
        if (i < 0)
            i += PyList_GET_SIZE(v);
        if (i >= 0 && i < PyList_GET_SIZE(v)) {
            x = PyList_GET_ITEM(v, i);
            Py_INCREF(x);
        }

С этой закомментированной оптимизацией кортежи работают немного быстрее списков (примерно на 4%).

Обратите внимание, что добавление отдельной оптимизации для особых случаев здесь не является хорошей идеей. Каждый такой особый случай в основном теле цикла VM увеличивает размер кода, что снижает согласованность кэша, и это означает, что для каждого другого поиска требуется дополнительная ветвь.

11 голосов
/ 11 апреля 2011

В противоположность этому, у меня совершенно другой совет.

Если данные - по природе проблемы - фиксированы по длине, используйте кортеж.

Примеры:

  • (r, g, b) - три элемента, зафиксированные в определении задачи.
  • (широта, долгота) - два элемента, зафиксированные в определении задачи

Если данные - по природе проблемы - переменные, используйте список.

Скорость составляет , а не проблема.

Значение должно быть единственным соображением.

...