优雅的方法跳过可迭代对象中的元素

Question

我有一个很大的可迭代对象，实际上是由以下内容提供的：

itertools.permutations(range(10))

我想访问第一百万个元素。我已经用不同的方法解决了问题。

1. Casting iterable to list and getting 1000000th element:

   return list(permutations(range(10)))[999999]
   

2. Manually skiping elements till 999999:

   p = permutations(range(10))
   for i in xrange(999999): p.next()
   return p.next()
   

3. Manually skiping elements v2:

   p = permutations(range(10))
   for i, element in enumerate(p):
       if i == 999999:
           return element
   

4. Using islice from itertools:

   return islice(permutations(range(10)), 999999, 1000000).next()
   

但我仍然觉得它们中没有一个是Python优雅地完成这项工作的方法。第一种选择太费资源了，需要计算整个可迭代对象才能访问单个元素。如果我没错的话，islice在内部执行了我在方法2中刚刚做的相同计算，并且几乎与第3个选项完全相同，也许甚至有更多冗余操作。

所以，我只是好奇，想知道在Python中是否有其他方式可以访问可迭代对象的特定元素，或者至少跳过前面的元素，以一种更加优雅的方式，或者我只需要使用上述其中之一。

- Imanol Luengo

Answer 1

使用itertools模块中的consume方法可以跳过n个元素：

def consume(iterator, n):
    "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)

注意那里的islice()调用; 它使用n，n，有效地不返回任何内容，并且next()函数会回退到默认值。

简化为您的示例，其中您要跳过999999个元素，然后返回第1000000个元素：

return next(islice(permutations(range(10)), 999999, 1000000))

islice() 在 C 中处理迭代器，这是 Python 循环无法超越的。

为了说明，以下是每种方法仅重复 10 次的时间：

>>> from itertools import islice, permutations
>>> from timeit import timeit
>>> def list_index():
...     return list(permutations(range(10)))[999999]
... 
>>> def for_loop():
...     p = permutations(range(10))
...     for i in xrange(999999): p.next()
...     return p.next()
... 
>>> def enumerate_loop():
...     p = permutations(range(10))
...     for i, element in enumerate(p):
...         if i == 999999:
...             return element
... 
>>> def islice_next():
...     return next(islice(permutations(range(10)), 999999, 1000000))
... 
>>> timeit('f()', 'from __main__ import list_index as f', number=10)
5.550895929336548
>>> timeit('f()', 'from __main__ import for_loop as f', number=10)
1.6166789531707764
>>> timeit('f()', 'from __main__ import enumerate_loop as f', number=10)
1.2498459815979004
>>> timeit('f()', 'from __main__ import islice_next as f', number=10)
0.18969106674194336

islice() 方法的速度几乎比下一个最快的方法快了7倍。

- Martijn Pieters

---

那个回答非常快速和详细，非常好。顺便说一下，你还教了我使用timeit调用函数的方法。谢谢 =D - Imanol Luengo

Answer 2

找到第n个排列可能只是一个示例，但如果这确实是你要解决的问题，那么有更好的方法来解决它。而不是跳过迭代器的元素，您可以直接计算第n个排列。借用这里的另一个答案的代码:

import math

def nthperm(li, n):
    li = list(li)
    n -= 1
    s = len(li)
    res = []
    if math.factorial(s) <= n:
        return None
    for x in range(s-1,-1,-1):
        f = math.factorial(x)
        d = n / f
        n -= d * f
        res.append(li[d])
        del(li[d])
    return res

示例和时间比较：

In [4]: nthperm(range(10), 1000000)
Out[4]: [2, 7, 8, 3, 9, 1, 5, 4, 6, 0]

In [5]: next(islice(permutations(range(10)), 999999, 1000000))
Out[5]: (2, 7, 8, 3, 9, 1, 5, 4, 6, 0)

In [6]: %timeit nthperm(range(10), 1000000)
100000 loops, best of 3: 9.01 us per loop

In [7]: %timeit next(islice(permutations(range(10)), 999999, 1000000))
10 loops, best of 3: 29.5 ms per loop

同样的答案，速度提升了3000倍以上。请注意，我对原始代码进行了轻微修改，以使其不再破坏原始列表。

- Andrew Clark

---

这不是问题的关键，我只是好奇如何更快地跳过可迭代对象中的元素。不过，你的答案是解决第n个阶乘更快的有趣方法。我给了你+1。谢谢！ - Imanol Luengo

Answer 3

在获取下一个项目之前，浪费时间获取一百万个项目确实是非常浪费的。不幸的是，是否可以避免这种情况取决于您的迭代器：如果迭代器有一种方法可以直接跳到特定偏移量，它可以实现__getitem__方法，并且您可以使用它直接请求iterator[1000000]。（如何到达那里取决于生成算法）。

如果您的数据源需要按顺序生成所有先前的值才能到达那里，那么如何丢弃它们是最小的问题。您可以选择一种好的方式，但这只是锦上添花。

附：鉴于您的问题背景，我想概述一种直接生成第n个排列的算法，但我看到@F.J.已经解决了它。不错的解决方案！ :-)

- alexis

---

许多进程无法提供此选项；例如网络套接字。或者是具有可变长度行的文件，需要跳过 x 行。但是，如果您可以直接“查找”到所需项目，则请使用该功能。 - Martijn Pieters

没错，这就是我想说的。"不优雅"（即低效）的是，通常没有办法避免生成被跳过的项目。 - alexis