6

私は大きな iterable を持っています。実際、大きな iterable は以下によって与えられます:

itertools.permutations(range(10))

100万番目の要素にアクセスしたいです。私はすでにいくつかの異なる方法で問題を解決しています。

  1. iterable をリストにキャストして 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のエレガントな方法ではないように感じていません. 最初のオプションはコストが高すぎます。単一の要素にアクセスするためだけに iterable 全体を計算する必要があります。私が間違っていなければ、islice は方法 2 で行ったのと同じ計算を内部的に実行し、ほぼ正確に 3 番目と同じです。おそらく、さらに冗長な操作があります。

だから、私はただ興味があります.Pythonにイテラブルの具体的な要素にアクセスするための他の方法があるかどうか、または少なくとも最初の要素をスキップするためのよりエレガントな方法があるかどうか、または単に1つを使用する必要があるかどうか疑問に思っています上記の。

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 番目の順列を見つけることは単なる例かもしれませんが、これが実際に解決しようとしている問題である場合は、これを行うためのより良い方法があります。iterable の要素をスキップする代わりに、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 に答える