6

我有一个大的可迭代对象，实际上，一个大的可迭代对象由以下公式给出：

itertools.permutations(range(10))

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

  1. 将可迭代对象转换为列表并获取第 1000000 个元素：

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

  2. 手动跳过元素直到 999999：

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

  3. 手动跳过元素 v2：

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

  4. 使用来自 itertools 的 islice：

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

但我仍然不觉得它们都不是 python 的优雅方式。第一个选项太昂贵了，它需要计算整个迭代来访问单个元素。如果我没记错的话，islice 在内部进行的计算与我在方法 2 中所做的计算相同，并且几乎与第 3 次一样，也许它有更多的冗余操作。

所以，我只是好奇，想知道在 python 中是否有其他方式可以访问可迭代的具体元素，或者至少以更优雅的方式跳过第一个元素，或者我只需要使用一个以上的。

4

3 回答 3

16

使用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 倍。

于 2013-05-28T20:25:52.880 回答
4

找到第 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 倍以上。请注意，我确实对原始代码进行了轻微修改，以便它不再破坏原始列表。

于 2013-05-28T20:41:15.943 回答
2

为了获得下一个而啜饮一百万件物品确实是非常浪费的。不幸的是，是否可以避免取决于您的迭代器：如果迭代器有直接跳转到特定偏移量的方法，它可以实现该__getitem__方法，您可以使用它直接请求iterator[1000000]。（它如何到达那里取决于生成算法）。

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

PS。鉴于您的问题的上下文，我将概述一种用于直接生成第 n 个排列的算法，但我看到 @FJ 击败了我。不错的解决方案！:-)

于 2013-05-28T20:46:36.960 回答