6

複数のビット配列の最長のプレフィックスを検索する高速なアルゴリズムを見つけようとしています。私のアプリケーションでは、これらのビット配列は無限に長く、可変長にすることができます。たとえば、これらのビット配列がある場合:

0b1011001
0b1001101
0b1001010
0b1010100

最長のプレフィックスは 10 です。現在、ビット配列の OR と NAND を計算して共通の 0 と 1 を見つけ、結果を XOR しています。

OR
0b1011111

NAND
0b0111111

XOR
0b1100000

もっと速い解決策はありますか？

4

4 に答える 4

2

あなたのアプローチについて

ビット配列の数に応じて（線形に）スケーリングします。

ビット配列のサイズではうまくスケーリングされません。理想的には、ビット配列のサイズではなく、共通のプレフィックスの長さに基づいてスケーリングする必要があります。

低レベルで

ビット配列からの個々のバイト/ワードに対するビット操作は、ビットを 1 つずつ処理するよりもはるかに高速です。(ただし、Python がどれだけ低レベルの制御を提供できるかはわかりません)。

最初の提案

これがCのような低レベル言語である場合、私はあなたと同様の方法でこれを解決しますが、他の回答からのいくつかのアイデアを使用します.

この例では、コンピューターが 64 ビット マシンであると想定します。

各ビット配列の最初の 64 ビットのみ (OR NAND XOR) から始めます (これらは 64 ビット マシンでの基本的な操作であり、複雑さは O( # of array ) です)。

次に、結果で最初に設定されたビットの位置をすばやく見つけます (ほとんどのコンピューターには、Cの組み込みまたは少なくとも最適化されたアセンブリ コードで、この高速な方法がいくつかあります。設定されたビットがある場合は、その値を返します。

それ以外の場合は、各ビット配列の次の 64 ～ 127 ビットで繰り返します。

（おそらく、束の最小長のビット配列を見つけて、それを最大として使用することにより、さまざまな長さのビット配列を処理する必要があります。）

このアプローチの利点は、ビット配列の数が線形であり、共通プレフィックスの長さが線形であることです。

2番目の提案

多数のビット配列がある場合は、並列処理を使用して高速化できます。

まず、NAND と同時に OR を実行できます。

もっと工夫すれば、次のように適用できます。

4 つのビット配列 A、B、C、D がある場合

(((A OR B) OR C) OR D) の代わりに

(A OR B) OR (C OR D) を実行できます。

どちらの場合も、同じ数の OR が実行されます。

しかし、2 番目の方法は効果的に並列化できます (そして、実際には 2 番目の方法を実行した方がシングルコア マシンでは高速になる可能性があります。これは、多くの場合、CPU が実際には複数の ALU を持っているためです)。

OR の結果を保持する単一の一時変数を使用して単一の for ループを使用することはできないため、論理を書き出すのは少し面倒です。

サブ結果をビット配列の数の半分の長さの配列に格納することを想像できます。A OR B のサブ結果を array[0] に格納し、C OR D を array[1] に格納してから、array[0] OR array[1] を実行します。（そして、その結果を半分の長さの新しい配列に保存するか、配列内の値を上書きしてスペースとメモリ割り当てを節約できます）。

作業を十分な大きさのチャンクに分割して、オーバーヘッドをあまり導入せずにコンピューター全体をビジー状態に保ちます。

十分なプロセッサを使用すると、線形ではなく、ビット配列の数の対数の複雑さに近づくことができます。しかし、実際には、6 コアのマシンで 5 倍のスピードアップが得られれば、おそらくかなり良いでしょう。

于 2012-08-04T07:56:48.173 に答える
1

すべての配列を OR または NAND で処理する必要はありません (配列は任意の長さであるため、これは非常にコストがかかります)。最初の不一致が見つかったら、配列を左から右にスキャンして停止するだけです。これはO(kn)で、nは配列の数、kは共通プレフィックスの長さです。

私のpythonはひどいので、明確にするために、固定長の2つの配列を使用した非常に単純な例のみを示します。

a = [1,0,1,1,0,0,1]
b = [1,0,1,1,0,1,1]

for x in xrange(0,7):
    if a[x] != b[x]:
        print a[0:x]
        break

output:
[1, 0, 1, 1, 0]

明らかにそれを修正する必要があります。コードの背後にあるロジックを理解していれば、簡単に解決できると思います。

  • 不一致が見つかるまで (つまり、配列がすべて同じビット値を持たない)、または最短の配列の終わりまで、すべての配列の x 番目のビットに対してxを反復します。
  • array1の最初のxビットを出力します。
于 2012-08-02T12:55:17.307 に答える
0

入力文字列 s1、s2、s3 があると仮定します ...

  1. s = commonSubString(s1,s2) とする
  2. i=3..n の場合
    1. s = commonSubString(s,s2)
  3. 戻り値

最悪の場合、s1 と s2 は同一である可能性があり、その場合はヒューリスティックを使用できます (たとえば、s の最初の長さを最初に k=100 に制限します。最終的な s の長さが k=100 のままである場合は、プロセス全体を繰り返します。ただし、すべての文字列の位置 k+1 から開始します)。

于 2012-08-02T12:07:58.150 に答える
0

場合によっては、最適な解決策は、O(n) の複雑さを持つプレフィックス ツリーを使用することです。ここで、n はバイナリ文字列の共有プレフィックスの合計ですが、係数は大きくなります。

于 2012-08-02T11:51:21.540 に答える