Memilih elemen acak dari suatu set

Bagaimana cara memilih elemen acak dari suatu set? Saya sangat tertarik untuk memilih elemen acak dari HashSet atau LinkedHashSet, di Jawa. Solusi untuk bahasa lain juga diterima.

int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
    if (i == item)
        return obj;
    i++;
}

Tahukah Anda:

Ada metode yang berguna java.util.Collectionsuntuk mengacak seluruh koleksi: Collections.shuffle(List<?>)dan Collections.shuffle(List<?> list, Random rnd).

Solusi cepat untuk Java menggunakan a ArrayListdan HashMap: [elemen -> indeks].

Motivasi: Saya membutuhkan satu set item dengan RandomAccessproperti, terutama untuk memilih item acak dari set (lihat pollRandommetode). Navigasi acak di pohon biner tidak akurat: pohon tidak seimbang sempurna, yang tidak akan mengarah pada distribusi yang seragam.

public class RandomSet<E> extends AbstractSet<E> {

    List<E> dta = new ArrayList<E>();
    Map<E, Integer> idx = new HashMap<E, Integer>();

    public RandomSet() {
    }

    public RandomSet(Collection<E> items) {
        for (E item : items) {
            idx.put(item, dta.size());
            dta.add(item);
        }
    }

    @Override
    public boolean add(E item) {
        if (idx.containsKey(item)) {
            return false;
        }
        idx.put(item, dta.size());
        dta.add(item);
        return true;
    }

    /**
     * Override element at position <code>id</code> with last element.
     * @param id
     */
    public E removeAt(int id) {
        if (id >= dta.size()) {
            return null;
        }
        E res = dta.get(id);
        idx.remove(res);
        E last = dta.remove(dta.size() - 1);
        // skip filling the hole if last is removed
        if (id < dta.size()) {
            idx.put(last, id);
            dta.set(id, last);
        }
        return res;
    }

    @Override
    public boolean remove(Object item) {
        @SuppressWarnings(value = "element-type-mismatch")
        Integer id = idx.get(item);
        if (id == null) {
            return false;
        }
        removeAt(id);
        return true;
    }

    public E get(int i) {
        return dta.get(i);
    }

    public E pollRandom(Random rnd) {
        if (dta.isEmpty()) {
            return null;
        }
        int id = rnd.nextInt(dta.size());
        return removeAt(id);
    }

    @Override
    public int size() {
        return dta.size();
    }

    @Override
    public Iterator<E> iterator() {
        return dta.iterator();
    }
}

Ini lebih cepat daripada untuk-setiap loop dalam jawaban yang diterima:

int index = rand.nextInt(set.size());
Iterator<Object> iter = set.iterator();
for (int i = 0; i < index; i++) {
    iter.next();
}
return iter.next();

Konstruk untuk-setiap panggilan Iterator.hasNext()pada setiap loop, tetapi karena index < set.size(), pemeriksaan itu tidak perlu overhead. Saya melihat peningkatan 10-20% dalam kecepatan, tapi YMMV. (Juga, ini mengkompilasi tanpa harus menambahkan pernyataan pengembalian tambahan.)

Perhatikan bahwa kode ini (dan sebagian besar jawaban lainnya) dapat diterapkan ke Koleksi apa pun, bukan hanya Set. Dalam bentuk metode umum:

public static <E> E choice(Collection<? extends E> coll, Random rand) {
    if (coll.size() == 0) {
        return null; // or throw IAE, if you prefer
    }

    int index = rand.nextInt(coll.size());
    if (coll instanceof List) { // optimization
        return ((List<? extends E>) coll).get(index);
    } else {
        Iterator<? extends E> iter = coll.iterator();
        for (int i = 0; i < index; i++) {
            iter.next();
        }
        return iter.next();
    }
}

Jika Anda ingin melakukannya di Jawa, Anda harus mempertimbangkan menyalin elemen ke beberapa jenis koleksi akses acak (seperti ArrayList). Karena, kecuali set Anda kecil, mengakses elemen yang dipilih akan mahal (O (n) daripada O (1)). [ed: daftar salinan juga O (n)]

