Почему list (xrange) медленнее range ()?


Я провел несколько тестов и обнаружил, что xrange() намного быстрее, чем range() (что подтверждается также различными вопросами / ответами):

>>> from timeit import timeit
>>> timeit(stmt = 'x = range(1000)', number = 10000)
0.38216601211680734
>>> timeit(stmt = 'x = xrange(1000)', number = 10000)
0.010537726631953959 # xrange is much faster than range

Мне стало любопытно, поэтому я попробовал другой тест, чтобы увидеть, если list(xrange(1000)) будет по-прежнему будет быстрее, чем Просто range(1000):

>>> timeit(stmt = 'x = range(1000)', number = 10000)
0.3858838963796529
>>> timeit(stmt = 'x = list(xrange(1000))', number = 10000)
0.492734766028903 # now, xrange is slower

Это также верно и для других вызовов:

>>> timeit(stmt = 'x = range(1000)', number = 100000)
3.6457308233315757
>>> timeit(stmt = 'x = list(xrange(1000))', number = 100000)
5.722031755612818
Итак, мой вопрос в том, почему list(xrange) значительно медленнее, чем range сам по себе?

Я видел этот вопрос о медлительности list(), dict(), и прочее методы конструктора , так вот почему list(xrange) настолько медленнее?

Используя dis.dis(), я обнаружил, что list(xrange) выполняет больше вычислений, чем range):

>>> dis.dis('x = list(xrange(1000))')
          0 SETUP_LOOP      15648 (to 15651)
          3 SLICE+2        
          4 IMPORT_NAME     29545 (29545)
          7 LOAD_GLOBAL     30760 (30760)
         10 POP_JUMP_IF_FALSE 28257
         13 BUILD_LIST      10341
         16 <49>           
         17 <48>           
         18 <48>           
         19 <48>           
         20 STORE_SLICE+1  
         21 STORE_SLICE+1  
>>> dis.dis('x = range(1000)')
          0 SETUP_LOOP      15648 (to 15651)
          3 SLICE+2        
          4 POP_JUMP_IF_FALSE 28257
          7 BUILD_LIST      10341
         10 <49>           
         11 <48>           
         12 <48>           
         13 <48>           
         14 STORE_SLICE+1  
2 2

2 ответа:

Конечно, range() будет быстрее, когда конечный продукт, который вы хотите, - это список всех чисел в диапазоне, range делает все это в одном вызове функции. В отличие от list(xrange()), который обременяет конструктор list(..) накладными расходами объекта rangeiterator, созданного для итерации над объектом xrange, который должен потреблять конструктор list(..). В то время как range() создает список немедленно, без промежуточного потребления итератора... как это можно победить? Основное отличие: 1 вызов функции vs 2 и менее важно 1 глобальный поиск против 2.

range() сразу же составлю список и верну его вам. Поэтому, если у него много элементов, он медленно строится.

С другой стороны, xrange() возвращает непосредственно итератор-подобный объект, который выдает значения, когда вы их просите. Из документов:

Xrange (start, stop [, step])
Эта функция очень похожа на range (), но возвращает объект xrange вместо списка. Это непрозрачный тип последовательности, который дает те же значения, что и соответствующий список, фактически не сохраняя их все одновременно. Преимущество xrange() перед range() минимально (так как xrange() все еще должен создавать значения, когда их просят) , за исключением, когда очень большой диапазон используется на машине с нехваткой памяти или когда все элементы диапазона никогда не используются (например, когда цикл обычно заканчивается разрывом).

Итак, в первом примере xrange() естественно быстрее, а во втором-медленнее, потому что, в то время как range() уже возвращает список (который не будет преобразован тогда), list(xrange()) придется сделать больше работы, чтобы не только производить значения, но и создавать новый список и хранить значения.

P. S. Это справедливо для Python 2. В Python 3 вместо этого есть только range(), который работает точно так же, как Python 2-xrange().