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

180

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

Меньше подсказок
источник
5
Вы должны указать некоторые условия, чтобы увидеть, действительно ли это то, что вы хотите. - Как раз вы будете выбирать случайный элемент? - Должны ли данные быть сохранены в HashSet или LinkedHashSet, ни те, ни другие не доступны в случайном порядке. - Большой ли хеш установлен? Ключи маленькие?
Дэвид Нехм

Ответы:

88
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++;
}
Khoth
источник
94
Если myHashSet велик, то это будет довольно медленное решение, поскольку в среднем потребуется (n / 2) итераций для поиска случайного объекта.
Даниэль
6
если ваши данные находятся в хэш-наборе, вам нужно время O (n). Обойти это невозможно, если вы просто выбираете один элемент, а данные хранятся в HashSet.
Дэвид Неем
8
@David Nehme: это недостаток в спецификации HashSet в Java. В C ++ обычно можно получить прямой доступ к сегментам, которые составляют хэш-набор, что позволяет нам более эффективно выбирать случайные элементы. Если в Java необходимы случайные элементы, возможно, стоит определить пользовательский хэш-набор, который позволит пользователю заглянуть в тайник. См. [Документацию для повышения] [1], чтобы узнать больше об этом. [1] boost.org/doc/libs/1_43_0/doc/html/unordered/buckets.html
Аарон МакДейд,
11
Если набор не видоизменяется при множественном доступе, вы можете скопировать его в массив и получить доступ к O (1). Просто используйте myHashSet.toArray ()
ykaganovich
2
@ykaganovich Разве это не усугубит ситуацию, поскольку набор должен быть скопирован в новый массив? docs.oracle.com/javase/7/docs/api/java/util/… "этот метод должен выделять новый массив, даже если эта коллекция поддерживается массивом"
anton1980
73

В некотором родстве Знаете ли вы:

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

chickeninabiscuit
источник
Потрясающие! Это не перекрестные ссылки нигде в документе Java! Как в Python random.shuffle ()
smci
25
Но это работает только со списками, то есть со структурами, которые имеют функцию .get ().
bourbaki4481472
4
@ bourbaki4481472 абсолютно правильно. Это работает только для тех коллекций, которые расширяют Listинтерфейс, а не Setинтерфейс, обсуждаемый OP.
Томас,
31

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

Мотивация: мне нужен был набор предметов со 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();
    }
}
fandrew
источник
Хорошо, что это сработало бы, но вопрос был об интерфейсе Set. Это решение заставляет пользователей иметь конкретные ссылки на тип RandomSet.
Йохан Тиден
Мне очень нравится это решение, но оно не поточно-ориентированное, возможны неточности между картой и списком, поэтому я бы добавил несколько синхронизированных блоков
Kostas Chalkias
@KonstantinosChalkias встроенные коллекции также не являются потокобезопасными. Только те, у кого есть имя Concurrent, действительно безопасны, а те, что завернуты Collections.synchronized()в полубезопасны Также ОП ничего не сказал о параллелизме, так что это правильный и хороший ответ.
TWiStErRob
Возвращенный здесь итератор не должен иметь возможности удалять элементы dta(например, это может быть достигнуто с помощью guava Iterators.unmodifiableIterator). В противном случае реализации по умолчанию, например, removeAll и retainAll в AbstractSet и его родителях, работающих с этим итератором, могут испортить ваш RandomSet!
muued
Хорошее решение. На самом деле вы можете использовать дерево, если каждый узел содержит количество узлов в поддереве, которое оно коренит. Затем вычислите случайное действительное число в 0..1 и примите взвешенное трехстороннее решение (выберите текущий узел или перейдите в левое или правое поддерево) в каждом узле на основе количества узлов. Но, по-моему, ваше решение намного приятнее.
Джин
30

Это быстрее, чем цикл 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. (Кроме того, это компилируется без добавления дополнительного оператора возврата.)

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

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();
    }
}
Шон Ван Гордер
источник
15

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

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

Дэн Дайер
источник
8
Копирование в список будет стоить O (n) во времени, а также потребует O (n) памяти, так почему это будет лучшим выбором, чем выборка с карты напрямую?
МДМА
12
Это зависит от того, сколько раз вы хотите выбрать из набора. Копирование выполняется один раз, и затем вы можете выбирать из набора столько раз, сколько вам нужно. Если вы выбираете только один элемент, то да, копия не делает вещи быстрее.
Дэн Дайер
Это только одноразовая операция, если вы хотите иметь возможность выбирать с повторением. Если вы хотите, чтобы выбранный элемент был удален из набора, вы вернетесь к O (n).
TurnipEntropy
13

В Java 8:

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}
Джошуа Боун
источник
9

