Wybór losowego elementu z zestawu

Jak wybrać losowy element z zestawu? Szczególnie interesuje mnie wybranie losowego elementu z HashSet lub LinkedHashSet w Javie. Mile widziane są również rozwiązania dla innych języków.

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

Nieco pokrewne Czy wiesz, że:

Istnieją przydatne metody java.util.Collectionstasowania całych kolekcji: Collections.shuffle(List<?>)i Collections.shuffle(List<?> list, Random rnd).

Szybkie rozwiązanie dla języka Java za pomocą znaków ArrayListi HashMap: [element -> indeks].

Motywacja: potrzebowałem zestawu przedmiotów z RandomAccesswłaściwościami, zwłaszcza aby wybrać losowy przedmiot z zestawu (patrz pollRandommetoda). Losowa nawigacja w drzewie binarnym nie jest dokładna: drzewa nie są idealnie zrównoważone, co nie prowadziłoby do równomiernego rozmieszczenia.

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

Jest to szybsze niż pętla for-each w akceptowanej odpowiedzi:

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

Konstrukcja for-each wywołuje Iterator.hasNext()każdą pętlę, ale ponieważ index < set.size()to sprawdzenie jest niepotrzebnym narzutem. Widziałem wzrost prędkości o 10-20%, ale YMMV. (Ponadto kompiluje się bez konieczności dodawania dodatkowej instrukcji return).

Zwróć uwagę, że ten kod (i większość innych odpowiedzi) można zastosować do dowolnej kolekcji, a nie tylko do zestawu. W ogólnej formie metody:

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

Jeśli chcesz to zrobić w Javie, powinieneś rozważyć skopiowanie elementów do jakiejś kolekcji o swobodnym dostępie (takiej jak ArrayList). Ponieważ, chyba że twój zestaw jest mały, dostęp do wybranego elementu będzie kosztowny (O (n) zamiast O (1)). [ed: kopia listy jest również O (n)]

Alternatywnie możesz poszukać innej implementacji zestawu, która bardziej odpowiada Twoim wymaganiom. Zestaw ListOrderedSet z Commons Collections wygląda obiecująco.

W Javie 8:

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

W Javie:

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

Jest to identyczne z zaakceptowaną odpowiedzią (Khoth), ale z niepotrzebną sizei usuniętymi i zmiennymi.

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

Pomimo rezygnacji z dwóch wyżej wymienionych zmiennych, powyższe rozwiązanie nadal pozostaje przypadkowe, ponieważ polegamy na losowym (zaczynającym się od losowo wybranym indeksie), aby zmniejszyć się w kierunku 0każdej iteracji.

Rozwiązanie 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]};

Oto jeden sposób, aby to zrobić.

C ++. Powinno to być dość szybkie, ponieważ nie wymaga iterowania po całym zestawie ani sortowania go. Powinno to działać po wyjęciu z pudełka z większością nowoczesnych kompilatorów, zakładając, że obsługują one tr1 . Jeśli nie, może być konieczne użycie funkcji Boost.

Dokumentacja Boost są tutaj pomocne, aby to wyjaśnić, nawet jeśli nie używasz Boost.

Sztuczka polega na wykorzystaniu faktu, że dane zostały podzielone na kosze i szybko zidentyfikować losowo wybrany kosz (z odpowiednim prawdopodobieństwem).

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

Powyższe rozwiązanie mówi w kategoriach opóźnienia, ale nie gwarantuje równego prawdopodobieństwa wybrania każdego indeksu.
Jeśli trzeba to wziąć pod uwagę, spróbuj pobrać próbki ze zbiornika. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (jak sugeruje niewielu) używa jednego z takich algorytmów.

Ponieważ powiedziałeś „Mile widziane są również rozwiązania dla innych języków”, oto wersja dla Pythona:

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

