シーケンシャルコレクションからランダムな要素を取得する

Question

私はコレクションにjava.util.IteratorというAPIを付けます。それは私がそれを反復することができますが、私は要素に直接/ランダムアクセスを取得することはできません。

私の問題は次のとおりです。このコレクションからランダムな要素を1つ取得したいと考えています。それ、どうやったら出来るの？私は直接アクセスできる新しいコレクションを作ることができたと思いますが、少しメモリを消費するのではないですか？私はコレクション全体を反復することもできますし、各要素の "ロールス・オブ・サイコロ"を使ってその要素を取り、反復をやめるか続行するかを確認することもできます。しかし、私はコレクションのサイズが必要です、そして、私はIteratorからそれを得ることができません。

ありがとうございます。

Answer 1

を述べたサイコロメソッドを使用する必要があり、要件によって異なります余分なメモリ（コレクションの1つの要素の大きさとフロートの大きさだけ）を使用しないコレクションを1回通過したときに発生します。疑似コード：

• コレクションを繰り返します。
• 各項目について、ランダムフロートを生成します。
• これまでに見たフロートが一番低い（またはそれほど重要ではない）場合は、コレクションの現在のアイテムを一時変数に格納します。
• コレクションの最後に到達すると、temp変数にランダムな項目があります。

明らかに、これにはコールするたびにコレクション全体を反復するという欠点がありますが、直面している制約を多く選択する必要はありません。

更新：最終的にこのタイプの問題の名前が戻ってきました。これはReservoir samplingと呼ばれます。

Answer 2

反復処理を行うと、反復処理したオブジェクトの数がわかるので、現在の要素がランダムに選択される確率を知ることができます。したがって、カウントと現在のランダムに選択された項目を保持するだけで済みます。

public static <T> T selectRandom(final Iterator<T> iter, final Random random) { 
    if (!iter.hasNext()) { 
     throw new IllegalArgumentException(); 
    } 
    if (random == null) { 
     throw new NullPointerException(); 
    } 
    T selected = iter.next(); 
    int count = 1; 
    while (iter.hasNext()) { 
     final T current = iter.next(); 
     ++count; 
     if (random.nextInt(count) == 0) { 
      selected = current; 
     } 
    } 
    return selected; 
} 

（スタックオーバーフロー免責事項：コンパイルされていない、と確かにテストされていない）

また、JavaのpuzzlersでCollections.shuffleに関するセクションを参照してください。 がIteratorからListを作成し、ランダムな要素を選ぶ：

Answer 3

唯一の安全な解決策は、（場合にはそれ以上の情報は保証/知られていない）あなたが説明した方法です。

基礎となるコレクションのサイズが常に同じ場合は、平均で半分の労力を削減できます。反復の乱数の後にIterator.next（）の後にある要素を使用するだけです。

BTW：実際にはjava.util.Iteratorを実装するコレクションを使用していますか？

Answer 4

コレクションのサイズが、これはそれを行うだろう巨大でない場合、それがそうでなければ、あなたがそれを行う方法があります反復処理し、あなたが

List<Object> list = Arrays.asList(yourCollection.toArray(new Object[0])); 
result = list.get(new Random().nextInt(list.size())); 

Answer 5

あなたが本当に任意のランダムアクセスを持っていない、とあなたは次の操作を行うことができ、それをコピーすることはできませんので、あなたは非常に大規模なリストを持っている場合：

int n = 2 
iterator i = ... 
Random rand = new Random(); 
Object candidate = i.next(); 
while (i.hasNext()) { 
    if (rand.nextInt(n)) { 
     candidate = i.next(); 
    } else { 
     i.next(); 
    } 
    n++; 
} 
return candidate; 

これは、からランダムな要素を保持しますリストは必要ですが、リスト全体をトラバースする必要があります。真に均等に分散した価値を望むなら、あなたはこれをする以外に選択肢がありません。

また、アイテムの数が少ない場合、または不明なサイズのリストのランダムな並べ替えを必要とする場合（つまり、ランダムな順序でリストのすべての要素にアクセスする場合）は、すべての参照を新しいリストにコピーします（参照を格納するだけなので、何百万ものアイテムを持たない限り、これは大量のメモリではありません）。次に、getをランダムな整数で使用するか、標準のjava.util.Collectionsシャッフルメソッドを使用してリストを並べ替えます。

Answer 6

重み付けテストデータを生成するために使用します。それは効率的ではないですが、

class ProbabilitySet<E> { 

    Set<Option<E>> options = new HashSet<Option<E>>(); 

    class Option<E> { 
     E object; 
     double min; 
     double max; 

     private Option(E object, double prob) { 
      this.object = object; 
      min = totalProb; 
      max = totalProb + prob; 
     } 

     @Override 
     public String toString() { 
      return "Option [object=" + object + ", min=" + min + ", max=" + max + "]"; 
     } 
    } 

    double totalProb = 0; 
    Random rnd = new Random(); 

    public void add(E object, double probability){ 
     Option<E> tuple = new Option<E>(object, probability); 
     options.add(tuple); 
     totalProb += probability; 
    } 

    public E getRandomElement(){ 

     double no = rnd.nextDouble() * totalProb; 
     for (Option<E> tuple : options) { 
      if (no >= tuple.min && no < tuple.max){ 
       return tuple.object; 
      } 
     } 


     return null; // if this happens sumfink is wrong. 

    } 

    @Override 
    public String toString() { 
     return "ProbabilitySet [options=" + options + ", totalProb=" + totalProb + "]"; 
    } 

} 

簡単です注：確率パラメータはありません1.0

使い方に合計に対する次のようになります。

public static void main(String[] args) { 
    ProbabilitySet<String> stati = new ProbabilitySet<String>(); 
    stati.add("TIMEOUT", 0.2); 
    stati.add("FAILED", 0.2); 
    stati.add("SUCCESSFUL", 1.0); 

    for (int i = 0; i < 100; i++) { 
     System.out.println(stati.getRandomElement()); 
    } 

}