Python:迭代子列表

mbjcgjjk  于 2023-03-20  发布在  Python
关注(0)|答案(5)|浏览(128)

通常,当你想在Python中迭代列表的一部分时,最简单的方法就是对列表进行切片。

# Iterate over everything except the first item in a list
#
items = [1,2,3,4]
iterrange = (x for x in items[1:])

但是slice操作符创建了一个新的列表,这在很多情况下是不必要的。理想情况下,我希望使用某种创建生成器的slice函数,而不是创建新的列表对象。类似的操作可以通过创建一个生成器表达式来完成,该表达式使用range只返回列表的特定部分:

# Create a generator expression that returns everything except 
# the first item in the list
#
iterrange = (x for x, idx in zip(items, range(0, len(items))) if idx != 0)

但是这有点麻烦,我想知道是否有更好,更优雅的方法来做这个,那么,最简单的方法是什么,来切片一个列表,从而创建一个生成器表达式,而不是一个新的列表对象呢?

ldxq2e6h

ldxq2e6h1#

使用迭代工具。islice:

import itertools

l = range(20)

for i in itertools.islice(l,10,15):
    print i

10
11
12
13
14

来自文档:
创建一个迭代器,从可迭代对象中返回选定的元素

cl25kdpy

cl25kdpy2#

在开始之前,需要说明的是,在切片方法之间进行选择的正确顺序通常是:
1.使用常规切片(复制除最长输入之外的所有输入的成本通常没有意义,并且代码要简单得多)。如果输入可能不是可切片序列类型,则将其转换为可切片序列类型,然后切片,例如allbutone = list(someiterable)[1:]。这比任何其他方法都更简单,并且在大多数情况下通常更快。
1.如果常规切片不可行(输入不保证是序列,并且在切片之前转换成序列可能导致存储器问题,或者它很大并且切片覆盖了它的大部分,例如跳过10 M元素list的前1000个和后1000个元素,因此存储器可能是个问题),itertools.islice通常是正确的解决方案,因为它非常简单,而且性能成本通常并不重要。
1.当且仅当islice的性能慢得无法接受(它增加了生成每一项的开销,尽管不可否认这是一个相当小的量) 并且 * 要跳过的数据量很小,而要包含的数据量很大(例如OP跳过单个元素并保留其余元素的场景),继续阅读*
如果您发现自己处于第三种情况,那么islice快速绕过初始元素的能力不足以弥补生成其余元素所增加的成本。在这种情况下,您可以通过将问题从 * 选择 * n之后的所有元素 * 转换为 * 丢弃 * n之前的所有元素 * 来提高性能。
对于这种方法,您可以手动将输入转换为迭代器,然后显式地取出并丢弃n值,然后迭代迭代器中剩余的内容(但不需要islice的每个元素开销)。例如,对于myinput = list(range(1, 10000))的输入,您可以选择元素1到元素末尾的选项:

# Approach 1, OP's approach, simple slice:
for x in myinput[1:]:

# Approach 2, Sebastian's approach, using itertools.islice:
for x in islice(myinput, 1, None):

# Approach 3 (my approach)
myiter = iter(myinput)  # Explicitly create iterator from input (looping does this already)
next(myiter, None) # Throw away one element, providing None default to avoid StopIteration error
for x in myiter:  # Iterate unwrapped iterator

如果要丢弃的元素数量较大,最好从itertools文档中借用consume的方法:

def consume(iterator, n=None):
    "Advance the iterator n-steps ahead. If n is None, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

这使得跳过n元素的方法一般化为:

# Approach 1, OP's approach, simple slice:
for x in myinput[n:]:

# Approach 2, Sebastian's approach, using itertools.islice:
for x in islice(myinput, n, None):

# Approach 3 (my approach)
myiter = iter(myinput)  # Explicitly create iterator from input (looping does this already)
consume(myiter, n)      # Throw away n elements
# Or inlined consume as next(islice(myiter, n, n), None)
for x in myiter:        # Iterate unwrapped iterator