Nie możesz po prostu uzyskać rozmiaru / długości zestawu / tablicy, wygenerować losową liczbę od 0 do rozmiaru / długości, a następnie wywołać element, którego indeks pasuje do tej liczby? HashSet ma metodę .size (), jestem prawie pewien.

W psuedokodzie -

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

PHP, zakładając, że „zestaw” jest tablicą:

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

Funkcje Mersenne Twister są lepsze, ale w PHP nie ma odpowiednika MT dla array_rand.

Ikona ma ustawiony typ i operator elementu losowego, jednoargumentowy „?”, Czyli wyrażenie

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

wygeneruje losową liczbę od 1 do 5.

Losowe ziarno jest inicjowane na 0, gdy program jest uruchamiany, aby uzyskać różne wyniki przy każdym uruchomieniu randomize()

W 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"]);

Rozwiązanie Javascript;)

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

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

Lub alternatywnie:

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

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

W seplenieniu

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

W Mathematica:

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

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

Lub, w najnowszych wersjach, po prostu:

RandomChoice[a]

Ta otrzymała głos negatywny, być może dlatego, że brakuje jej wyjaśnienia, więc oto jedno:

Random[]generuje pseudolosową liczbę zmiennoprzecinkową z przedziału od 0 do 1. Jest to mnożone przez długość listy, a następnie funkcja sufitu jest używana do zaokrąglania w górę do następnej liczby całkowitej. Ten indeks jest następnie wyodrębniany z a.

Ponieważ funkcja tablicy skrótów jest często wykonywana za pomocą reguł w Mathematica, a reguły są przechowywane na listach, można użyć:

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

Może po prostu

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

Dla zabawy napisałem RandomHashSet na podstawie próbkowania odrzucania. To trochę hacky, ponieważ HashMap nie pozwala nam uzyskać bezpośredniego dostępu do jego tabeli, ale powinno działać dobrze.

Nie używa dodatkowej pamięci, a czas wyszukiwania jest amortyzowany O (1). (Ponieważ java HashTable jest gęsty).

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

Najłatwiejszy z Javą 8 to:

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

gdzie njest losową liczbą całkowitą. Oczywiście ma mniejszą wydajność niż w przypadkufor(elem: Col)

Z guawą możemy zrobić trochę lepiej niż odpowiedź Khotha:

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, używając 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];

możesz również przenieść zestaw do tablicy użyj tablicy to prawdopodobnie zadziała na małą skalę Widzę pętlę for w najczęściej głosowanej odpowiedzi i tak O (n)

Object[] arr = set.toArray();

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

Jeśli naprawdę chcesz po prostu wybrać „dowolny” obiekt z elementu Set, bez żadnych gwarancji co do losowości, najłatwiej jest wziąć pierwszy zwrócony przez iterator.

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

Ogólne rozwiązanie wykorzystujące odpowiedź Khotha jako punkt wyjścia.

/**
 * @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;
}

Niestety, nie można tego zrobić wydajnie (lepiej niż O (n)) w żadnym z kontenerów zestawu biblioteki standardowej.

Jest to dziwne, ponieważ bardzo łatwo jest dodać losową funkcję wybierania zarówno do zestawów haszujących, jak i binarnych. W niezbyt rzadkim zestawie skrótów możesz próbować losowych wpisów, aż uzyskasz trafienie. W przypadku drzewa binarnego można losowo wybierać między lewym lub prawym poddrzewem, z maksymalną liczbą O (log2) kroków. Zaimplementowałem demo poniżej:

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

Otrzymałem [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] jako wyjście, więc rozkład wydaje się dobry.

Sam zmagałem się z tym samym problemem i nie zdecydowałem jeszcze, czy wzrost wydajności tego bardziej wydajnego wyboru jest wart kosztów narzutów związanych z używaniem kolekcji opartej na Pythonie. Mógłbym to oczywiście udoskonalić i przetłumaczyć na C, ale to dla mnie dziś za dużo pracy :)