Atau, Anda bisa mencari implementasi Set lain yang lebih dekat dengan kebutuhan Anda. The ListOrderedSet dari Commons Koleksi tampak menjanjikan.

Di Jawa 8:

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}

Di Jawa:

Set<Integer> set = new LinkedHashSet<Integer>(3);
set.add(1);
set.add(2);
set.add(3);

Random rand = new Random(System.currentTimeMillis());
int[] setArray = (int[]) set.toArray();
for (int i = 0; i < 10; ++i) {
    System.out.println(setArray[rand.nextInt(set.size())]);
}

List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);

Ini identik dengan jawaban yang diterima (Khoth), tetapi dengan variabel yang tidak perlu sizedan idihapus.

    int random = new Random().nextInt(myhashSet.size());
    for(Object obj : myhashSet) {
        if (random-- == 0) {
            return obj;
        }
    }

Meskipun menghilangkan dua variabel yang disebutkan di atas, solusi di atas masih tetap acak karena kami mengandalkan acak (mulai dari indeks yang dipilih secara acak) untuk mengurangi sendiri ke 0atas setiap iterasi.

Solusi clojure:

(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))

Perl 5

@hash_keys = (keys %hash);
$rand = int(rand(@hash_keys));
print $hash{$hash_keys[$rand]};

Inilah salah satu cara untuk melakukannya.

C ++. Ini harus cukup cepat, karena tidak memerlukan iterasi pada seluruh set, atau mengurutkannya. Ini harus bekerja di luar kotak dengan kebanyakan kompiler modern, dengan asumsi mereka mendukung tr1 . Jika tidak, Anda mungkin perlu menggunakan Boost.

Dokumen Boost sangat membantu di sini untuk menjelaskan hal ini, bahkan jika Anda tidak menggunakan Boost.

Caranya adalah dengan memanfaatkan fakta bahwa data telah dibagi ke dalam ember, dan untuk dengan cepat mengidentifikasi ember yang dipilih secara acak (dengan probabilitas yang sesuai).

//#include <boost/unordered_set.hpp>  
//using namespace boost;
#include <tr1/unordered_set>
using namespace std::tr1;
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;

int main() {
  unordered_set<int> u;
  u.max_load_factor(40);
  for (int i=0; i<40; i++) {
    u.insert(i);
    cout << ' ' << i;
  }
  cout << endl;
  cout << "Number of buckets: " << u.bucket_count() << endl;

  for(size_t b=0; b<u.bucket_count(); b++)
    cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl;

  for(size_t i=0; i<20; i++) {
    size_t x = rand() % u.size();
    cout << "we'll quickly get the " << x << "th item in the unordered set. ";
    size_t b;
    for(b=0; b<u.bucket_count(); b++) {
      if(x < u.bucket_size(b)) {
        break;
      } else
        x -= u.bucket_size(b);
    }
    cout << "it'll be in the " << b << "th bucket at offset " << x << ". ";
    unordered_set<int>::const_local_iterator l = u.begin(b);
    while(x>0) {
      l++;
      assert(l!=u.end(b));
      x--;
    }
    cout << "random item is " << *l << ". ";
    cout << endl;
  }
}

Solusi di atas berbicara dalam hal latensi tetapi tidak menjamin probabilitas yang sama dari setiap indeks yang dipilih.
Jika itu perlu dipertimbangkan, coba sampling reservoir. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (seperti yang disarankan oleh beberapa orang) menggunakan satu algoritma seperti itu.

Karena Anda mengatakan "Solusi untuk bahasa lain juga diterima", inilah versi untuk Python:

>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4

Tidak bisakah Anda mendapatkan ukuran / panjang dari himpunan / array, menghasilkan angka acak antara 0 dan ukuran / panjang, kemudian memanggil elemen yang indeksnya cocok dengan angka itu? HashSet memiliki metode .size (), saya cukup yakin.

Dalam psuedocode -

function randFromSet(target){
 var targetLength:uint = target.length()
 var randomIndex:uint = random(0,targetLength);
 return target[randomIndex];
}

PHP, dengan asumsi "set" adalah array:

