6

Python でリストを逆にする方法は少なくとも 2 つありますが、イテレータ アプローチの方がはるかに高速です (少なくとも Python 2.7.x では)。この速度差の原因を理解したいと思います。

>>> 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

速度の違いは、少なくとも次のことが原因であると思われます。

  1. reversedCで書かれています
  2. reversedはイテレータであるため、メモリ オーバーヘッドが少ない

これらの操作をよりよく理解するためにモジュールを使用しようとしました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で実装されているのでしょうか?

4

3 に答える 3

12

これは、スライス中にリスト全体を返すreversedためです。iterator

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

list()そのイテレータをリスト全体に変換するために使用する必要があります。

>>> 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: _

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

Return a reverse iterator
于 2013-05-09T15:08:33.387 に答える
4

reversed()イテレータを返します。ループするまで、実際には何も逆になりません。ドキュメントから:

逆反復子を返します。

の結果をreversed()再びリストに変換するのにかかる時間を比較する必要があります。

%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
于 2013-05-09T15:08:41.133 に答える