使用可能なノードのコレクションを独自の構造に保持することで、ストレージ アロケーターへの多くの呼び出しを回避できます。
この考え方は、二分探索木のデータ構造に適用できます。
著者は次のように述べています。「ノードを一度にすべて割り当てると、ツリーに必要なスペースが大幅に削減され、実行時間が約 3 分の 1 に短縮されます。」
このトリックがスペース要件をどのように削減できるのか、私は興味があります。つまり、4 つのノードを持つ二分探索木を構築したい場合、ノードを 1 つずつ割り当てても、一度に割り当てても、これら 4 つのノードにメモリを割り当てる必要があります。
メモリ アロケーターは、非常に小さなオブジェクトの割り当てが苦手なことで知られています。過去 10 年間で状況はいくらか改善されましたが、この本のトリックは今でも有効です。
ほとんどのアロケータは、メモリを適切に解放できるように、割り当てたブロックに追加情報を保持します。たとえば、C のmalloc/ペアfreeまたはC++ のnew[]/delete[]ペアは、実際のメモリ チャンクの長さに関する情報をどこかに保存する必要があります。通常、このデータはアドレスが返される直前の 4 バイトに収まります。
これは、割り当てごとに少なくとも 4 バイトが無駄になることを意味します。ツリー ノードが 12 バイト (2 つのポインターのそれぞれに 4 バイトと数値に 4 バイトを加えたもの) を必要とする場合、各ノードに 16 バイトが割り当てられ、33.3% 増加します。
メモリ アロケータは、追加のブックキーピングも実行する必要があります。チャンクがヒープから取得されるたびに、アロケーターはそれを考慮する必要があります。
最後に、ツリーが使用するメモリが多いほど、現在のノードが処理されるときに隣接するノードがキャッシュにフェッチされる可能性が低くなります。これは、次のノードまでのメモリ内の距離のためです。
この種の文字列は、Javaによる文字列の処理方法に関連しています。一方、文字列に連結する場合、実際には3つの文字列オブジェクトを使用しています。古い文字列、新しいセグメント、新しい結果です。最終的にガベージコレクターは片付けられますが、この状況（私の文字列の例と手続き型のバイナリ検索）では、無駄な方法でメモリスペースを増やしています。少なくともそれは私がそれを理解する方法です。