就性能而言,对于大多数大型输入而言,这将赢得有意义的优势(例外情况:Python 3上的range本身已经针对普通切片进行了优化;ipython3微基准测试(在CPython 3.6,64位Linux版本上)说明了这一点(设置中slurp的定义只是一种方法,用于使运行出可迭代对象的开销最低,从而使我们不感兴趣的东西的影响最小化):

>>> from itertools import islice
>>> from collections import deque
>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(10000))
... slurp(r[1:])
...
65.8 μs ± 109 ns per loop (mean ± std. dev. of 5 runs, 10000 loops each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(10000))
... slurp(islice(r, 1, None))
...
70.7 μs ± 104 ns per loop (mean ± std. dev. of 5 runs, 10000 loops each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(10000))
... ir = iter(r)
... next(islice(ir, 1, 1), None)  # Inlined consume for simplicity, but with islice wrapping to show generalized usage
... slurp(ir)
...
30.3 μs ± 64.1 ns per loop (mean ± std. dev. of 5 runs, 10000 loops each)

显然,我的解决方案的额外复杂性通常是不值得的,但是对于中等大小的输入(本例中为10 K个元素),性能优势是显而易见的;islice表现最差(差了一点),普通切片稍好一些(这强化了我的观点,即当你有一个实际的序列时,普通切片几乎总是最好的解决方案),相对而言,“转换为迭代器,丢弃初始值,使用rest”的方法赢得了巨大的胜利(不到任何一个不足解决方案的一半时间)。
这种好处不会体现在微小的输入上,因为加载/调用iter/next的固定开销,尤其是islice,将超过节省的开销:

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(10))
... slurp(r[1:])
...
207 ns ± 1.86 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(10))
... slurp(islice(r, 1, None))
...
307 ns ± 1.71 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(10))
... ir = iter(r)
... next(islice(ir, 1, 1), None)  # Inlined consume for simplicity, but with islice wrapping to show generalized usage
... slurp(ir)
...
518 ns ± 4.5 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(10))
... ir = iter(r)
... next(ir, None)  # To show fixed overhead of islice, use next without it
... slurp(ir)
...
341 ns ± 0.947 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

但是正如你所看到的,即使对于10个元素,islice-free方法也没有差多少;100个元素,islice自由的方法比所有竞争者快,200个元素,通用的next + islice击败所有竞争者(显然,考虑到islice的180 ns开销,它没有击败islice-free,但是这通过一般化为作为单个步骤跳过n元素来弥补,而不需要重复调用next来跳过一个以上的元素)。普通的islice很少在“跳过一些,保留很多”的情况下获胜,这是由于 Package 器要求的每个元素的开销(直到大约100 K个元素时,它才明显地击败微基准测试中的渴望切片;它的内存效率高,但CPU效率低),而且在“跳过很多,保留一些”的情况下,它会做得更差(相对于急切切片)。

性能 * 至关重要 * 时针对特定内置序列的特殊情况黑客攻击

大多数带O(1)索引的内置序列的特殊情况(listtuplestr等,不包括collections.deque

把它埋在最下面,因为尽管它绝对是最快的解决方案,但它也是类型特定的(不会在任意可迭代对象上工作),并且它依赖于实现细节(具体地说,Python内置序列的pickle功能的实现;这是 * 不太可能 * 改变,因为如果支持被移除,它将破坏现有pickle数据,但这不是语言保证)。如果您处于以下情况:
1.输入是list(或其他具有O(1)索引的内置平面序列类型,如tuplestr,但 * 不是 * collections.deque,它是O(n)索引)

1.要跳过的项目数量巨大
1.要选择的项的数量也是巨大的(你甚至不想为一个浅拷贝切片所产生的指针支付内存成本)
直接操作迭代器跳过开销为O(1)的项(这里使用consume方法,不管是否内联,跳过的项都是O(n)),这在本质上与上面的方法#3相同,只是我们滥用了序列迭代器的设计,直接跳到我们关心的索引:

# Approach 4 (my hacky, but performant, approach)
myiter = iter(myinput)  # Explicitly create iterator from input like before
myiter.__setstate__(n)  # Set n as the next index to iterate
for x in myiter:        # Iterate updated iterator

比较之前针对较大输入的最佳解决方案(使用内联-consume)、普通切片(具有相关内存成本和急切操作)、手动更改迭代器位置(使用CPython 3.11.1 64位Linux构建版本)的计时:

>>> from itertools import islice
>>> from collections import deque
>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(100_000_000))  # *Much* bigger input
... ir = iter(r)
... next(islice(ir, 90_000_000, 90_000_000), None)  # *Much* bigger skip
... slurp(ir)                                       # *Much* larger amount to consume
...
339 ms ± 3.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(100_000_000))
... slurp(r[90_000_000:])
...
104 ms ± 648 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = list(range(100_000_000))
... ir = iter(r)
... ir.__setstate__(90_000_000)
... slurp(ir)
...
32.7 ms ± 278 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

