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

9

利用：

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。因此，即使 inx中的对象很大，x[5: 5+k]也会创建一个包含 k 个元素的新列表，这些元素引用与 in 中相同的对象x。因此，您只需要额外的内存来创建一个包含 k 对预先存在的对象的引用的列表。这可能不会成为任何内存问题的根源。

于 2013-08-04T23:55:11.750 回答
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取决于切片的起点和可迭代的大小，普通切片在几乎所有情况下都会很快，应该是首选。以下是更多时间比较：

对于Huge 列表 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]

诚然：它看起来不像 Python，但它比创建新切片更有效，因为不会浪费额外的内存。另一种方法是使用迭代器，如@AshwiniChaudhary 的回答所示。

于 2013-08-04T23:38:22.557 回答
3

您已经在切片上进行了 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 上，以防任何更高版本添加特定于列表的优化。

于 2013-08-04T23:55:24.597 回答
0

我认为更好的方法是使用类似 c 的迭代，如果 'k' 很大（因为一个大的 'k' - 比如 10000000000000 - 甚至可以让你等待大约 10 个小时才能在 pythonic for 循环中得到答案）

这是我试图告诉你的：

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 小时内完成（就像 pythonic 中的 for 循环一样做大约 10 小时），因为它需要从 5 到 10000000000005 一次！每次使用 'xrange()' 的 'range()' 甚至切片本身（如上所述）都会使程序执行 20000000000000 次迭代，我认为这可能会导致更长的执行时间。（据我所知，使用生成器方法将返回一个可迭代对象，该对象需要首先完全运行生成器，并且需要两次才能完成工作；一个用于生成器本身，另一个用于“for”循环）

编辑：

在 python 3 中，生成器方法/对象不需要首先运行来为 for 循环生成可迭代对象

于 2013-08-05T00:35:18.407 回答
0

接受的答案没有提供有效的解决方案。它的顺序是n，其中n是切片起点。如果n很大，那就有问题了。后续结论（“Go for normal slices”）也不理想，因为它使用了额外的空间来k进行复制。

Python 为切片问题提供了一个非常优雅和高效的解决方案，称为生成器表达式，它可以尽可能地优化：O(1) 空间和 O(k) 运行时间：

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

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

于 2020-04-24T22:16:57.437 回答
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 回答