Python中对切片进行迭代的效率如何?如果无法避免使用切片,是否有替代方法?
我知道对列表进行切片操作是O(k)的,其中k是切片的大小。
x[5 : 5+k] # O(k) copy operation
然而,当我迭代列表的一部分时,我发现最干净的(也许是最Pythonic的?)方法是执行以下操作(无需使用索引):
for elem in x[5 : 5+k]:
print elem
然而,我的直觉是这仍会导致子列表的昂贵复制,而不是简单地遍历现有列表。
Python中对切片进行迭代的效率如何?如果无法避免使用切片,是否有替代方法?
我知道对列表进行切片操作是O(k)的,其中k是切片的大小。
x[5 : 5+k] # O(k) copy operation
然而,当我迭代列表的一部分时,我发现最干净的(也许是最Pythonic的?)方法是执行以下操作(无需使用索引):
for elem in x[5 : 5+k]:
print elem
然而,我的直觉是这仍会导致子列表的昂贵复制,而不是简单地遍历现有列表。
使用:
for elem in x[5 : 5+k]:
这太符合Python的编程习惯了!在你进行代码性能分析并确定这是一个瓶颈之前,请不要改变它 - 尽管我怀疑你是否会发现这是瓶颈的主要原因。
就速度而言,这可能是您最佳的选择:
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 个对现有对象的引用的列表。这可能不会成为任何内存问题的来源。
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
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
itertools.islice
不是这样使用的!它适用于对任意可迭代对象进行切片,而不会尝试使用 __getitem__
。如果您尝试从 1000000
开始使用 islice
,则 islice
将在生成任何内容之前循环遍历列表的前 1000000
个项目,完全破坏您的性能。 - user2357112lis
是什么,这是哪个Python版本?我的计时结果与你的相反。 - user2357112lis
是 range(10**6)
。这是 IPython shell,py2.7.4。 - Ashwini Chaudharyislice
可以获胜,但是如果start
比stop - start
大得多,性能会下降。请参见我(修订后的)答案中的时间数据。 - user2357112只需遍历所需的索引,不需要为此创建新切片:
for i in xrange(5, 5+k):
print x[i]
虽然看起来不太符合Python的风格,但与创建新切片相比,它更加高效,因为不会浪费额外的内存。另一种选择是使用迭代器,就像@AshwiniChaudhary的答案中所演示的那样。
IndexError
。 - Ashwini Chaudharytimeit
来测试。迭代器和切片并不花哨,它们是基本的、核心的 Python 特性。 - user2357112您已经在这个切片上进行了O(n)的迭代。在大多数情况下,这比实际创建切片更为重要,因为创建切片完全是在优化过的C语言中完成的。一旦您制作了切片,在其上循环遍历需要的时间超过切片的创建时间两倍,即使您不做任何操作:
>>> timeit.timeit('l[50:100]', 'import collections; l=range(150)')
0.46978958638010226
>>> timeit.timeit('for x in slice: pass',
'import collections; l=range(150); slice=l[50:100]')
1.2332711270150867
xrange
对索引进行迭代,但要考虑到检索列表元素所需的时间,它比切片慢。即使你跳过这一部分,它仍然不如切片快:>>> timeit.timeit('for i in xrange(50, 100): x = l[i]', 'l = range(150)')
4.3081963062022055
>>> timeit.timeit('for i in xrange(50, 100): pass', 'l = range(150)')
1.675838213385532
请不要使用itertools.islice
! 它会从列表的开始循环,而不是通过 __getitem__
跳到您想要的值。下面是一些时间数据,显示其性能取决于切片的起始位置:
>>> timeit.timeit('next(itertools.islice(l, 9, None))', 'import itertools; l = r
ange(1000000)')
0.5628290558478852
>>> timeit.timeit('next(itertools.islice(l, 999, None))', 'import itertools; l =
range(1000000)')
6.885294697594759
以下是使用普通切片操作胜过islice
的示例:
>>> timeit.timeit('for i in itertools.islice(l, 900, None): pass', 'import itert
ools; l = range(1000)')
8.979957560911316
>>> timeit.timeit('for i in l[900:]: pass', 'import itertools; l = range(1000)')
3.0318417204211983
被接受的答案未提供有效的解决方案。它是按n
顺序排列的,其中n
是一个切片起始点。如果n
很大,这将成为一个问题。
后续结论("选择正常切片")也不理想,因为它使用额外的空间按k
进行复制。
Python 提供了一种非常优雅和高效的解决方案,称为生成器表达式,可作为您可以获得的最佳效果运行:O(1)空间和O(k)运行时间:
(l[i] for i in range(n,n+k))
它类似于列表推导式,但它是惰性地工作的,您可以将其与其他迭代器工具(如itertools模块或过滤器)结合使用。请注意,表达式周围有圆括号。
如果需要迭代子数组(请参考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()
我认为更好的方法是使用类似C语言的迭代方式,如果'k'非常大(例如像10000000000000这样的大数),在Python的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小时就能完成(因为Python中的等价循环需要大约10小时),因为它只需要一次从5到10000000000005的迭代!每次使用'range()'或'xrange()'甚至是切片本身(如你上面提到的)都会使程序执行20000000000000次迭代,这可能会导致更长的执行时间。 (据我所学,使用生成器方法将返回一个可迭代对象,需要先完全运行生成器才能创建它,并且需要两倍的时间来完成工作;一次用于生成器本身,另一次用于'for'循环)
编辑:
在Python 3中,生成器方法/对象不需要先运行以创建可迭代对象供for循环使用。
range(5, 5 + k)
迭代索引。 - Mariusitertools.islice
的工作方式与我们想象的不同。如果你使用从1000000开始的islice
,Python 会在生成任何东西之前遍历您列表的前1000000个元素。这可能会将线性时间算法变成二次或更糟的复杂度。 - user2357112