リストを反復するよりも遅いリストを反転させる理由

Question

Pythonでリストを逆転させる方法は少なくとも2つありますが、少なくともPython 2.7.xではイテレータの方がはるかに高速です。私はこのスピードの違いに何が寄与しているのか理解したい。

1. reversedイテレータので、少ないメモリオーバーヘッド

Iを

reversed C

に書き込まれる。

>>> x = range(1000) 
>>> %timeit x[::-1] 
100000 loops, best of 3: 2.99 us per loop 
>>> %timeit reversed(x) 
10000000 loops, best of 3: 169 ns per loop 

Iは、速度差は、少なくとも以下に起因している疑いdisモジュールを使用してこれらの操作をより適切に表示しようとしましたが、あまり役に立ちませんでした。私はこれらの操作を分解するための関数に入れなければなりませんでした。

>> def reverselist(_list): 
...  return _list[::-1] 
... 
>>> dis.dis(reverselist) 
    2   0 LOAD_FAST    0 (_list) 
       3 LOAD_CONST    0 (None) 
       6 LOAD_CONST    0 (None) 
       9 LOAD_CONST    1 (-1) 
      12 BUILD_SLICE    3 
      15 BINARY_SUBSCR  
      16 RETURN_VALUE 
>>> def reversed_iter(_list): 
...  return reversed(_list) 
... 
>>> dis.dis(reversed_iter) 
    2   0 LOAD_GLOBAL    0 (reversed) 
       3 LOAD_FAST    0 (_list) 
       6 CALL_FUNCTION   1 
       9 RETURN_VALUE   

スライシング操作中にすべて正確に何が起こるのですか？メモリオーバーヘッドが多くありますか？たぶんスライスは純粋なPythonで実装されていますか？

Answer 1

これは、が、iteratorを返し、スライスがリスト全体を返すためです。

あなたは全体のリストにその反復子を変換する list()を使用するようにしました

>>> lis = range(10) 
>>> lis[::-1] 
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 
>>> reversed(lis) 
<listreverseiterator object at 0x909dd0c> 

：reversed上

>>> lis = range(10**5) 
>>> %timeit lis[::-1] 
100 loops, best of 3: 2.8 ms per loop 
>>> %timeit list(reversed(lis)) 
100 loops, best of 3: 3.13 ms per loop 

ヘルプ：

>>> reversed? 
Type:  type 
String Form:<type 'reversed'> 
Namespace: Python builtin 
Docstring: 
reversed(sequence) -> reverse iterator over values of the sequence 

Return a reverse iterator 

Answer 2

イテレータを返しますreversed()。 実際にはは、ループするまで何も逆になりません。

戻る逆iterator：documentationから。

元のリストを参照するが、何とアイテムではありませんちょうどイテレータを（作成

%timeit list(reversed(x)) 

：あなたはそれが再びリストにreversed()の結果を回すのにかかる時間を比較する必要が

リストの長さに初期化されたポインタ）は、何時でも何もしません。

>>> import timeit 
>>> x = range(1000) 
>>> timeit.timeit('x[::-1]', 'from __main__ import x') 
4.623600006103516 
>>> timeit.timeit('list(reversed(x))', 'from __main__ import x') 
16.647125005722046 

Answer 3

reversed()は、実際には何も逆転しない、それは単にコンテナの要素を反復処理するために使用できるオブジェクトを返します。バックリストにreversed()をオンにする必要が

は、それがたくさん遅くなります逆の順序で。これが実際に要素を逆転させるよりも速い理由です。

スライス演算子と同じことをしているreverse()もあります。

reverse()が適切に動作します。スライス演算子はリストオブジェクトを返します。