Python中切片上的高效迭代

tmb3ates  于 2023-10-15  发布在  Python
关注(0)|答案(7)|浏览(96)

Python中切片操作的迭代效率如何?如果复制是不可避免的切片,有替代方案吗?
我知道对列表的切片操作是O(k),其中k是切片的大小。

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

然而,当迭代列表的一部分时,我发现最干净的(也是最Python的?)这样做的方法(而不必诉诸指数)是这样做:

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

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

xe55xuns

xe55xuns1#

用途:

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个对预先存在的对象的引用的列表。这可能不会成为任何记忆问题的根源。

qeeaahzv

qeeaahzv2#

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

总结:

去正常切片。

whhtz7ly

whhtz7ly3#

只需遍历所需的索引,无需为此创建新切片:

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

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

gojuced7

gojuced74#

时间复杂度为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上,以防任何后续版本添加特定于列表的优化。

6tr1vspr

6tr1vspr5#

公认的答案并没有提供有效的解决方案。其顺序为n,其中n是切片起始点。如果n很大,这将是一个问题。后续结论(“Go for normal slices”)也不理想,因为它使用k顺序的额外空间进行复制。
Python为切片问题提供了一个非常优雅和高效的解决方案,称为生成器表达式,它可以尽可能地优化:时间复杂度为O(k)

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

它类似于列表解析,除了它的工作方式是惰性的,你可以将它与其他迭代器工具(如itertools模块或过滤器)合并结合使用。注意表达式中的圆括号。

dsf9zpds

dsf9zpds6#

对于遍历子数组(创建子数组参见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()
disho6za

disho6za7#

我认为更好的方法是使用一个类似c的迭代,如果“k”是如此之大(作为一个大的“k”-像100000000000-甚至可以让你等待大约10个小时才能在Python的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小时内完成(因为Python中的for循环需要大约10小时),因为它只需要从5到1000000000005一次!每次使用'range()'或'xrange()',甚至切片本身(如上面提到的)都会使程序进行2000000000000次迭代,这可能会导致更长的执行时间。(正如我所了解的,使用生成器方法将返回一个可迭代对象,需要首先完全运行生成器才能创建,并且需要两倍的时间来完成工作;一个用于生成器本身,另一个用于"for“循环)

编辑:

在python3中,生成器方法/对象不需要首先运行来为for循环创建可迭代对象

相关问题