对于这个“跳过90 M,占用10 M”的场景,普通切片所需的时间大约是优化的内联consume的三分之一,而手动迭代器操作所需的时间又是普通切片的三分之一(因为普通切片实际上必须做3倍的迭代工作,一次从输入复制到切片副本,一次迭代它,并且一次用于在释放切片时递减引用)。如果您不希望保留跳过阈值之后的所有项,切片可能是最佳解决方案,但是您 * 可以 * 在此时 Package islice,以便从pre-advanced迭代器中拉取n项。

collections.deque的特殊情况

对于任意的迭代,这显然行不通(dict [及其视图和迭代器]、set [及其迭代器]、打开文件对象等),因此内联的consume仍然是唯一的真实的选项。尽管collections.deque是特殊情况,因为虽然它不支持切片,并且它的迭代器不支持__setstate__,它 * 确实 * 支持旋转,所以你可以写一个定制的 Package 器来旋转你想要的元素到前面,islice它们关闭,然后再旋转回来切片就完成了(依赖于在迭代过程中不需要修改deque)。

def fast_islice_deque(deq, *slc):
    try:
        [stop] = slc  # Check for simple case, just islicing from beginning
    except ValueError:
        pass
    else:
        yield from islice(deq, stop)  # No need for rotation, just pull what we need

    # We need to rotate, which requires some fix-ups to indices first
    start, stop, step = slice(*slc).indices(len(deq))
    stop -= start  # Rotate takes care of start
    deq.rotate(-start)  # Move elements we care about to start with tiny amount of work
    try:
        yield from islice(deq, None, stop, step)
    finally:
        deq.rotate(start)  # Restore original ordering with tiny amount of work

同样,64位Linux上CPython 3.11.1的计时:

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = deque(range(100_000_000))  # Same huge input, as deque
... ir = iter(r)
... next(islice(ir, 90_000_000, 90_000_000), None)
... slurp(ir)
...
368 ms ± 2.06 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = deque(range(100_000_000))
... slurp(fast_islice_deque(r, 90_000_000, None))
...
245 ms ± 5.34 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

或者比较在跳过之后提取较少数量的项目:

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = deque(range(100_000_000))  # Same huge input, as deque
... slurp(islice(r, 90_000_000, 90_001_000))  # Need islice to bound selection anyway, so no pre-consume
...
331 ms ± 4.43 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %%timeit -r5 slurp = deque(maxlen=0).extend; r = deque(range(100_000_000))
... slurp(fast_islice_deque(r, 90_000_000, 90_001_000))
...
19.4 ms ± 138 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

如您所见,使用rotate在这两种情况下都节省了大量的工作量,当拉取数量较少的项时尤其有用。它并不是那么有用,仅仅是因为拉动10 M个项目的成本明显高于跳过前90 M个项目的成本,并且您要支付每个项目的成本。islice的项目开销,其中内联consume方法不需要将其用于您拉取的项目。但是当拉取小的/有界的数量时,两种方法都需要支付每个项目的islice开销成本,但是基于rotate的解决方案,虽然 * 技术上 * 仍然是O(n),但 * 显著 * 减少了工作量(它不涉及任何引用计数,只需修复块指针,以完成与islice一样复杂的工作)。

mwg9r5ms

mwg9r5ms3#

受ShadowRanger的answer和多种高效解决方案的启发,这里有另一个解决方案。在“块”中工作。在我的实验中,它比大列表切片快2.5倍。而且对于小块,内存使用率很低。
下面是处理单个列表切片的过程:

for element in lst[start:]:
    # do something with the element

分块处理的过程可能是这样的:

for i in range(start, len(lst), chunksize):
    for element in lst[i : i+chunksize]:
        # do something with the element

