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

Question

Раньше, когда мне требовались индексированные поисковые запросы с массивами в узком цикле, я обычно использую кортежи, поскольку они, как представляется, в целом чрезвычайно эффективны (близко к использованию только 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  

Для справки, типичный 10000000 глобальной переменной подстановки/возвращает принимать 2.2s. Кроме того, я запустил его без лямбда, а на всякий случай (обратите внимание, что число = 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% меньше времени). Не принимайте эти результаты как общие правила; Я просто выполнил несколько minitests, которые будут бессмысленны для большинства проектов.

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

Answer 1

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

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

Причина списки несколько быстрее для поисков происходит потому, что 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, увеличивает размер кода, что уменьшает согласованность кеша, и это означает, что для любого типа поиска требуется дополнительная ветвь.

Answer 2

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

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

Примеры:

• (г, г, б) - три элемента, фиксированный по определению проблемы.
• (широта, долгота) - два элемента, фиксированного по определению проблемы

Если данные - по характеру задачи - переменная, использовать список.

Ставка ¥ не вопрос.

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