2

イテレータにのみアクセスできる要素をm含むマップから要素を削除できる必要があります。n簡単に言えば、辞書を1回繰り返して、すべての要素を確率m/nで削除することもできますが、これにより、アイテムよりも多かれ少なかれ削除される可能性がありmます（ただし、削除されるアイテムの予想数は正しくありますm）。

int m = 10;
int n = map.size();

Iterator<K> keys = map.keySet().iterator();
while (keys.hasNext()) {
    keys.next();
    if (random.nextDouble() < m / (double) n) {
        keys.remove();
    }
}

私が考えていた解決策は、要素が削除されたらm要素の削除を停止し、反復の最後に、要素が削除された場合は、2回目の反復でevicted < m残りの要素を削除することです。m - evictedこの2回目のパスが確率的に正しくないのではないかと心配しています。

int m = 10;
int n = size();
int evicted = 0;

outer: while (evicted < m) {

Iterator<K> keys = keySet().iterator();
while (keys.hasNext()) {
    keys.next();
    if (random.nextDouble() < m / (double) n) {
        keys.remove();

        if (++evicted == m) {
            break outer;
        }
    }
}

または、キーのリストを保持し、1回の反復でリストをリザーバーサンプリングし、キーのリスト内のすべてのキーを削除することもできますが、m使用を強制されたくないメモリオーバーヘッドが少しあります。また、イテレータを使用して削除する方が、キーで要素を削除するよりも高速です（キーが格納されているバケットを見つけて、リスト内のその場所を見つける必要があります）。イテレータへのアクセスのみで（個別のリストを作成せずに）使用できる別のオンラインアルゴリズムはありますか？

編集：興味のある人のために、ランダムな分布を順番に生成する方法を詳しく説明した論文を見つけました。これにより、個別の並べ替え手順は必要ありません。コードは次のようなものです（整数に切り捨てられると重複が含まれる場合があります）：

int curmax = 1.0;
int[] indices = new int[m];
for (int i = indices.length; i >= 0; i--) {
    curmax = curmax * Math.pow(random.nextDouble(), 1 / (double) (i+1));
    indices[i] = (int) curmax;
}
4

2 に答える 2

3

最初のM個の要素を削除してからイテレータを停止しないのはなぜですか? 排除された要素に望ましくないバイアスを与えるような順序付けが反復子に反映されていますか?

はいの場合、2 パス アプローチは統計的に完璧ではありません。反復の最後に到達する前にMに到達したために最初のパスが早期に終了した場合、後の要素はエビクションの対象とは見なされませんでした。

M個の要素を削除せずに反復の最後に到達した場合、反復の最初の要素は 2 回削除される危険がありますが、反復の終わりに向かう要素は 1 回だけ削除される危険があります。

Nが事前にわかっている場合は、0 から N までのM個のランダムで繰り返しのない数のリストを作成できます。1 回反復し、反復のどこにいるのかをカウントします。反復番号が「削除リスト」にある場合は、その要素を削除します。

そのアプローチに従って、反復プロセスのために一時的にMインデックス位置 (おそらく整数) にのみメモリを割り当てる必要があります。

于 2012-11-12T00:00:22.893 に答える
1

これを行う正しい方法は、確率 m/n で各要素を削除することですが、結果に応じて確率を再正規化します (要素を削除する場合、m を減分し、現在の確率を選択する残りの要素の数でスケーリングする必要があります)。から）。私のJavaは少しさびていて、コンパイラにアクセスできないので、これがうまくいかない場合はすみません（しかし、あまり手間をかけずに修正できるはずです）：

int seen = 0

Iterator<K> keys = map.keySet().iterator();
while (keys.hasNext()) {
    if (m==0)
      break;

    keys.next();
    prob = m / (double)(n-seen)  //renormalise the prob so that the total available is 1 across all remaining instances
    if (random.nextDouble() < prob) {
        keys.remove();
        m--;
    }
    seen++;
}

ここでの論理が明確であることを願っています---これは、セットから 1 つの要素を確率 1/n でサンプリングする方法の一般化です。要素を拒否したら、それを無視して、残りのすべての要素の分布を考慮することができます。これにより、正確な確率で正確に m 個の要素が返されるようになります。

編集：

いくつかのタイプミスを修正し、冗長な変数を削除しました。

于 2012-11-12T17:11:04.823 に答える