5

long[]配列内のビットとして保存された真/偽の結果がたくさんあります。私はこれらの膨大な数を持っています（何百万ものロング）。

たとえば、結果が 5 つしかない場合、次のようになります。

+----- condition 5 is true
|
|+---- condition 4 is false
||
||+--- condition 3 is true
|||
|||+-- condition 2 is true
||||
||||+- condition 1 is false
10110

次のようなステートメントを表すツリーもいくつかあります。

condition1 AND (condition2 OR (condition3 AND condition 4))

木はとてもシンプルですが、とても長いです。それらは基本的に次のようになります (以下では、私が持っているものを示すために単純化しすぎています)。

class Node {    
    int operator();
    List<Node> nodes;
    int conditionNumber();    
}

基本的に、Node がリーフであり、条件番号 (long[] 配列のビットの 1 つに一致) を持つか、Node がリーフではないため、いくつかのサブノードを参照します。

シンプルですが、複雑なブール式を表現できます。それはうまくいきます。

これまでのところ、すべてがうまく機能しています。ただし、問題があります。多くの式を評価して、それらが真か偽かを判断する必要があります。基本的に、ブルートフォースよりも優れた解決策がわからない問題に対して、ブルートフォース計算を行う必要があります。

そのため、ツリーをたどってtrue、falseツリーの内容とlong[].

最適化する必要があるメソッドは次のようになります。

boolean solve( Node node, long[] trueorfalse ) {
   ...
}

ここで、最初の呼び出しでnodeは がルート ノードであり、次に明らかにサブノードです (再帰的であるため、そのsolveメソッドはそれ自体を呼び出します)。

少数の木 (おそらく最大で 100 程度) しかなく、何百万ものツリーlong[]をチェックすることを知っている場合、これを最適化するためにどのような手順を実行できますか?

明らかな再帰的な解決策は、パラメーター ((サブ) ツリーと long[]、パラメーターとして渡さないことで取り除くことができlong[]ます) を渡し、すべての再帰呼び出しなどで非常に遅くなります。 (AND または OR または NOT など) が使用され、非常に多くの if/else または switch ステートメントが含まれます。

私は別のアルゴリズムを探しているわけではありません (存在しません) ので、y が x よりも小さい O(x) から O(y) に移動することを探していません。

私が探しているのは、「x 倍」のスピードアップです。5 倍速く実行されるコードを記述できれば、5 倍のスピードアップが得られ、それで十分であり、非常に満足しています。

現時点で私が見ている唯一の拡張機能は、現在のものと比較して「x」倍の大幅な高速化になると思いますが、すべてのツリーのバイトコードを生成し、すべてのツリーのロジックをクラスにハードコーディングすることです。 . 100本ほどの木しかないので、うまくいくはずです（ただし、木は固定されていません。木がどのように見えるかを事前に知ることはできません。そうでなければ、すべての木を手動でハードコーディングするのは簡単です）。

すべてのツリーのバイトコードを生成する以外に何か考えはありますか?

バイトコード生成ルートを試してみたい場合は、どうすればよいですか?

4

3 に答える 3

3

ショートカット評価の機会を最大化するには、独自の分岐予測を行う必要があります。

あなたはそれをプロファイリングしたいかもしれません

  • どのANDブランチがfalseと評価されるか
  • どのOR分岐がtrueになるか

次に、プロファイリングステップで見つけた重みに関連してツリーを並べ替えることができます。特に気の利いたものが必要な場合は、実行時に特定のデータセットの均等化を検出するメカニズムを考案して、その場でブランチを並べ替えることができます。

後者の場合、（保存効率と実行中の結果の正確さに関して）実際のツリーを並べ替えるのではなく、ローカルで並べ替えることができるツリーノードビジター（トラバーサルアルゴリズム）を考案することをお勧めします。 「ライブ」の重みに従ってブランチ。

散文バージョンが密集していることに気付いたので、これらすべてが理にかなっていることを願っています。ただし、Fermatが言ったように、コード例は大きすぎてこのマージンに収まりません:)

