9

この以前のスタック オーバーフローの質問に触発されて、各イテラブル内の要素の順序を維持しながら、Python でイテラブルをランダムにインターリーブする方法を検討してきました。例えば：

>>> def interleave(*iterables):
...     "Return the source iterables randomly interleaved"
...     <insert magic here>
>>> interleave(xrange(1, 5), xrange(5, 10), xrange(10, 15))
[1, 5, 10, 11, 2, 6, 3, 12, 4, 13, 7, 14, 8, 9]

元の質問は、2 つのリスト a と b をランダムにインターリーブするように求められ、受け入れられた解決策は次のとおりです。

>>> c = [x.pop(0) for x in random.sample([a]*len(a) + [b]*len(b), len(a)+len(b))]

ただし、このソリューションは 2 つのリストに対してのみ機能し (簡単に拡張できます)、a と b がリストであるという事実に依存しているため、それらに対してpop()およびlen()を呼び出すことができます。つまり、イテラブルでは使用できません。また、ソース リスト a と b を空にするという不幸な副作用もあります。

元の質問に対して与えられた代替回答は、ソースリストのコピーを取得して変更を回避しますが、特にソースリストがかなり大きい場合、これは非効率的だと思います。代替の回答も利用するためlen()、単なるイテラブルでは使用できません。

任意の数の入力リストに対して機能し、それらを変更しない独自のソリューションを作成しました。

def interleave(*args):
    iters = [i for i, b in ((iter(a), a) for a in args) for _ in xrange(len(b))]
    random.shuffle(iters)
    return map(next, iters)

ただし、このソリューションは、ソース引数がリストであることに依存しているため、len()それらで使用できます。

それで、事前にイテラブルの長さを知る必要がなく、イテラブルのコピーを取らない、要素の元の順序を維持しながら、Pythonでイテラブルをランダムにインターリーブする効率的な方法はありますか?

編集：元の質問と同様に、公平にするためにランダム化は必要ないことに注意してください。

4

3 に答える 3

10

ジェネレーターを使用してそれを行う 1 つの方法を次に示します。

import random

def interleave(*args):
  iters = map(iter, args)
  while iters:
    it = random.choice(iters)
    try:
      yield next(it)
    except StopIteration:
      iters.remove(it)

print list(interleave(xrange(1, 5), xrange(5, 10), xrange(10, 15)))
于 2012-05-18T07:27:36.597 に答える
3

あなたが「公平」になりたいのなら、そうではありません。

100万個のアイテムを含むリストと、2個のアイテムのみを含むリストがあるとします。「公正な」ランダム化では、ショートリストの最初の要素が約300000程度のインデックスで発生します。

a,a,a,a,a,a,a,...,a,a,a,b,a,a,a,....
                        ^

ただし、リストの長さがわかるまで、事前に知る方法はありません。

50％（1 / n）の確率で各リストから取得する場合、リストの長さを知らなくても実行できますが、次のようなものが得られます。

a,a,b,a,b,a,a,a,a,a,a,a,a,a,a,a,...
    ^   ^
于 2012-05-18T07:23:29.990 に答える
3

aix が提供するソリューションが質問の要件を満たしていることに満足しています。しかし、Mark Byers のコメントを読んだ後、この解決策がいかに「不公平」であるかを知りたいと思いました。

さらに、私がこの質問を書いた後、スタック オーバーフロー ユーザーの EOLが元の質問に対する別の解決策を投稿し、「公正な」結果が得られました。EOL の解決策は次のとおりです。

>>> a.reverse()
>>> b.reverse()
>>> [(a if random.randrange(0, len(a)+len(b)) < len(a) else b).pop()
...     for _ in xrange(len(a)+len(b))]

また、独自のソリューションをさらに拡張して、引数のサポートに依存せず len()、ソース iterable のコピーを作成するようにしました。

def interleave(*args):
    iters = sum(([iter(list_arg)]*len(list_arg) for list_arg in map(list, args)), [])
    random.shuffle(iters)
    return map(next, iters)

または、別の書き方:

def interleave(*args):
    iters = [i for i, j in ((iter(k), k) for k in map(list, args)) for _ in j]
    random.shuffle(iters)
    return map(next, iters)

次に、FJによって書かれ、上記の質問で再現された元の質問に対する受け入れられた解決策を、aix、EOL、および私自身の解決策に対してテストしました。このテストでは、30000 個の要素のリストを 1 つの要素リスト (センチネル) にインターリーブしました。テストを 1000 回繰り返しました。次の表は、アルゴリズムごとに、インターリーブ後のセンチネルの最小、最大、および平均インデックスと、合計所要時間を示しています。「公正な」アルゴリズムは、平均値が約 1 になると予想されます。15,000:

algo    min             max             mean            total_seconds
----    ---             ---             ----            -------------
F.J:    5               29952           14626.3         152.1
aix:    0               8               0.9             27.5
EOL:    45              29972           15091.0         61.2
srgerg: 23              29978           14961.6         18.6

結果からわかるように、FJ、EOL、および srgerg の各アルゴリズムは、表向きは「公正な」結果を生成します (少なくとも、指定されたテスト条件下では)。ただし、aix のアルゴリズムでは常に、センチネルが結果の最初の 10 要素内に配置されていました。実験を数回繰り返しましたが、同様の結果が得られました。

したがって、Mark Byers は正しいことが証明されています。真にランダムなインターリーブが必要な場合は、ソース iterable の長さを事前に知る必要があるか、長さを決定できるようにコピーを作成する必要があります。

于 2012-05-19T03:23:46.997 に答える