このアルゴリズムを最適化できますか？

私はいくつかのオブジェクトのリストを持っており、次の関数によって返される特定の番号の特定のシーケンスで繰り返し処理したいと思います。次のことは、ハッシュ番号のモジュロに基づいて各数値をリストサイズに削除し、シーケンスを生成します。このアルゴリズムを最適化できますか？

def genSeq(hash,n): 
    l = range(n) 
    seq = [] 
    while l: 
     ind = hash % len(l) 
     seq.append(l[ind]) 
     del l[ind] 
    return seq

例：私は理解を容易にするためのpythonでアルゴを提示しています[3, 1, 4, 2, 0]

genSeq（53,5）が返されます。私はC++でコードを作成することになっています。 O（n^2）におけるこの形式の複雑さは、ベクトルとリストの両方にあります。（私達は削除またはアクセスのために支払う）。これはどんなに良くできますか？

2011-12-29 balki

あなたの 'l'に適切なデータ構造を使用すると、理論的に' log n'性能が可能になり、 'n log n'となるでしょう。それにもかかわらず、あなたの「n」が本当に大きい場合を除いて、このパフォーマンスの向上は大きいとは思えません。 – Howard

だから、n個の数字をシャッフルしたいのですが？ – Zonko

どのデータ構造が適切でしょうか？それはどのようにログに記録されますか？ – balki

skip listを入力すると、O(log n)のアクセスと削除が行われます。したがって、総トラバーサル時間はO(n log n)になります。

リニアソリューションがあると思っていますが、私には何も飛び交いません。

2011-12-29 16:50:56

-1

ベクターからは削除しないでください。末尾をスワップし、塗りつぶしポインタを減らしてください。フィッシャー・イェイツのシャッフルについて考えてみましょう。

2011-12-29 19:10:36 Svante

これは、アイテムの順序が変わるため動作しません。彼のアルゴリズムを使用した場合と同じ順序ではありません。 –

[範囲（len（l））の範囲のハッシュ％（i + 1）] は、factoradicの数字として見ることができます。パーミュテーションとファクタデジット番号の間には1つの帰結があります。

ファクタデジット番号から順列へのマッピングについては、the top answerの「インデックスシーケンスを使用してリストを許可する」セクションで説明しています。残念ながら、提供されるアルゴリズムは二次的です。しかし、アルゴリズムO（nlog（n））を作るデータ構造を指すコメント作成者がいる。

2011-12-30 06:53:13

答えて