Выбор случайного элемента из набора

Как выбрать случайный элемент из набора? Я особенно заинтересован в выборе случайного элемента из HashSet или LinkedHashSet в Java. Решения для других языков также приветствуются.

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

Несколько связанных Знаете ли вы:

В java.util.Collections есть полезные методы для перетасовки целых коллекций: Collections.shuffle(List) И Collections.shuffle(List list, Random rnd) .

Быстрое решение для Java с использованием ArrayList и HashMap : [element -> index].

Мотивация: мне нужен набор элементов со свойствами RandomAccess , особенно для выбора случайного элемента из набора (см. Метод pollRandom ). Случайная навигация в двоичном дереве неточна: деревья не идеально сбалансированы, что не приведет к равномерному распределению.

 public class RandomSet extends AbstractSet { List dta = new ArrayList(); Map idx = new HashMap(); public RandomSet() { } public RandomSet(Collection 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 id 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 iterator() { return dta.iterator(); } } 

Это быстрее, чем для каждого цикла в принятом ответе:

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

Конструкция for-each вызывает Iterator.hasNext() для каждого цикла, но поскольку index < set.size() , эта проверка лишних накладных расходов. Я видел повышение скорости на 10-20%, но YMMV. (Кроме того, это компиляция без необходимости добавления дополнительного оператора return).

Обратите внимание, что этот код (и большинство других ответов) может применяться к любой коллекции, а не только к набору. В форме общего метода:

 public static  E choice(Collection 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) coll).get(index); } else { Iterator iter = coll.iterator(); for (int i = 0; i < index; i++) { iter.next(); } return iter.next(); } } 

Если вы хотите сделать это на Java, вам следует рассмотреть возможность копирования элементов в какую-то коллекцию произвольного доступа (например, ArrayList). Поскольку, если ваш набор невелик, доступ к выбранному элементу будет дорогим (O (n) вместо O (1)). [ed: копия списка также O (n)]

Кроме того, вы можете искать другую реализацию Set, которая более точно соответствует вашим требованиям. Список ListOrderedSet из Коллекций Commons выглядит многообещающим.

В Java:

 Set set = new LinkedHashSet(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); 

Решение Clojure:

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

Не можете ли вы просто получить размер / длину массива set / array, создать случайное число между 0 и размером / длиной, а затем вызвать элемент, индекс которого соответствует этому числу? У HashSet есть метод .size (), я уверен.

В psuedocode –

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

Perl 5

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

Вот один из способов сделать это.

C ++. Это должно быть достаточно быстро, так как оно не требует повторения по всему набору или его сортировки. Это должно работать из коробки с большинством современных компиляторов, предполагая, что они поддерживают tr1 . Если нет, вам может понадобиться использовать Boost.

Документы Boost полезны здесь, чтобы объяснить это, даже если вы не используете Boost.

Хитрость заключается в том, чтобы использовать тот факт, что данные были разделены на ведра и быстро идентифицировать случайно выбранный ковш (с соответствующей вероятностью).

 //#include  //using namespace boost; #include  using namespace std::tr1; #include  #include  #include  using namespace std; int main() { unordered_set 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::const_local_iterator l = u.begin(b); while(x>0) { l++; assert(l!=u.end(b)); x--; } cout << "random item is " << *l << ". "; cout << endl; } } 

В приведенном выше решении говорится о задержке, но не гарантирует равную вероятность выбора каждого выбранного индекса.
Если это необходимо учитывать, попробуйте отбор проб коллектора. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (как это предлагается несколькими) использует один такой алгоритм.

Поскольку вы сказали: «Решения для других языков также приветствуются», вот версия для Python:

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

PHP, предполагая, что «set» – это массив:

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

Функции Mersenne Twister лучше, но в PHP нет MT-эквивалента array_rand.

Значок имеет тип набора и оператор случайного элемента, унарный «?», Поэтому выражение

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

будет производить случайное число от 1 до 5.

Случайное семя инициализируется до 0 при запуске программы, поэтому для получения разных результатов в каждом прогоне используйте randomize()

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

Javascript решение;)

 function choose (set) { return set[Math.floor(Math.random() * set.length)]; } var set = [1, 2, 3, 4], rand = choose (set); 

Или, альтернативно:

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

В lisp

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

В Mathematica:

 a = {1, 2, 3, 4, 5} a[[ ⌈ Length[a] Random[] ⌉ ]] 

Или, в последних версиях, просто:

 RandomChoice[a] 