$foo = array("alpha", "bravo", "charlie");
$index = array_rand($foo);
$val = $foo[$index];

Fungsi Mersenne Twister lebih baik tetapi tidak ada MT yang setara dengan array_rand di PHP.

Ikon memiliki tipe dan operator elemen acak, unary "?", Begitu ekspresi

? set( [1, 2, 3, 4, 5] )

akan menghasilkan angka acak antara 1 dan 5.

Benih acak diinisialisasi ke 0 ketika program dijalankan, sehingga menghasilkan hasil yang berbeda pada setiap penggunaan run randomize()

Dalam C #

        Random random = new Random((int)DateTime.Now.Ticks);

        OrderedDictionary od = new OrderedDictionary();

        od.Add("abc", 1);
        od.Add("def", 2);
        od.Add("ghi", 3);
        od.Add("jkl", 4);


        int randomIndex = random.Next(od.Count);

        Console.WriteLine(od[randomIndex]);

        // Can access via index or key value:
        Console.WriteLine(od[1]);
        Console.WriteLine(od["def"]);

Solusi Javascript;)

function choose (set) {
    return set[Math.floor(Math.random() * set.length)];
}

var set  = [1, 2, 3, 4], rand = choose (set);

Atau sebagai alternatif:

Array.prototype.choose = function () {
    return this[Math.floor(Math.random() * this.length)];
};

[1, 2, 3, 4].choose();

Dalam lisp

(defun pick-random (set)
       (nth (random (length set)) set))

Dalam Mathematica:

a = {1, 2, 3, 4, 5}

a[[ ⌈ Length[a] Random[] ⌉ ]]

Atau, dalam versi terbaru, cukup:

RandomChoice[a]

Ini menerima suara turun, mungkin karena kurang penjelasan, jadi di sini adalah:

Random[]menghasilkan float pseudorandom antara 0 dan 1. Ini dikalikan dengan panjang daftar dan kemudian fungsi plafon digunakan untuk membulatkan ke bilangan bulat berikutnya. Indeks ini kemudian diekstraksi dari a.

Karena fungsi tabel hash sering dilakukan dengan aturan dalam Mathematica, dan aturan disimpan dalam daftar, orang mungkin menggunakan:

a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};

Bagaimana kalau saja

public static <A> A getRandomElement(Collection<A> c, Random r) {
  return new ArrayList<A>(c).get(r.nextInt(c.size()));
}

Untuk bersenang-senang saya menulis RandomHashSet berdasarkan sampel penolakan. Agak gila, karena HashMap tidak membiarkan kami mengakses tabelnya secara langsung, tetapi seharusnya berfungsi dengan baik.

Itu tidak menggunakan memori tambahan, dan waktu pencarian adalah O (1) diamortisasi. (Karena java HashTable padat).

class RandomHashSet<V> extends AbstractSet<V> {
    private Map<Object,V> map = new HashMap<>();
    public boolean add(V v) {
        return map.put(new WrapKey<V>(v),v) == null;
    }
    @Override
    public Iterator<V> iterator() {
        return new Iterator<V>() {
            RandKey key = new RandKey();
            @Override public boolean hasNext() {
                return true;
            }
            @Override public V next() {
                while (true) {
                    key.next();
                    V v = map.get(key);
                    if (v != null)
                        return v;
                }
            }
            @Override public void remove() {
                throw new NotImplementedException();
            }
        };
    }
    @Override
    public int size() {
        return map.size();
    }
    static class WrapKey<V> {
        private V v;
        WrapKey(V v) {
            this.v = v;
        }
        @Override public int hashCode() {
            return v.hashCode();
        }
        @Override public boolean equals(Object o) {
            if (o instanceof RandKey)
                return true;
            return v.equals(o);
        }
    }
    static class RandKey {
        private Random rand = new Random();
        int key = rand.nextInt();
        public void next() {
            key = rand.nextInt();
        }
        @Override public int hashCode() {
            return key;
        }
        @Override public boolean equals(Object o) {
            return true;
        }
    }
}

Yang termudah dengan Java 8 adalah:

outbound.stream().skip(n % outbound.size()).findFirst().get()

