DjangoBB LoFi version

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

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

1 2

o7412369815963

Июль 23, 2011 13:05:20

По логике, скорость доступа к массивам должна быть выше, а тут лист всех порвал.

# coding:utf8

import array
from time import time
import numpy as np

COUNT = 10**7

l = [0 for i in xrange(COUNT)]
t = tuple(l)
a = array.array('l',l)
n = np.zeros(COUNT)

def calc_delta():
    t1 = time()
    for i in xrange(COUNT):
        pass
    return (time() - t1) * 1000
delta = calc_delta()

def sm(x):
    t1 = time()
    for i in xrange(COUNT):
        x[i]
    print type(x), (time() - t1) * 1000 - delta

sm(l)
sm(t)
sm(a)
sm(n)

результат:

<type 'list'> 300.084114075
<type 'tuple'> 530.132055283
<type 'array.array'> 667.308330536
<type 'numpy.ndarray'> 1605.17811775

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

Июль 23, 2011 19:55:42

1. list в Питоне имеет константное время доступа к элементу. Зато вставка-удаление — O(N).
2. Если уж меряем — то давайте делать это более корректно. В вашем случае первый выигрывает.

import array                                                                                                                                                                     
import numpy                                                                                                                                                                     
import random                                                                                                                                                                    
import sys                                                                                                                                                                       
import timeit                                                                                                                                                                    
                                                                                                                                                                                 
from collections import defaultdict                                                                                                                                              
                                                                                                                                                                                 
COUNT = 10**7                                                                                                                                                                    
                                                                                                                                                                                 
a = (list(xrange(COUNT)), tuple(xrange(COUNT)),                                                                                                                                  
     array.array('l', list(xrange(COUNT))),                                                                                                                                      
     numpy.zeros(COUNT))                                                                                                                                                         
                                                                                                                                                                                 
                                                                                                                                                                                 
def f(collection, count):                                                                                                                                                        
    l = len(collection)                                                                                                                                                          
    for i in xrange(count):                                                                                                                                                      
        ind = random.randint(0, l-1)                                                                                                                                             
        collection[ind]                                                                                                                                                          
                                                                                                                                                                                 
print '-' * 80                                                                                                                                                                   
                                                                                                                                                                                 
                                                                                                                                                                                 
res = defaultdict(list)                                                                                                                                                          
                                                                                                                                                                                 
                                                                                                                                                                                 
for i in xrange(100):                                                                                                                                                            
    col = random.choice(a)                                                                                                                                                       
    res[type(col)].append(timeit.timeit("f(col, 100)", "from __main__ import f, col",                                                                                            
                        number=1000))                                                                                                                                            
    sys.stdout.write('.')                                                                                                                                                        
    sys.stdout.flush()                                                                                                                                                           
                                                                                                                                                                                 
print                                                                                                                                                                            
for key, val in res.iteritems():                                                                                                                                                 
    print key, sum(val) / len(val)

дает результат

——————————————————————————–
……………………………………………………………………………………….
<type ‘numpy.ndarray’> 0.18912228294
<type ‘array.array’> 0.161817329901
<type ‘tuple’> 0.174325704575
<type ‘list’> 0.173715612163
Что больше похоже на правду — все примерно равноценны.

o7412369815963

Июль 23, 2011 21:23:54

Андрей Светлов
Что больше похоже на правду — все примерно равноценны.

Все примерно равны потому что вы меряете скорость рандома:

for i in xrange(count):
    ind = random.randint(0, l-1)

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

Июль 23, 2011 23:07:15

И то верно. Ступил.
Поправил:

import array
import numpy
import random
import sys
import timeit

from collections import defaultdict

COUNT = 10**7

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

indices = random.sample(a[0], 1000)

def f(collection, indices=indices):
    for i in indices:
        collection[i]

print('-' * 80)

res = defaultdict(list)

for i in xrange(100):
    col = random.choice(a)
    res[type(col)].append(timeit.timeit("f(col)", "from __main__ import f, col",
                        number=1000))
    sys.stdout.write('.')
    sys.stdout.flush()

print('')
for key, val in res.iteritems():
    print(key, sum(val) / len(val))

(<type ‘array.array’>, 0.08111019288339923)
(<type ‘numpy.ndarray’>, 0.13737227366520807)
(<type ‘tuple’>, 0.09698744824058131)
(<type ‘list’>, 0.06958240270614624)

Результаты похожи на ваши. Почему list быстрый — понимаю. Почему tuple на 30% медленней — понять не могу. Очень похожие структуры и SUBSCR для обоих выполняется практически одинаково…

ZAN

Июль 23, 2011 23:58:30

Судя по всему дело в оптимизации:

        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);
                }
                else
                    goto slow_get;
            }
            else
              slow_get:
                x = PyObject_GetItem(v, w);

o7412369815963

Июль 24, 2011 00:30:41

Вот код получения элемента из тупла, берется напрямую из массива - должен работать быстро…

PyObject *
PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)
{
    if (!PyTuple_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        PyErr_SetString(PyExc_IndexError, "tuple index out of range");
        return NULL;
    }
    return ((PyTupleObject *)op) -> ob_item[i];
}

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

Июль 24, 2011 00:59:40

ZAN прав. Для tuple берется не PyTuple_GetItem а tuplesubscript из того же файла.

Isem

Июль 25, 2011 07:45:45

Для должной точности надо уменьшить количество вызовов функции f и увеличить выборку для индексов в цикле функции f и тогда array оказывается впереди планеты всей.
К примеру:

indices = random.sample(a[0], 100000)

res[type(col)].append(timeit.timeit("f(col)", "from __main__ import f, col",
                        number=10))

А разница между tuple и list будет эфимерна.

o7412369815963

Июль 25, 2011 09:27:47

Isem
Для должной точности надо уменьшить количество вызовов функции f и увеличить выборку для индексов в цикле функции f и тогда array оказывается впереди планеты всей.

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

(<type 'list'>, 0.33289950370788574)
(<type 'array.array'>, 0.38352442741394044)
(<type 'numpy.ndarray'>, 0.44202763693673269)
(<type 'tuple'>, 0.57573616504669189)

o7412369815963

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

Isem
Для должной точности надо ,,,

Для точности нужно исключить затрачиваемое время на list в каждом тесте:

    for i in indices:

и нужно перенести все переменные из глобальника в локальную область - быстродействие может повыситься в 2 раза и более