Это получило проголосовавший голос, возможно, потому, что ему не хватает объяснений, так что вот один из них:

Random[] генерирует псевдослучайное поплавок между 0 и 1. Это умножается на длину списка, а затем функция потолка используется для округления до следующего целого числа. Затем этот индекс извлекается из a .

Поскольку функции хеш-таблицы часто выполняются с помощью правил в Mathematica, а правила хранятся в списках, можно использовать:

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

Это идентично принятому ответу (Khoth), но с ненужными size и i переменными удалены.

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

Хотя устранение двух вышеупомянутых переменных, вышеупомянутое решение по-прежнему остается случайным, потому что мы полагаемся на случайное (начиная с случайно выбранного индекса), чтобы уменьшаться до 0 на каждой итерации.

К сожалению, это невозможно сделать эффективно (лучше, чем O (n)) в любом из контейнеров стандартной библиотеки.

Это странно, так как очень легко добавить рандомизированную функцию выбора в hash-множества, а также в бинарные множества. Если вы не используете редкий хеш-набор, вы можете попробовать случайные записи, пока не получите хит. Для двоичного дерева вы можете выбирать случайным образом между левым или правым поддеревом с максимальным шагом O (log2). Я реализовал демо ниже:

 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 

Я получил [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] в качестве выхода, поэтому распределительные швы хороши.

Я боролся с той же проблемой для себя, и я еще не решил, что увеличение производительности этого более эффективного выбора стоит накладных расходов на использование коллекции на основе python. Я мог бы, конечно, усовершенствовать его и перевести на C, но это слишком много для меня сегодня 🙂

В Java 8:

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

PHP, используя 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]; 

Для удовольствия я написал RandomHashSet, основанный на выборке отбраковки. Это немного взломанно, так как HashMap не позволяет нам напрямую обращаться к его таблице, но он должен работать нормально.

Он не использует дополнительной памяти, а время поиска O (1) амортизируется. (Потому что java HashTable плотен).

 class RandomHashSet extends AbstractSet { private Map map = new HashMap<>(); public boolean add(V v) { return map.put(new WrapKey(v),v) == null; } @Override public Iterator iterator() { return new Iterator() { 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 { 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; } } } 

вы также можете перенести набор в массив использования массива, он, вероятно, будет работать в малом масштабе, я вижу, что цикл for в самом голосованном ответе – O (n) в любом случае

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

Если вы действительно хотите выбрать «любой» объект из Set , без каких-либо гарантий по случайности, проще всего взять первый, возвращенный iteratorом.

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

Самый простой с Java 8:

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

где n – случайное целое число. Конечно, он имеет меньшую производительность, чем при использовании for(elem: Col)

Общее решение с использованием ответа Хота в качестве отправной точки.

 /** * @param set a Set in which to look for a random element * @param  generic type of the Set elements * @return a random element in the Set or null if the set is empty */ public  T randomElement(Set 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; } 

Если заданный размер невелик, то с помощью массивов это можно сделать.

 int random; HashSet someSet; [] randData; random = new Random(System.currentTimeMillis).nextInt(someSet.size()); randData = someSet.toArray();  sResult = randData[random]; 
  • У boost есть тип данных для заданных операций, который проще, чем STL?
  • Как обновить существующий элемент std :: set?
  • Сети не работают в свойствах зависимостей?
  • Когда использовать обратный вызов React setState
  • ReactJS: Warning: setState (...): невозможно обновить во время существующего перехода состояния
  • Interesting Posts

    Есть ли комбинация клавиш для «отмены выбора» в проводнике Windows?

    Как определить размер сектора на внешнем жестком диске?

    Стационарные индексы не поддерживаются в C #?

    Как установить максимальное использование памяти для JVM?

    У общих методов в .NET не может быть указан их возвращаемый тип. Зачем?

    Длина строки без использования метода length ()

    Простой, простой в использовании кеш LRU в java

    Как создать внешний диск в качестве внутреннего диска?

    Моделирование сетевого соединения с низкой пропускной способностью и высокой задержкой в ​​Linux

    Как Facebook Sharer выбирает Изображения и другие метаданные при совместном использовании моего URL?

    Gnuplot: как загрузить и отобразить одно числовое значение из файла данных

    Как загрузить файл с помощью VBA (без Internet Explorer)

    Я регулярно вижу gstatic.com в строке состояния, что это за домен?

    Пересылка Ipv6 6in4

    Есть ли недостатки в создании кода в Userforms вместо модhive?

    Давайте будем гением компьютера.