dimana ninteger acak. Tentu saja kinerjanya kurang dari itu denganfor(elem: Col)

Dengan Guava kita bisa melakukan sedikit lebih baik daripada jawaban Khoth:

public static E random(Set<E> set) {
  int index = random.nextInt(set.size();
  if (set instanceof ImmutableSet) {
    // ImmutableSet.asList() is O(1), as is .get() on the returned list
    return set.asList().get(index);
  }
  return Iterables.get(set, index);
}

PHP, menggunakan MT:

$items_array = array("alpha", "bravo", "charlie");
$last_pos = count($items_array) - 1;
$random_pos = mt_rand(0, $last_pos);
$random_item = $items_array[$random_pos];

Anda juga dapat mentransfer set ke array menggunakan array itu mungkin akan bekerja pada skala kecil saya melihat untuk loop di jawaban yang paling banyak dipilih adalah O (n) tetap

Object[] arr = set.toArray();

int v = (int) arr[rnd.nextInt(arr.length)];

Jika Anda benar-benar hanya ingin memilih objek "apa saja" dari Set, tanpa jaminan keacakan, yang paling mudah adalah mengambil yang pertama dikembalikan oleh iterator.

    Set<Integer> s = ...
    Iterator<Integer> it = s.iterator();
    if(it.hasNext()){
        Integer i = it.next();
        // i is a "random" object from set
    }

Solusi umum menggunakan jawaban Khoth sebagai titik awal.

/**
 * @param set a Set in which to look for a random element
 * @param <T> generic type of the Set elements
 * @return a random element in the Set or null if the set is empty
 */
public <T> T randomElement(Set<T> set) {
    int size = set.size();
    int item = random.nextInt(size);
    int i = 0;
    for (T obj : set) {
        if (i == item) {
            return obj;
        }
        i++;
    }
    return null;
}

Sayangnya, ini tidak dapat dilakukan secara efisien (lebih baik daripada O (n)) di salah satu wadah Perpustakaan Standar.

Ini aneh, karena sangat mudah untuk menambahkan fungsi pilih acak ke hash set dan juga set biner. Dalam set hash tidak jarang, Anda dapat mencoba entri acak, hingga Anda mendapatkan hit. Untuk pohon biner, Anda dapat memilih secara acak antara subtree kiri atau kanan, dengan maksimum O (log2) langkah. Saya sudah mengimplementasikan demo nanti di bawah ini:

import random

class Node:
    def __init__(self, object):
        self.object = object
        self.value = hash(object)
        self.size = 1
        self.a = self.b = None

class RandomSet:
    def __init__(self):
        self.top = None

    def add(self, object):
        """ Add any hashable object to the set.
            Notice: In this simple implementation you shouldn't add two
                    identical items. """
        new = Node(object)
        if not self.top: self.top = new
        else: self._recursiveAdd(self.top, new)
    def _recursiveAdd(self, top, new):
        top.size += 1
        if new.value < top.value:
            if not top.a: top.a = new
            else: self._recursiveAdd(top.a, new)
        else:
            if not top.b: top.b = new
            else: self._recursiveAdd(top.b, new)

    def pickRandom(self):
        """ Pick a random item in O(log2) time.
            Does a maximum of O(log2) calls to random as well. """
        return self._recursivePickRandom(self.top)
    def _recursivePickRandom(self, top):
        r = random.randrange(top.size)
        if r == 0: return top.object
        elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a)
        return self._recursivePickRandom(top.b)

if __name__ == '__main__':
    s = RandomSet()
    for i in [5,3,7,1,4,6,9,2,8,0]:
        s.add(i)

    dists = [0]*10
    for i in xrange(10000):
        dists[s.pickRandom()] += 1
    print dists

Saya mendapat [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] sebagai output, sehingga distribusinya bagus.

Saya telah berjuang dengan masalah yang sama untuk diri saya sendiri, dan saya belum memutuskan apakah kenaikan kinerja dari pick yang lebih efisien ini sepadan dengan biaya menggunakan koleksi berbasis python. Tentu saja saya bisa memperbaikinya dan menerjemahkannya ke C, tapi itu terlalu banyak bekerja untuk saya hari ini :)