正如ShadowRanger所说,列表切片速度很快,但需要经过三个步骤:用于创建、迭代和丢弃切片。如果切片很大,则对缓存不友好。大致来说:假设你有1 MB的缓存,列表切片及其元素有2 MB,那么在第一次传递结束时,列表的后半部分在缓存中,而前半部分不在缓存中,所以第二次传递没有从该高速缓存中受益:在前半部分,缓存中没有任何内容,在后半部分,缓存中也没有任何内容,因为前半部分刚刚替换该高速缓存中的所有内容,第三遍也是如此。
现在,我们不再创建、迭代和丢弃单个较大的存储片,而是在较小的区块中执行此操作。**然后,每个区块的第二次和第三次传递都可以受益于仍在缓存中的区块数据。**这就是加快速度的原因。
下面是一个实验,我创建了一个包含1600万个元素的列表,并将其分成不同大小的块进行处理,从包含16个元素的小块一直到包含所有1600万个元素的单个块:

chunk size 2^4     19.8 ± 0.6 ns / element
chunk size 2^5     13.2 ± 0.2 ns / element
chunk size 2^6     10.2 ± 0.0 ns / element
chunk size 2^7      8.9 ± 0.1 ns / element
chunk size 2^8      8.3 ± 0.2 ns / element
chunk size 2^9      7.6 ± 0.1 ns / element
chunk size 2^10     7.5 ± 0.0 ns / element
chunk size 2^11     7.4 ± 0.0 ns / element
chunk size 2^12     7.3 ± 0.1 ns / element
chunk size 2^13     7.4 ± 0.0 ns / element
chunk size 2^14     7.8 ± 0.1 ns / element
chunk size 2^15     8.4 ± 0.0 ns / element
chunk size 2^16     8.9 ± 0.1 ns / element
chunk size 2^17     9.5 ± 0.1 ns / element
chunk size 2^18    10.4 ± 0.1 ns / element
chunk size 2^19    11.3 ± 0.3 ns / element
chunk size 2^20    12.0 ± 0.1 ns / element
chunk size 2^21    12.1 ± 0.2 ns / element
chunk size 2^22    13.9 ± 0.1 ns / element
chunk size 2^23    13.8 ± 0.2 ns / element
chunk size 2^24    13.8 ± 0.1 ns / element

我们看到三件事:

  • 由于分块开销的原因,小块速度较慢。
  • 大块比较慢,如上所述。
  • 最佳块大小似乎是212个元素左右。

这是因为列表中的元素是按创建顺序排列的,所以列表中相邻的元素在内存中也是相邻的,如果我们打乱它们的顺序,使相邻的元素分散在内存中,事情会变得更慢,也会有一些变化(注意,我在这里只使用了200万个元素,因为它太慢了):

chunk size 2^4     38.3 ± 0.7 ns / element
chunk size 2^5     29.5 ± 0.0 ns / element
chunk size 2^6     24.0 ± 0.4 ns / element
chunk size 2^7     21.0 ± 0.3 ns / element
chunk size 2^8     19.8 ± 0.3 ns / element
chunk size 2^9     19.6 ± 0.2 ns / element
chunk size 2^10    19.5 ± 0.3 ns / element
chunk size 2^11    19.6 ± 0.5 ns / element
chunk size 2^12    21.1 ± 0.5 ns / element
chunk size 2^13    25.4 ± 0.1 ns / element
chunk size 2^14    29.3 ± 0.5 ns / element
chunk size 2^15    33.5 ± 0.4 ns / element
chunk size 2^16    37.3 ± 0.2 ns / element
chunk size 2^17    41.1 ± 0.4 ns / element
chunk size 2^18    46.7 ± 0.2 ns / element
chunk size 2^19    48.1 ± 0.7 ns / element
chunk size 2^20    48.9 ± 0.3 ns / element
chunk size 2^21    49.0 ± 0.1 ns / element

现在,最佳的块大小大约是210个元素,比使用一个包含200万个元素的大切片快2.5倍。
在这两种情况下,块大小为210的元素都很好,所以这是我的建议。虽然它取决于缓存大小,所以不同的计算机可以有不同的最佳大小。此外,如果你的对象较大,或者你实际上是用元素做一些事情,所以你也使用缓存,那么较小的块大小可能更好。
同意,写作

for i in range(start, len(lst), chunksize):
    for element in lst[i : i+chunksize]:
        # do something with the element

与简单的单个列表切片相比是很麻烦的。我们可以编写工具函数来帮助我们,所以我们可以编写

for chunk in chunks(lst, start):
    for element in chunk:
        # do something with the element

或者甚至:

for element in islice_chunked(lst, start):
    # do something with the element

