私はN次元の畳み込みに似た何かを実行していますが、メモリと時間を節約するために、進むにつれて互いに近い値を組み合わせます。
- 配列内のキーを探します。
- キーが見つかったら、そのキーに保存されている値に追加します。
- キーが見つからない場合は、次に高いキーと次に低いキーを見つけます。
- 2つの隣接ノードの近い方が十分に近い場合、そのキーと値のペアを累積します。
- それ以外の場合は、新しいキーと値のペアを追加します。
キーはダブルです。それは常にポジティブであり、決して無限ではありません。（私は特別にゼロを扱います。）値はペニーから1000億までの範囲になると思います。アルゴリズムが進行して最大配列サイズを10,000〜1,000,000に維持すると、丸めの粗さが変化します。（テストのみが、速度、メモリ、精度の間のトレードオフのスイートスポットを明らかにします。）値の範囲とアレイサイズの関係から、直接アドレス指定は実用的ではありません。スパースストレージが必要です。
単純なアプローチは、リストを使用し、BinarySearchを実行してキーまたは挿入ポイントを見つけ、そこから続行することです。これは最も近いキーを見つけるのに速く、キーの順序で繰り返すことができますが、挿入はひどいです。（削除を実行する必要はありません！外側のループで反復するたびに、新しいリストが最初から作成されます。）
どのようなデータ構造が推奨されますか？ウィキペディアでは、Trie、Judyarrayなどのいくつかについて言及しています。
（私は何年も前に同様の特性を持つTrieのようなものを実装しましたが、それはJavaであり、実装に1週間かかり、トリッキーでした。時間に追われています。）
アップデート：
SortedSetの提案により、要件を変更することになります。次に低いキーと次に高いキーを見つけることが私のタスクを達成する方法でしたが、SortedSet.GetViewBetweenは別の方法で処理を行います。集計するのに十分近い値があるかどうかを確認したいだけで、特定の丸め粒度Gがあるので、を使用して関心のあるすべての要素を要求できます。
var possibilities = mySet.GetViewBetween(x - G, x + G)
そのセットが空の場合は、追加する必要があります。そうでない場合は、おそらく小さなセットであり、私はそれを繰り返します。
パフォーマンステストを実行して、十分に高速かどうかを確認する必要があります。ただし、そうでない場合でも、同じコントラクトを持つ別のコレクションは、FindNextHighestKeyおよびFindNextLowestKeyの代替として受け入れられます。
更新2：
プレーンディクショナリを使用し、カスタムの丸め関数を使用してキーをバケットに強制することにしました。並べ替えられた順序でアイテムを繰り返すことは重要ではありません。この丸め関数を使用することで、集計するのに「十分に近い」値を見つけることができます。反復中に粒度を変更しません。新しい次元で畳み込みを終えるたびに調整します。反復ごとに、そのパスの結果を保持するための新しい配列を作成します。