1

次の要件を持つコレクションが必要です（それが重要な場合はObjective Cで）：

  1. 一定時間挿入
  2. 一定時間の削除
  3. 要素数を取得する
  4. 定数時間ランダム要素を取得

ハッシュ セットは機能しますが、NSMutableSet クラスは抽象的です。NSMutableSet クラスがどのように記述されているかはわかりませんが、動的に拡大/縮小するハッシュ セットが適していると考えました。これは、負荷率の範囲が保証されているため、バケットをランダムに選択することでランダム要素機能を実装できるためです。空でないバケットが見つかるまでバケットを反復処理し、そのバケットからランダムな要素を選択します。これは、ランダムな要素を一定時間選択できるので素晴らしいことですが、車輪の再発明はしたくありません。誰かが私に指摘する提案やライブラリを持っていますか?

前もって感謝します。

4

2 に答える 2

1

私は最近、同じ問題に出くわしました。ここに私が思いついたものがあります

#include <unordered_set>
#include <iostream>

using namespace std;

int main() {

unordered_set<int> u;
int ins = 0;
for (int i=0; i<30; i++) {   // something to fill the test set
    ins += i;
    ins %= 73;
    u.insert(ins);
}
cout << "total number of buckets: " << u.bucket_count() << endl;
for(size_t b=0; b<u.bucket_count(); b++)      //showing how the set looks like
    if (u.bucket_size(b)) {
        cout << "Bucket " << b << " contains: ";
        unordered_set<int>::local_iterator lit;
        for (lit = u.begin(b);  lit != u.end(b);) {
            cout << *lit;
            if (++lit != u.end(b))
                cout << ", ";
        }
        cout << endl;
    }
cout << endl;

int r = rand() % u.bucket_count();

while (u.bucket_size(r) == 0)         // finding nonempty bucket 
    r = (r + 1) % u.bucket_count();   // modulo is here to prevent overflow

unordered_set<int>::local_iterator lit = u.begin(r);

if (u.bucket_size(r) > 1) {              // if bucket has more elements then
    int r2 = rand() % u.bucket_size(r);  // pick randomly from them
    for (int i = 0; i < r2; i++)
        lit++;
}
cout << "Randomly picked element is " << *lit << endl;
cin.ignore();

return 0;
}

再ハッシュの問題については、次のとおりです。

  1. セットが成長している場合、要素/バケットの比率が 1 より大きくなると、デフォルトで再ハッシュされます。したがって、私のソリューションはここでは安全です。

  2. ただし、セットが大きくなり、その後急速に縮小する場合は、セットが空になるまで再ハッシュしないため、チェックを実行して最終的に再ハッシュすることをお勧めします。

    if (u.load_factor() < 0.1) u.rehash(u.size());

これは、セットが少なくとも 10% 使用されているかどうかをチェックし、そうでない場合は再ハッシュして、セットのサイズが現在の要素数を格納するのに適切になるようにします。(通常、新しいサイズは、サイズよりも小さい 2 のべき乗に等しくなります)

于 2013-09-26T21:07:16.110 に答える
0

あなたconstantは実際には であるため、独自のB-treelog nをロールアップすることをお勧めします。次に、次のようになります。

- (id)randomObject {
    Your_Branch_Type* branch = your_root;
    NSUInteger randomIndex = RANDOM_INTEGER_UP_TO(count);
    while (!branch.final)
        if (branch.left.count >= randomIndex) {
            branch = branch.left; 
        } else {
            branch = branch.right;
        }
    return branch.object;
}
于 2013-09-27T10:54:51.150 に答える