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

StackOverflow https://stackoverflow.com/questions/124671

Вопрос

Как мне выбрать случайный элемент из набора?Меня особенно интересует выбор случайного элемента из 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:[элемент -> индекс].

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

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

Это быстрее, чем цикл for-each в принятом ответе:

int index = rand.nextInt(set.size());
Iterator<Object> 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 .)

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

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

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

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

На языке Java:

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

Решение 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]};

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

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

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

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

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

Решение, приведенное выше, говорит о задержке, но не гарантирует равной вероятности выбора каждого индекса.
Если это необходимо учитывать, попробуйте взять пробы из резервуара. 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

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

В псевдокоде -

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

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

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

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

Значок имеет тип set и оператор случайного элемента, унарный "?", поэтому выражение

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

На лиспе

(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.Это значение умножается на длину списка, а затем используется функция ceiling для округления в большую сторону до следующего целого числа.Затем этот индекс извлекается из a.

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

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

Как насчет того, чтобы просто

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

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

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

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

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

Это странно, поскольку очень легко добавить функцию рандомизированного выбора как к хэш-наборам, так и к двоичным наборам.В наборе хэшей, который не должен быть разреженным, вы можете пробовать случайные записи, пока не получите совпадение.Для двоичного дерева вы можете произвольно выбирать между левым или правым поддеревом с шагом не более 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> E getRandomSetElement(Set<E> 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-хэш-таблица плотная).

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

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

Object[] arr = set.toArray();

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

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

    Set<Integer> s = ...
    Iterator<Integer> 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 <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;
}

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

int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top