16

Pythonでのスライス操作の反復はどのくらい効率的ですか? また、スライスでコピーが避けられない場合、代替手段はありますか?

リストに対するスライス操作は O(k) であることがわかっています。ここで、k はスライスのサイズです。

x[5 : 5+k]  # O(k) copy operation

ただし、リストの一部を反復処理する場合、これを行う最もクリーンな (そして最も Pythonic な?) 方法 (インデックスに頼る必要なし) は、次のようにすることです。

for elem in x[5 : 5+k]:
  print elem

ただし、私の直感では、既存のリストを単純に反復するのではなく、サブリストのコストのかかるコピーが依然として発生します。

4

7 に答える 7

6

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

結論：

通常のスライスに進みます。

于 2013-08-04T23:38:50.340 に答える
4

目的のインデックスをトラバースするだけです。このために新しいスライスを作成する必要はありません。

for i in xrange(5, 5+k):
    print x[i]

確かに: これは非 Pythonic に見えますが、余分なメモリが浪費されないという意味で、新しいスライスを作成するよりも効率的です。@AshwiniChaudharyの回答に示されているように、代わりにイテレータを使用することもできます。

于 2013-08-04T23:38:22.557 に答える
0

「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 ループの反復可能なオブジェクトを作成するために、ジェネレーター メソッド/オブジェクトを最初に実行する必要はありません。

于 2013-08-05T00:35:18.407 に答える
0

サブ配列を反復処理する場合 (サブ配列の作成については、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()
于 2022-01-01T11:43:46.363 に答える