木よりも速いデータ構造を使うことができますか？

Question

私はバイナリデシジョンツリーを持っています。それは入力を浮動小数点の配列として受け取り、各分岐ノードは入力インデックスと値を分割し、最終的に私を葉にします。

パフォーマンス分析（編集：他の領域を最適化して、現在はほぼ40％になっています）によれば、実行時間の約17％）がこのツリーで大量に検索されています。検索速度を改善するために別のデータ構造を使用する必要があります。

入力が葉ノードに直接マップされないため、何らかのハッシュテーブルを使用することはできませんが、ツリーの代わりに使用できるメソッドやデータ構造について誰かが示唆していたのでしょうかルックアップ速度を向上させるために、

メモリは懸念されますが、速度よりも懸念されます。

コードは現在C＃で書かれていますが、明らかにどのような方法でも適用できます。

編集： 投稿するにはあまりにも多くのコードがありますが、私はその木についてもっと詳しく説明します。

ツリーは情報ゲインの計算を使用して生成されますが、必ずしも50/50の分割ではなく、分割値は任意の浮動小数点値にすることができます。 1つの入力を複数回分割して、その入力の解像度を上げることもできます。

私はここで、イテレータのパフォーマンスについての質問投稿：

Micro optimisations iterating through a tree in C#

をしかし、私はさらにパフォーマンスを向上させるためのデータ構造自体を見る必要があるかもしれないと思います。

私はできるだけ多くのパフォーマンスを目指しています。私は機械学習の新しい方法に取り組んでいます。木はフィードバックループを使って自ら成長します。私が取り組んでいるプロセスでは、数ヶ月間稼働すると見積もられているので、数％の節約は大規模です。究極の目標は、あまりにも多くのメモリを使わずにスピードを上げることです。

Answer 1

仮定の決定は50/50のチャンスがあります：あなたは2つのバイナリの決定があったことを想像し

を。可能なパスは00,01,10,11です。

ツリーの代わりに4つの結果を持つ配列を想像してください。浮動小数点配列をこの配列のインデックスとなる2進数に変換することができます。

Answer 2

私が正しく理解していれば、浮動小数点の範囲は決定にマップする必要があります。このようなもの：

 x <= 0.0  : Decision A 
0.0 < x <= 0.5  : Decision B 
0.5 < x <= 0.6  : Decision C 
0.6 < x    : Decision D 

バイナリツリーは、これを処理するかなり良い方法です。ツリーのバランスがよく、入力値が範囲全体に均等に分散されていれば、O（log n）個の比較を期待できます。ここでnは考えられる決定の数です。

ツリーのバランスが取れていない場合は、必要以上に多くの比較を行うことができます。最悪の場合：O（n）。だから私は木々を見て、彼らがどれほど深いかを見ていきます。同じツリーが何度も何度も使用されると、一度リバランスを取るために費やされたコストは、多くのルックアップで償却されることがあります。

入力値が均等に分布していない場合は（事前にわかっている）、最も一般的なケースが早期に検出されるように、比較の順序を特別にすることができます。これを行うには、ツリーを操作するか、実際にツリーをチェックする前にコードに特殊なケースを追加します。

アルゴリズムの改良を使い果たしても最適化が必要な場合は、一般的なバイナリツリーよりも局所性の高いデータ構造を調べることができます。たとえば、パーティション境界を連続した配列に配置し、バイナリ検索を実行できます。 （配列が長すぎない場合は、キャッシュと分岐予測の方がわかりやすいので、配列の線形検索を試みることもできます）。

最後に、それは私たちに木（または配列）への頭出しを与えます。たとえば、入力値の最上位ビットのいくつかをインデックスとして使用し、それがツリーの最初の数レイヤをカットできるかどうかを確認します。これはスキップされた比較が正しい分岐予測を得る可能性が低いため、想像以上に役立ちます。