(Note它不使用itertools.islice,我之所以这样称呼它,是因为它同样提供了一个元素迭代器。)
从索引700万开始迭代1000万个元素的混洗列表的基准:

179 ms ± 1.9 ms  use_chunks1
188 ms ± 4.6 ms  use_islice_chunked
230 ms ± 7.3 ms  use_chunks2
349 ms ± 2.0 ms  use_one_slice
459 ms ± 4.9 ms  use_islice

工具函数还可以扩展为支持stopstep参数。留给读者作为练习(或者我可以稍后添加,但目前的简单函数足以演示该技术及其好处,这是我的主要目标)。
基准代码(Attempt This Online!):

from itertools import islice, chain
from collections import deque
from timeit import default_timer as time
from random import shuffle
from statistics import mean, stdev

slurp = deque(maxlen=0).extend
lst = list(range(10_000_000))
shuffle(lst)
start = 7_000_000

def chunks(seq, start):
    chunk_size = 2**10
    for start in range(start, len(seq), chunk_size):
        yield seq[start : start+chunk_size]

def islice_chunked(seq, start):
    """Like islice(seq, start, None), but
       using list slice chunks for more speed."""
    return chain.from_iterable(chunks(seq, start))

def use_one_slice(lst, start):
    slurp(lst[start:])

def use_islice(lst, start):
    slurp(islice(lst, start, None))

def use_chunks1(lst, start):
    slurp(map(slurp, chunks(lst, start)))

def use_chunks2(lst, start):
    for chunk in chunks(lst, start):
        slurp(chunk)

def use_islice_chunked(lst, start):
    slurp(islice_chunked(lst, start))

funcs = use_one_slice, use_islice, use_chunks1, use_chunks2, use_islice_chunked

times = {f: [] for f in funcs}
def stats(f):
    ts = [t * 1e3 for t in sorted(times[f])[:3]]
    return f'{round(mean(ts))} ms ± {stdev(ts):3.1f} ms '
for _ in range(10):
    for f in funcs:
        t = time()
        f(lst, start)
        times[f].append(time() - t)
for f in sorted(funcs, key=stats):
    print(stats(f), f.__name__)

初始实验代码(Attempt This Online!):

from collections import deque
from timeit import default_timer as time
from statistics import mean, stdev
from random import shuffle

shuffled = False

E = 21 if shuffled else 24
es = range(4, E+1)
n = 2 ** E
lst = list(range(n))
if shuffled:
    shuffle(lst)
slurp = deque(maxlen=0).extend

def run(lst, chunksize):
    for start in range(0, n, chunksize):
        slurp(lst[start : start+chunksize])

times = {e: [] for e in es}
def stats(f):
    ts = [t / n * 1e9 for t in sorted(times[f])[:3]]
    return f'{mean(ts):6.1f} ± {stdev(ts):3.1f} ns'
for _ in range(20 if shuffled else 10):
    for e in es:
        t = time()
        run(lst, 2 ** e)
        times[e].append(time() - t)
for e in es:
    print(f'chunk size 2^{e:<3}', stats(e), '/ element')
v1uwarro

v1uwarro4#

试试itertools.islice:
http://docs.python.org/library/itertools.html#itertools.islice

iterrange = itertools.islice(items, 1, None)
kt06eoxx

kt06eoxx5#

使用itertools.islice的可接受答案并不完全令人满意:是的,这很容易,但是islice必须消耗列表的第一个元素,如果列表很大并且您从一个大索引开始,则这可能会很慢。
我的建议是编写自己的迭代器:

def gen_slice(my_list, *slice):
    for i in range(*slice):
        yield my_list[i]

或者,更简洁地说:

gen_slice_map = lambda my_list, *slice: map(my_list.__getitem__, range(*slice))

查看性能差异--注意第一个是ms,而其他是ns(另外,事实证明显式的for循环实际上比map版本稍微快一点,尽管正如@ShadowRanger在评论中指出的那样这只是因为我下面的示例是提取单个示例,而map版本对于较大的列表更快):

my_list = list(range(100_000_000))

%timeit list(islice(my_list, 99_000_000, 99_000_001))
400 ms ± 18.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(gen_slice(my_list, 99_000_000, 99_000_001))
409 ns ± 8.46 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit list(gen_slice_map(my_list, 99_000_000, 99_000_001))
430 ns ± 6.36 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

相关问题