1

「テープ」と呼ばれるデータ構造にメモリが割り当てられるグラフを生成するツールを実装したいと思います。テープは、それぞれが「ノードID」を保持し、その「親ノード」と「子ノード」にリンクする要素の配列と考えることができます。

私が探しているのは、アレイ内の使用可能なスロットを特定するのが安価で、新しいノードを追加するときに空のスロットをすばやく特定できるアプローチです。

また、動的配列を使用してテープを実装した場合はどうなりますか？アレイのサイズのサイズ変更が必要な状況で、テープ全体を新しく割り当てられたアレイにコピーすることを回避できますか？

ここの誰かが何か考えを持っていますか？

4

1 に答える 1

4

たとえば、数千のノードの前に大きな「テープ」を割り当てたいと思います。

2 つの概念を組み合わせる必要があります。

  • 最初に、最後に使用したエントリをテープに保存します。次に新しいエントリが必要になったときは、最後に使用したエントリの直後にあるエントリを選択してください。
  • 次に、空きリストを保持します。テープ エントリの最初の 4 バイト (64 ビットでは 8 バイト) を、次の空きエントリへのポインタとして使用します。テープの先頭は、最初の空きエントリを指している必要があります。

テープ上のエントリが解放されるたびに、それをフリー リストに追加します。

テープに新しいエントリが必要なときはいつでも:

  • フリー リストに要素があるかどうかを確認します。ある場合は、最初のエントリを取得して空きリストから削除します
  • フリー リストが空の場合は、最後に使用されたエントリを使用し、その直後のエントリを取得します。

これを再割り当てスキームと組み合わせることもできます。この場合、テープの合計割り当てサイズを保持し、最後に使用されたエントリがテープの終わりに達した場合に再割り当てします。

于 2012-05-10T14:15:37.993 に答える