「辞書」に何千ものキーを挿入することに関して、C ++の内部についてよく知っているように見える人から、別のフォーラムで次の投稿を読んでいました。
e) マップとセットのルックアップは Red-Black または Balanced Tree で行われ、各アイテムは「個別に」割り当てられます。そのため、500,000 のインストゥルメントを [シンボルごとに] 関連付けられたインストゥルメント オブジェクト クラスへのポインターで割り当てる場合、文字列には 'N' バイト [プラス オーバーヘッド] があり、ポインタには 4 バイト [プラス オーバーヘッド] があります。そして含める; すべての商品の 1 分、5 秒、1 秒の価格時系列と、STD コンテナー内のすべての商品の完全な取引履歴。それは大量のメモリであり、非常に大量のオブジェクトです。 割り当てのオーバーヘッドが小さいため、さらに無駄になります。
f) 悪名高いことですが、STD Map & Set は、LowerBound [Less Than Compare] を使用して FIND のすべてのキーをウォークスルーしますが、これは地獄のように遅いものです。
g) 一部の天才は、「いいえ、ソートされていないマップを使用します」と言うかもしれません...そうではありませんが、たとえ使用したとしても、個別に割り当てられた要素で文字列比較を実行しています。
私が C++ で行うことは次のとおりです (例)。
a) 2 つのパーソナリティを持つ「カスタム」インプレース文字列クラス オブジェクトを作成します。a) バイト配列、および b) 整数配列 [モジュラス 4 でネイティブ境界に整列]。b) カスタム マップ & セットを使用します。これは、2x ディメンションに基づくハッシュであり、ノードがフラットな連続メモリ領域に割り当てられています [動的にサイズ変更することができます]。c) 文字列 [in Integer 形式] CPU をパイプライン化するために Integer によってハッシュが行われ、キー比較も同様に行われます。
C++、C、または ASM でのみ実行できるこれらの手法を使用すると、.NET、C#、または Java で実行される同じことのパフォーマンスの少なくとも 4 ～ 5 倍のオーダーがあります。
挿入するキーの数がおおまかにわかっている場合、特定の用途で標準のものよりも効率的な独自の unordered_map 実装を設計するために使用できる手法は何ですか?
(ハッシュ関数の設計に関する 101 は大歓迎です)