Ardışık koleksiyondan rastgele bir öğe alın

Question

Koleksiyona bir java.util.Iterator veren bir API ile konuşuyorum. Bu, üzerinde yineleyebileceğim, ancak öğelere doğrudan/rasgele erişemediğim anlamına gelir.

Şimdi benim sorunum için: Bu koleksiyondan rastgele bir öğe almak istiyorum. Bunu nasıl yaparım? Sanırım doğrudan erişime izin veren yeni bir koleksiyon oluşturabilirim, ama bu küçük bir bellek tüketmiyor mu? Ayrıca, bu öğeyi alıp yinelemeyi bırakıp devam ettirmeme gerek olup olmadığını görmek için tüm koleksiyonun üzerinde ve her öğenin "bir zar atması" için yineleyebilirim. Ama sonra koleksiyonun büyüklüğüne ihtiyacım var ve bunu yineleyiciden alamıyorum.

Şimdiden teşekkürler.

Answer 1

söz zar yöntemini bunu yapmanın bir yolu var kullanmalıdır Çok fazla bellek kullanmayan koleksiyondan tek geçişte (sadece koleksiyonun bir unsuru ve bir floatın boyutu). Pseudocode içinde:

• Koleksiyonda yineleyin.
• Her öğe için rasgele bir kayan nokta oluşturun.
• Şamandıra şimdiye kadar gördüğünüz en düşük (veya en yüksek, önemli değil) ise, geçerli öğeyi koleksiyondan geçici bir değişkende saklayın. (Ayrıca yeni en düşük rasgele değeri de saklayın.)
• Koleksiyonun sonuna ulaştığınızda, geçici değişkende rastgele bir öğeniz var.

Açıkçası bu, her arama yaptığınızda tüm koleksiyonda yineleme sakıncasına sahiptir, ancak karşılaştığınız kısıtlamalarla çok fazla seçeneğiniz yoktur.

Güncelleme: Bu tür bir sorunun adı nihayet geldi bana. Buna Reservoir sampling denir.

Answer 2

Yineleme sırasında, kaç nesnenin geçtiğini bilirsiniz, bu nedenle geçerli öğenin rastgele seçim yapma olasılığı olduğunu bilirsiniz. Yani sadece bir sayı ve mevcut rastgele seçilmiş öğeyi tutmak gerekir.

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; 
} 

(yığın taşması Yasal Uyarı: derlenmiş değil ve kesinlikle test edilmemiş.)

da yaklaşık Collections.shuffle Java puzzlers bölümüne bakın. Iterator bir List oluşturun ve rastgele eleman almak:

Answer 3

tek güvenli çözüm (durumunda başka bilgiler garanti/bilinir) tarif ettiğin yoludur.

Temeldeki koleksiyonun boyutu her zaman aynıysa, bu işlemi ortalamada bir buçuk oranında azaltabilirsiniz - yalnızca Iterator.next() öğesinden sonra aldığınız öğeyi rastgele bir sayıda yineleme sonrasında kullanabilirsiniz.

BTW: Gerçekten, java.util.Iterator'u uygulayan bir Koleksiyon kullanıyor musunuz?

koleksiyonun boyutu o zaman bu yapacak çok büyük değilse O gereksinimlerine bağlıdır

Answer 4

, aksi takdirde sen yineleme ve

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

Answer 5

Eğer gerçekten herhangi rastgele erişimi olmayan ve çok büyük bir listesi varsa o zaman kopyalamak edememesi için aşağıdakileri yapabilirsiniz:

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; 

Bu rastgele bir eleman koruyacaktır bir liste, ancak tüm listeyi geçmenizi gerektirir. Gerçekten eşit dağıtılmış bir değer istiyorsanız, bunu yapmak için başka seçeneğiniz yoktur. öğelerin sayısı küçükse (diğer bir deyişle bir rasgele sırada listedeki tüm unsurlarını erişmek istediğiniz) bilinmeyen boyutta bir listenin rasgele kararak istiyorsanız

Alternatif veya sonra ben tavsiye Tüm referansları yeni bir listeye kopyalamak (sadece referansları depoladığınızdan bu yana milyonlarca öğeye sahip değilseniz, önemli miktarda bellek olmaz). Sonra ya rasgele bir tam sayı ile kullanın ya da listeye izin vermek için standart java.util.Collections shuffle yöntemini kullanın.

Answer 6

Ağırlıklı test verileri oluşturmak için kullanılır. verimli değil ama kolay

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 + "]"; 
    } 

} 

çıkarıldı NOT:

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()); 
    } 

}