1

私はC＃を使用していますが、それを知らなくても、この質問を理解するのは非常に簡単です。

これが私の問題です。IDに基づいて検索できるように、ハッシュセットのようなデータ構造に保持したいオブジェクトがいくつかありintます。これらのオブジェクトには変更可能なプロパティがあるため、ハッシュすることはできません（ハッシュするには、オブジェクトについて一定の定数が必要ですよね？）。

私がやったことは、次のインターフェースを開発することです。

public interface IUniqueIDCollection
{
    // Can return any int that hasn't been requested yet.
    public int RequestUniqueID();

    // Undos the requesting of an int
    public int ReleaseUniqueID(int uniqueID);
}

IUniqueIDCollection私の最初の考えは、IDが要求されると増分する内部カウンターを格納することです。ただし、IDがリリースされたら、削除された範囲または個々のIDを追跡する必要があります。後者の方がいいと思います。しかし、カウンター（または任意の循環関数）を使用してIDを生成すると、カウンターがラップアラウンドすると解放されないことによって連続して要求されたIDのシーケンスをチェックする必要があるという問題が発生します。

ヒューリスティックは次のとおりです。一度に最大5,000個のIDが要求されるとします。ただし、多くの場合、IDが要求されてからリリースされます。リリースは範囲内で発生する傾向があります。つまり、100個すべてが一度に要求され、その後100個すべてが短い時間間隔でリリースされる可能性があります。

intの代わりにGUIDなどを使用できることはわかっていますが、IDのスペース/帯域幅/処理時間を節約したいと思います。

だから私の質問は：ヒューリスティックを考えると、疑似コードの観点から、上記のインターフェースでリクエストとリリースのメソッドはどのように見えるべきですか？

4

2 に答える 2

5

リリースされたIDが安全にすぐに再利用できると確信している場合（つまり、新しいオブジェクトに最近リリースされたIDが割り当てられた場合に混乱する、古いIDへの古い参照がぶら下がることはありません）、 IDを最初にリリースしました。したがって、IDが解放されると、それをキューの最後に配置します。新しいIDが要求されると、キューの最初のIDを使用します。キューが空の場合は、内部カウンターをインクリメントして新しい番号を出します。

この実装の利点：

  • すべての操作はO（1）です。コレクションや範囲を反復処理することはありません。キューの最後に挿入するか、キューの先頭から削除するか、カウンターをインクリメントするだけです。
  • キューをできるだけ早く使い果たしようとしているため、メモリフットプリントはかなり低くする必要があります。
  • 実装は簡単です。

短所：

  • IDをすばやく再利用するため、インデックス範囲全体を使用して、新しいオブジェクトが最近リリースされたオブジェクトと同じIDを使用しないようにする必要はありません。
  • IDを見ても、オブジェクトの年齢を推測することはできません。
于 2012-09-06T17:36:57.057 に答える
1

ほとんどすべての場合、上記のTom Panningよりも悪い考えですが、BitArrayを使用して、使用中のIDを追跡することができます。メモリ使用量は、ライブIDの合計と同じ数のビットです。最悪の場合は、すべての32ビットintをマッピングするために512MBになります。解放は簡単です。対応するビットを0に設定するだけです。IDを取得（または要求）するには、0ビットを検索し、見つからない場合はBitArrayを拡張する必要があります。

BitArrayを拡張するオプションがまだある場合（つまり、まだ512MBになっていない場合）、拡張を決定する前にすべてのBitArrayを検索したくない場合があります。これを行うと、常に時間がかかります。確かに、常に同じインデックスから始めたいとは限りません。最後に見つけた0を追跡し、そこから検索を開始することをお勧めします。

私が見ることができる1つの利点は、すべてまたはほとんどすべてのオブジェクトが解放された後のメモリ使用量です。次に、Tom Panningのソリューションには、これの少なくとも32倍のメモリが必要です。ただし、通常の使用法では、そのソリューションの使用量は少ないと思います。

于 2012-09-06T18:40:48.257 に答える