1

整数のプールを管理するのに役立つデータ構造を探しています。プールから整数をしばらく削除してから、再び使用されることを期待して元に戻すという点で、これはプールです。ただし、他にもいくつかの奇妙な制約があるため、通常のプールはうまく機能しません。

ハード要件:

  • 使用中の最大の整数への一定時間アクセス。
  • 整数のまばらさを制限する必要があります (原則としてのみであっても)。
    整数を互いに近づけて、範囲内の未使用の整数を最小限に抑えてすばやく反復できるようにします。

データ構造の選択に役立つ場合はこれらを使用し、そうでない場合は無視します。

  • プール内の整数は 0 ベースで連続しています。
  • プールは一定のサイズにすることができます。
  • プールからの整数は、解約率の高い短期間のみ使用されます。

私は実用的な解決策を持っていますが、それはエレガントではありません。
私の（準最適）ソリューション

一定サイズのプール。
利用可能なすべての整数をソート済みセット (free_set) に入れます。
新しい整数が要求されると、free_set から最小のものを取得します。
使用中のすべての整数を別のソート済みセット (used_set) に入れます。
最大が要求されると、used_set から最大のものを取得します。

私の特定のソリューションに役立つ可能性のある最適化がいくつかあります（優先キュー、メモ化など）。しかし、私のアプローチ全体が無駄に思えます。

私の問題に完全に適合する難解なデータ構造があることを願っています。または、少なくともより優れたプーリング アルゴリズム。

4

2 に答える 2

0

バランスの取れた二分探索木を使用しないのはなぜですか? min 要素へのポインター/イテレーターを格納して無料でアクセスできます。挿入/削除後の更新は O(1) 操作です。自己均衡ツリーを使用する場合、挿入/削除は O(log(n)) です。詳しく説明するには:

insert : 新しい要素を以前の最小要素と比較するだけです。より良い場合は、イテレータが新しい分を指すようにします。

delete : min が削除された場合は、削除する前に後継者を見つけ (イテレータを 1 ステップ進めるだけで実行できます)、その人を新しい min にします。

理論的には、洗練された超ヒープ データ構造 (つまり、フィボナッチ ヒープ) を使用してわずかに改善することは可能ですが、実際には、わずかなログ ファクターを節約するためだけにそのような実装を行いたいとは思わないでしょう。また、おまけとして、高速な順序トラバーサルを無料で利用できます。言うまでもなく、最近のほとんどのプログラミング言語には、箱から出してすぐに使用できるセルフバランシング バイナリ検索ツリー (赤黒木/avl など) の高速な実装が付属しています。 .)。

^ javascript を除いて :P

編集：さらに良い答えを考えました。

于 2012-04-18T19:37:21.897 に答える
0

疑似クラス:

class IntegerPool {

  int size = 0;
  Set<int> free_set = new Set<int>();

  public int Acquire() {
    if(!free_set.IsEmpty()) {
      return free_set.RemoveSmallest();
    } else {
      return size++;
    }
  }

  public void Release(int i) {
    if(i == size - 1) {
      size--;
    } else {
      free_set.Add(i);
    }
  }

  public int GetLargestUsedInteger() {
    return size;
  }
}

編集

RemoveSmallestまったく役に立ちません。RemoveWhatever十分です。したがって、より高速な代替手段 (または ) としてSet<int>置き換えることができます。LinkedList<int>Stack<int>

于 2012-04-18T16:11:04.430 に答える