Python中对切片的高效迭代

Question

Python中对切片进行迭代的效率如何？如果无法避免使用切片，是否有替代方法？

我知道对列表进行切片操作是O(k)的，其中k是切片的大小。

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

然而，当我迭代列表的一部分时，我发现最干净的（也许是最Pythonic的？）方法是执行以下操作（无需使用索引）：

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

然而，我的直觉是这仍会导致子列表的昂贵复制，而不是简单地遍历现有列表。

- WaelJ

---

如果您担心复制切片，那么另一种选择是使用 range(5, 5 + k) 迭代索引。 - Marius

危险！你之前得到了错误的建议; itertools.islice 的工作方式与我们想象的不同。如果你使用从1000000开始的 islice，Python 会在生成任何东西之前遍历您列表的前1000000个元素。这可能会将线性时间算法变成二次或更糟的复杂度。 - user2357112

Answer 1

使用：

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 个对现有对象的引用的列表。这可能不会成为任何内存问题的来源。

- unutbu

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

结论：选择普通切片。

- Ashwini Chaudhary

---

itertools.islice 不是这样使用的！它适用于对任意可迭代对象进行切片，而不会尝试使用 __getitem__。如果您尝试从 1000000 开始使用 islice，则 islice 将在生成任何内容之前循环遍历列表的前 1000000 个项目，完全破坏您的性能。 - user2357112

如果你尝试从开头到结尾迭代一个大量的小片段列表，那么时间复杂度将是二次的；你的运行时间将与切片数量成二次关系，而不是与列表大小成线性关系。 - user2357112

lis是什么，这是哪个Python版本？我的计时结果与你的相反。 - user2357112

@user2357112 lis 是 range(10**6)。这是 IPython shell，py2.7.4。 - Ashwini Chaudhary

当切片比前面的部分大时，islice可以获胜，但是如果start比stop - start大得多，性能会下降。请参见我（修订后的）答案中的时间数据。 - user2357112

Answer 3

只需遍历所需的索引，不需要为此创建新切片：

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

虽然看起来不太符合Python的风格，但与创建新切片相比，它更加高效，因为不会浪费额外的内存。另一种选择是使用迭代器，就像@AshwiniChaudhary的答案中所演示的那样。

- Óscar López

---

使用基于索引的方法的另一个问题是 IndexError。 - Ashwini Chaudhary

我相信对于这样一个简单的使用场景，最好的答案是更简单的。并不是所有的东西都必须花哨和Pythonic，包括迭代器、切片和推导式等等。对于我们这些来自C语言背景的人来说，有时候一个好的基于索引的遍历就可以很好地解决问题。 - Óscar López

这实际上是最慢的解决方案。你可以用 timeit 来测试。迭代器和切片并不花哨，它们是基本的、核心的 Python 特性。 - user2357112

@user2357112 嗯，这真是让人大开眼界！ - Óscar López

Answer 4

您已经在这个切片上进行了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

这是在Python 2.7.5上，如果任何后续版本添加了列表特定的优化，则会影响到此代码。

- user2357112

Answer 5

被接受的答案未提供有效的解决方案。它是按n顺序排列的，其中n是一个切片起始点。如果n很大，这将成为一个问题。 后续结论("选择正常切片")也不理想，因为它使用额外的空间按k进行复制。

Python 提供了一种非常优雅和高效的解决方案，称为生成器表达式，可作为您可以获得的最佳效果运行：O(1)空间和O(k)运行时间：

(l[i] for i in range(n,n+k))

它类似于列表推导式，但它是惰性地工作的，您可以将其与其他迭代器工具（如itertools模块或过滤器）结合使用。请注意，表达式周围有圆括号。

- yurgis

Answer 6

如果需要迭代子数组（请参考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()

- tejasvi88

Answer 7

我认为更好的方法是使用类似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循环使用。

- ARF

---

这实际上更慢！计时并查看。 - user2357112