在Python中对切片进行高效迭代

Question

Python中切片操作的迭代效率如何？如果切片不可避免地复制,是否有替代方案？

我知道列表上的切片操作是O(k),其中k是切片的大小.

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

然而,当迭代列表的一部分时,我发现最干净(和大多数Pythonic？)的方式(不必求助于索引)是这样做的:

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

然而,我的直觉是,这仍然会导致子列表的昂贵副本,而不是简单地迭代现有列表.

Answer 1

使用:

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

这是Pythonic!在你对代码进行分析并确定这是一个瓶颈之前不要改变这一点 - 尽管我怀疑你会发现这是瓶颈的主要来源.

在速度方面,它可能是您的最佳选择:

In [30]: x = range(100)

In [31]: k = 90

In [32]: %timeit x[5:5+k]
1000000 loops, best of 3: 357 ns per loop

In [35]: %timeit list(IT.islice(x, 5, 5+k))
100000 loops, best of 3: 2.42 us per loop

In [36]: %timeit [x[i] for i in xrange(5, 5+k)]
100000 loops, best of 3: 5.71 us per loop

在记忆方面,你可能没想到的那么糟糕.x[5: 5+k]是一部分的浅层副本x.因此,即使对象x很大,x[5: 5+k]也会创建一个包含k个元素的新列表,这些元素引用与之相同的对象x.因此,您只需要额外的内存来创建一个列表,其中包含对先前存在的对象的k个引用.这可能不会成为任何内存问题的根源.

Answer 2

您可以使用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

结论:

去正常切片.