В 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())]);
}
Хорхе Феррейра
источник
11
Ваш ответ работает, но он не очень эффективен из-за части set.toArray ().
Понятия меньше
12
Вы должны переместить массив toArray за пределы цикла.
Дэвид Неем
8
List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);
Бен Ноланд
источник
21
Это ужасно неэффективно. Ваш конструктор ArrayList вызывает .toArray () для предоставленного набора. ToArray (в большинстве, если не во всех стандартных реализациях коллекции) выполняет итерацию по всей коллекции, заполняя массив по мере его поступления. Затем вы перемешиваете список, который заменяет каждый элемент случайным элементом. Вам было бы гораздо лучше просто перебирать множество случайных элементов.
Крис Боде
4

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

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

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

Джейсон Хартли
источник
1
Третья строка также может быть if (--random < 0) {, где randomдостигает -1.
Сальвадор
3

Clojure решение:

(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))
pjb3
источник
1
Это решение также линейно, потому что, чтобы получить nthэлемент, вы также должны пройти через него seq.
Бруно Ким
1
Он также линейный, так как хорошо вписывается в одну строку: D
Кшиштоф Вольни,
2

Perl 5

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

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

JJ
источник
2

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

Документы Boost полезны здесь, чтобы объяснить это, даже если вы не используете 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;
  }
}
Аарон МакДейд
источник
2

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

темпы
источник
1

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

>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4
Swaroop CH
источник
3
Только [1,2,3,4,5,6] - это не набор, а список, поскольку он не поддерживает такие вещи, как быстрый поиск.
Томас Ахл
Вы все еще можете сделать: >>> random.choice (list (set (range (5)))) >>> 4 Не идеально, но это подойдет, если вам абсолютно необходимо.
SapphireSun
1

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

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

function randFromSet(target){
 var targetLength:uint = target.length()
 var randomIndex:uint = random(0,targetLength);
 return target[randomIndex];
}
Мэтт Лохкамп
источник
Это работает, только если рассматриваемый контейнер поддерживает случайный поиск индекса. Многие реализации контейнеров этого не делают (например, хеш-таблицы, двоичные деревья, связанные списки).
Дэвид Хейли
1

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

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

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

dirtside
источник
В большинстве реализаций множеств нет оператора get (i) или индексации, поэтому id предполагает, что OP указал свой набор
DownloadPizza
1

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

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

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

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

Хью Аллен
источник
1

В 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"]);
Митч Пшеничный
источник
Похоже, что они недооценены, потому что дрянной Java-словарь (или так называемый LinkedHashSet, независимо от того, что, черт возьми, это) не может быть "случайным образом доступен" (доступ к которому ключ, я думаю). Ява дерьмо заставляет меня смеяться так много
Федерико Берасатеги
1

Решение 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();
Мэтью Бирн
источник
Я предпочитаю второй вариант. :-)
marcospereira
ох, мне нравится расширять добавление нового метода массива!
Мэтт Лохкамп
1

В лиспе

(defun pick-random (set)
       (nth (random (length set)) set))
inglesp
источник
Это работает только для списков, верно? С ELTним может работать любая последовательность.
Кен,
1

В 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};
Mr.Wizard
источник
1

Как насчет просто

public static <A> A getRandomElement(Collection<A> c, Random r) {
  return new ArrayList<A>(c).get(r.nextInt(c.size()));
}
Даниэль Любаров
источник
1

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

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

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;
        }
    }
}
Томас Але
источник
1
Именно то, что я думал! Лучший ответ!
ммм
На самом деле, возвращаясь к этому, я думаю, что это не совсем равномерно, если в хэш-карте много коллизий, а мы делаем много запросов. Это потому, что в java hashmap используются сегменты / цепочки, и этот код всегда будет возвращать первый элемент в конкретном сегменте. Мы все еще едины в отношении случайности хэш-функции.
Томас Але
1

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

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

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

Нику Марасою
источник
1

С Гуавой мы можем сделать немного лучше, чем ответ Кота:

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);
}
dimo414
источник
0

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];
da5id
источник
0

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

Object[] arr = set.toArray();

int v = (int) arr[rnd.nextInt(arr.length)];
SiVi
источник
0

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

    Set<Integer> s = ...
    Iterator<Integer> it = s.iterator();
    if(it.hasNext()){
        Integer i = it.next();
        // i is a "random" object from set
    }
Philipp
источник
1
Это не будет случайным выбором, хотя. Представьте, что вы выполняете одну и ту же операцию над одним и тем же набором несколько раз. Я думаю, что порядок будет таким же.
Менезес Соуза
0

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

/**
 * @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;
}
stivlo
источник
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, но это слишком много для меня сегодня :)

Томас Але
источник
1
Причина, по которой я думаю, что это не реализовано в бинарном дереве, заключается в том, что такой метод не будет равномерно выбирать элементы. Поскольку они являются узлами без левого / правого дочернего элемента, может возникнуть ситуация, когда левый дочерний элемент содержит больше элементов, чем правый дочерний элемент (или наоборот), что сделает выбор элемента у правого (или левого) дочернего элемента более вероятным.
Виллем Ван Онсем
1
@CommuSoft: Вот почему я храню размер каждого поддерева, так что я могу выбирать свои вероятности, основываясь на них.
Томас Ахл