Pythonでのスライス操作の反復はどのくらい効率的ですか? また、スライスでコピーが避けられない場合、代替手段はありますか?
リストに対するスライス操作は O(k) であることがわかっています。ここで、k はスライスのサイズです。
x[5 : 5+k] # O(k) copy operation
ただし、リストの一部を反復処理する場合、これを行う最もクリーンな (そして最も Pythonic な?) 方法 (インデックスに頼る必要なし) は、次のようにすることです。
for elem in x[5 : 5+k]:
print elem
ただし、私の直感では、既存のリストを単純に反復するのではなく、サブリストのコストのかかるコピーが依然として発生します。
itertools.isliceリストからスライスされたイテレータを取得するために使用できます。
例：
>>> from itertools import islice
>>> lis = range(20)
>>> for x in islice(lis, 10, None, 1):
... print x
...
10
11
12
13
14
15
16
17
18
19
@ user2357112が指摘したように、パフォーマンスはisliceスライスの開始点と反復可能なサイズに依存し、通常のスライスはほとんどすべての場合に高速になり、優先されるはずです。次に、タイミングの比較をいくつか示します。
巨大なリスト の場合islice、スライスの開始点がリストのサイズの半分未満の場合、通常のスライスよりわずかに高速か同等です。より大きなインデックスの場合、通常のスライスが明らかに勝者です。
>>> def func(lis, n):
it = iter(lis)
for x in islice(it, n, None, 1):pass
...
>>> def func1(lis, n):
#it = iter(lis)
for x in islice(lis, n, None, 1):pass
...
>>> def func2(lis, n):
for x in lis[n:]:pass
...
>>> lis = range(10**6)
>>> n = 100
>>> %timeit func(lis, n)
10 loops, best of 3: 62.1 ms per loop
>>> %timeit func1(lis, n)
1 loops, best of 3: 60.8 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 82.8 ms per loop
>>> n = 1000
>>> %timeit func(lis, n)
10 loops, best of 3: 64.4 ms per loop
>>> %timeit func1(lis, n)
1 loops, best of 3: 60.3 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 85.8 ms per loop
>>> n = 10**4
>>> %timeit func(lis, n)
10 loops, best of 3: 61.4 ms per loop
>>> %timeit func1(lis, n)
10 loops, best of 3: 61 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 80.8 ms per loop
>>> n = (10**6)/2
>>> %timeit func(lis, n)
10 loops, best of 3: 39.2 ms per loop
>>> %timeit func1(lis, n)
10 loops, best of 3: 39.6 ms per loop
>>> %timeit func2(lis, n)
10 loops, best of 3: 41.5 ms per loop
>>> n = (10**6)-1000
>>> %timeit func(lis, n)
100 loops, best of 3: 18.9 ms per loop
>>> %timeit func1(lis, n)
100 loops, best of 3: 18.8 ms per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 50.9 us per loop #clear winner for large index
>>> %timeit func1(lis, n)
小さなリストの場合、通常のスライスはisliceほとんどすべての場合よりも高速です。
>>> lis = range(1000)
>>> n = 100
>>> %timeit func(lis, n)
10000 loops, best of 3: 60.7 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 59.6 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 59.9 us per loop
>>> n = 500
>>> %timeit func(lis, n)
10000 loops, best of 3: 38.4 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 33.9 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 26.6 us per loop
>>> n = 900
>>> %timeit func(lis, n)
10000 loops, best of 3: 20.1 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 17.2 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 11.3 us per loop
通常のスライスに進みます。
目的のインデックスをトラバースするだけです。このために新しいスライスを作成する必要はありません。
for i in xrange(5, 5+k):
print x[i]
確かに: これは非 Pythonic に見えますが、余分なメモリが浪費されないという意味で、新しいスライスを作成するよりも効率的です。@AshwiniChaudharyの回答に示されているように、代わりにイテレータを使用することもできます。
「k」が非常に大きい場合、より良い方法はcのような反復を使用することだと思います（10000000000000のような大きな「k」は、pythonic forループで回答を得るために約10時間待たせる可能性があります）
これが私があなたに伝えようとしていることです：
i = 5 ## which is the initial value
f = 5 + k ## which will be the final index
while i < f:
print(x[i])
i += 1
5 から 10000000000005 に 1 回だけ移動する必要があるため、私が言った大きな k に対して、これは 5 時間で実行できると思います (pythonic の同等の for ループは約 10 時間実行します)。「xrange()」の「range()」を使用するたびに、またはスライス自体(上記のように)でさえ、プログラムは20000000000000回の反復を実行するだけで、実行時間が長くなる可能性があります。（ジェネレーターメソッドを使用すると、最初にジェネレーターを完全に実行する必要がある反復可能なオブジェクトが返され、ジョブを実行するのに2倍の時間がかかります。1つはジェネレーター自体用で、もう1つは「for」ループ用です）
編集:
Python 3 では、for ループの反復可能なオブジェクトを作成するために、ジェネレーター メソッド/オブジェクトを最初に実行する必要はありません。
サブ配列を反復処理する場合 (サブ配列の作成については、unutbu の回答を参照)、スライスは最悪の場合のインデックス作成よりもわずかにl[1:]高速です ( )。
10 items
========
Slicing: 2.570001e-06 s
Indexing: 3.269997e-06 s
100 items
=========
Slicing: 6.820001e-06 s
Indexing: 1.220000e-05 s
1000 items
==========
Slicing: 7.647000e-05 s
Indexing: 1.482100e-04 s
10000 items
===========
Slicing: 2.876200e-04 s
Indexing: 5.270000e-04 s
100000 items
============
Slicing: 3.763300e-03 s
Indexing: 7.731050e-03 s
1000000 items
=============
Slicing: 2.963523e-02 s
Indexing: 4.921381e-02 s
ベンチマーク コード:
def f_slice(l):
for v in l[1:]:
_x = v
def f_index(l):
for i in range(1, len(l)):
_x = l[i]
from time import perf_counter
def func_time(func, l):
start = perf_counter()
func(l)
return perf_counter()-start
def bench(num_item):
l = list(range(num_item))
times = 10
t_index = t_slice = 0
for _ in range(times):
t_slice += func_time(f_slice, l)
t_index += func_time(f_index, l)
print(f"Slicing: {t_slice/times:e} s")
print(f"Indexing: {t_index/times:e} s")
for i in range(1, 7):
s = f"{10**i} items"
print(s)
print('='*len(s))
bench(10**i)
print()