于 2011-04-11T12:47:25.080 に答える
3

C では、このようなブール演算を評価する簡単で高速な方法があります。z=(x op y) を評価すると仮定すると、次のように実行できます。

 z = result[op+x+(y<<1)];

したがって、op は 4 の倍数で、AND、OR、XOR などの操作を選択します。考えられるすべての回答のルックアップ テーブルを作成します。このテーブルが十分に小さい場合は、それを単一の値にエンコードし、右シフトとマスクを使用して出力ビットを選択できます。

z = (MAGIC_NUMBER >> (op+x+(y<<1))) & 1;

これは、これらの多数を評価する最速の方法です。もちろん、複数の入力を持つ操作を、各ノードに 2 つの入力しかないツリーに分割する必要があります。ただし、これを短絡する簡単な方法はありません。ツリーをリストに変換して、各項目に操作番号と 2 つの入力と出力へのポインターを含めることができます。リスト形式になったら、単一のループを使用して、その 1 行を 100 万回非常にすばやく吹き飛ばすことができます。

小さな木の場合、これは勝利です。評価が必要なブランチの平均数が 2 から 1.5 になるため、ショート サーキットを伴う大きなツリーの場合、おそらくメリットはありません。これは、大きなツリーにとって大きなメリットです。YMMV。

EDIT：考え直し て、スキップリストのようなものを使用して短絡を実装できます。各操作 (ノード) には、比較値とスキップ カウントが含まれます。結果が比較値と一致した場合は、次のスキップ カウント値をバイパスできます。したがって、リストはツリーの深さ優先トラバーサルから作成され、最初の子には、他の子のサイズに等しいスキップ カウントが含まれます。これにより、各ノードの評価が少し複雑になりますが、短絡が可能になります。慎重に実装すると、条件チェックなしで実行できます (スキップ カウントの 1 倍または 0 倍を考えてください)。

于 2011-04-11T17:14:51.790 に答える
1

あなたのバイトコーディングのアイデアは正しい方向だと思います。言語に関係なく、プリコンパイラを作成します。各ツリーをたどり、print ステートメントを使用して、次のようなソース コードに変換します。

((word&1) && ((word&2) || ((word&4) && (word&8))))

これは、ツリーが変更されるたびにオンザフライでコンパイルでき、結果のバイト コード / dll が読み込まれます。これらすべてに 1 秒もかかりません。

問題は、現在、ツリーの内容を解釈しているということです。それらをコンパイル済みコードに変換すると、実行速度が 10 ～ 100 倍速くなります。

JDKを持っていないというあなたのコメントに応えて追加されました。次に、Java バイト コードを生成できない場合は、可能な限り高速に実行される独自のバイト コード インタープリターを作成しようとします。次のようになります。

while(iop < nop){
  switch(code[iop++]){
    case BIT1: // check the 1 bit and stack a boolean
      stack[nstack++] = ((word & 1) != 0);
      break;
    case BIT2: // check the 2 bit and stack a boolean
      stack[nstack++] = ((word & 2) != 0);
      break;
    case BIT4: // check the 4 bit and stack a boolean
      stack[nstack++] = ((word & 4) != 0);
      break;
    // etc. etc.
    case AND: // pop 2 booleans and push their AND
      nstack--;
      stack[nstack-1] = (stack[nstack-1] && stack[nstack]);
      break;
    case OR: // pop 2 booleans and push their OR
      nstack--;
      stack[nstack-1] = (stack[nstack-1] || stack[nstack]);
      break;
  }
}

アイデアは、コンパイラがスイッチをジャンプ テーブルに変換するようにすることで、最小のサイクル数で各操作を実行します。オペコードを生成するには、ツリーの後置ウォークを実行するだけです。

その上、ド・モルガンの法則を操作して単純化できる可能性があるため、一度に複数のビットをチェックできます。

于 2011-04-11T15:45:44.760 に答える