3

ここでの最初の投稿で、私は初心者です-自分が役に立てば幸いです...

私が求めている仕事をする ADT/概念を見つけて理解しようとしています。私はそれがすでにそこにあると推測しています。

オブジェクトの配列/リスト/ツリー (コンテナーは決定する必要があります) があり、それぞれがプロセスの反復で使用されていない量に関連付けられたカウントを持っています。反復が進むにつれて、各オブジェクトのカウントが 1 ずつ累積されます。アイデアは、遅かれ早かれ未使用のオブジェクトが使用しているメモリが必要になるので、それらを削除して RAM にないオブジェクト用のスペースを作ることです (の初期カウントは「0」になります) - ただし、まだメモリ内にあるオブジェクトを使用していることが判明した場合、そのカウントは「0」にリセットされます。その内容のディスク。

キャッシュ？

メイン プロセス ループには、次のようなものが含まれます。

if (object needs to be added && (totalNumberOfObjects > someConstant))
    object with highest count deleted from RAM and the (heap??)
    newObject added with a count of '0'

if (an object already in RAM is accessed by the process)
    accessedObject count is set to '0'

for (All objects in RAM) 
    count++

私は（長くてバグのある時間）バタバタして自分の混乱を構築することができましたが、単語から最も効率的な方法を学ぶのは興味深いと思いました。

山積みみたいなもの？

4

1 に答える 1

2

これにはヒープを使用できますが、やり過ぎだと思います。カウントに多くの異なる値を持たないように思えますが、各カウントには多くのオブジェクトがあります。そうであれば、オブジェクトを同じ数のオブジェクトのリストにスレッド化するだけで済みます。これらのリストは、それ自体がデキュー (または C++ が呼び出すことを主張する場合は「デキュー」) に配置されます。

ここで重要なのは、すべてのオブジェクトのカウントをインクリメントする必要があることです。おそらく、O(N) ではなく、可能であれば O(1) にする必要があります。可能です: 重要なのは、各リストのヘッダーに、そのカウントと次に小さいカウントの差も含まれていることです。最小カウントのリストのヘッダーには、最小カウントである 0 からの差分が含まれています。すべてのオブジェクトの数を増やすには、この 1 つの数値を 1 だけ増やす必要があります。

オブジェクトのカウントを 0 に設定するには、そのリストからオブジェクトを削除し (つまり、常にリスト イテレータによってオブジェクトを参照する必要があるか、独自の侵入型リンク リストを実装する必要があります)、(1) に追加します。リストのカウントが 0 の場合は一番下のリスト、または (2) そのオブジェクトのみを含むカウントが 0 の新しい一番下のリストを作成します。

新しいオブジェクトを作成する手順は同じですが、現在のリストからリンクを解除する必要はありません。

メモリからオブジェクトを削除するには、一番上のリスト (カウントが最大のリスト) の先頭にあるオブジェクトを選択します。そのリストが空になると、デキューからポップします。さらにメモリが必要な場合は、この操作を繰り返すことができます。

したがって、「すべてのカウントをインクリメントする」を含むすべての操作は O(1) です。残念ながら、ストレージのオーバーヘッドは、オブジェクトごとに 2 つのポインターと、一意のカウントごとに 2 つのポインターと 1 つの整数です (最悪の場合、これはオブジェクトの数と同じですが、実際にははるかに少ないと思われます)。1 つ未満のポインターと各オブジェクトのカウントを使用する他のアルゴリズムを想像するのは難しいため、これはおそらく空間と時間のトレードオフでさえありません。追加のスペース要件は最小限です。

于 2012-12-07T05:53:31.567 に答える