Подтвердить что ты не робот

Лучший способ выбрать случайный подмножество из коллекции?

У меня есть набор объектов в векторе, из которых я хотел бы выбрать случайное подмножество (например, 100 возвращаемых элементов, случайно выбрать 5). В моем первом (очень поспешном) проходе я сделал чрезвычайно простое и, возможно, слишком умное решение:

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

Хотя у этого есть преимущество быть красивым и простым, я подозреваю, что он не будет масштабироваться очень хорошо, т.е. Collections.shuffle() должен быть O (n) по крайней мере. Моя менее умная альтернатива -

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

Любые предложения по лучшим способам извлечения случайного подмножества из коллекции?

4b9b3361

ОТВЕТЫ

Ответ 1

Джон Бентли обсуждает это в "Программировании жемчуга" или "Больше программирующих жемчужин". Вы должны быть осторожны с процессом выбора N в M, но я думаю, что показанный код работает правильно. Вместо случайного перетасовки всех элементов вы можете выполнить случайную перетасовку, только перетасовывая первые N позиций, что является полезной экономией, когда N < М.

Кнут также обсуждает эти алгоритмы - я считаю, что это будет Vol 3 "Сортировка и поиск", но мой набор упакован в ожидании перемещения дома, поэтому я не могу официально проверить это.

Ответ 2

@Джонатан,

Я считаю, что это решение, о котором вы говорите:

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

Это на стр. 127 программирования Pearls от Jon Bentley и основано на реализации Knuth.

EDIT: я только что увидел дополнительную модификацию на стр. 129:

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

Это основано на идее, что "... нам нужно перетасовать только первые m элементов массива..."

Ответ 3

Я написал эффективную реализацию этого несколько недель назад. Он в С#, но перевод на Java тривиален (по сути, тот же код). Положительная сторона заключается в том, что он также полностью беспристрастен (в некоторых из существующих ответов нет) - способ тестирования, который здесь.

Это основано на реализации Durstenfeld перестановки Fisher-Yates.

Ответ 4

Если вы пытаетесь выбрать k различных элементов из списка n, методы, которые вы указали выше, будут O (n) или O (kn), поскольку удаление элемента из вектора приведет к тому, что arraycopy сдвинет все элементы опущены.

Поскольку вы запрашиваете лучший способ, это зависит от того, что вам разрешено делать с вашим списком входных данных.

Если допустимо изменить список входных данных, как в ваших примерах, вы можете просто поменять k случайных элементов на начало списка и вернуть их в O (k) время следующим образом:

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

Если список должен заканчиваться в том же состоянии, в котором он начался, вы можете отслеживать позиции, которые вы поменяли, а затем вернуть список в исходное состояние после копирования выбранного выбранного объекта. Это все еще решение O (k).

Если, однако, вы вообще не можете изменять список ввода, а k намного меньше n (например, 5 из 100), было бы гораздо лучше не удалять выбранные элементы каждый раз, а просто выбирать каждый элемент, и если вы когда-либо получаете дубликат, бросаете его и повторно выбираете. Это даст вам O (kn/(n-k)), который все еще близок к O (k), когда n доминирует k. (Например, если k меньше n/2, то оно сводится к O (k)).

Если k не доминирует над n, и вы не можете изменить список, вы можете также скопировать исходный список и использовать свое первое решение, потому что O (n) будет таким же хорошим, как O (k).

Как отмечали другие, если вы в зависимости от сильной случайности, где каждый подсчет возможен (и непредвзято), вам определенно нужно что-то более сильное, чем java.util.Random. См. java.security.SecureRandom.

Ответ 5

Второе решение использовать элемент Random to pick кажется звуковым, однако:

Ответ 6

Сколько стоит снять стоимость? Поскольку, если это нужно переписать массив на новый кусок памяти, то вы сделали O (5n) операции во второй версии, а не O (n), которые вы хотели раньше.

Вы можете создать массив логических значений, заданных как false, а затем:

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

Этот подход работает, если ваше подмножество меньше вашего общего размера на значительный запас. Поскольку эти размеры приближаются друг к другу (т.е. 1/4 размера или что-то еще), вы получите больше коллизий на этом генераторе случайных чисел. В этом случае я бы сделал список целых чисел размером вашего более крупного массива, а затем перетасовал этот список целых чисел и вытащил из него первые элементы, чтобы получить ваши (не сталкивающиеся) индексы. Таким образом, у вас есть стоимость O (n) при построении целочисленного массива и еще один O (n) в случайном порядке, но никаких столкновений с внутренним элементом проверки и меньше, чем потенциальный O (5n), который удаляется, может стоить.

Ответ 7

Я бы предпочел бы вашу первоначальную реализацию: очень краток. Тестирование производительности покажет, насколько хорошо оно масштабируется. Я реализовал очень похожий блок кода в прилично злоупотребляемом методе, и он достаточно масштабирован. Конкретный код основывался на массивах, содержащих > 10 000 элементов.

Ответ 8

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

Ответ 9

fooobar.com/questions/13377/...

Подводя итоги моим любимым ответам с этой страницы (скорее всего от пользователя Kyle):

  • O (n) solution: перейдите в свой список и скопируйте элемент (или ссылку на него) с вероятностью (#needed/#remaining). Пример: если k = 5 и n = 100, то вы берете первый элемент с проблемой 5/100. Если вы скопируете это, вы выбираете следующий с помощью проблемы 4/99; но если вы не приняли первый, проблема равна 5/99.
  • O (k log k) или O (k 2): постройте отсортированный список k индексов (числа в {0, 1,..., n -1}) путем случайного выбора числа < n, затем случайным образом выбирает число < n-1 и т.д. На каждом шаге вам нужно отозвать свой выбор, чтобы избежать столкновений и не допускать вероятности. В качестве примера, если k = 5 и n = 100, а ваш первый выбор - 43, ваш следующий выбор находится в диапазоне [0, 98], а если он = 43, вы добавите 1 к нему. Поэтому, если ваш второй вариант равен 50, вы добавляете 1 к нему, и у вас есть {43, 51}. Если ваш следующий выбор - 51, вы добавляете 2 к нему, чтобы получить {43, 51, 53}.

Вот несколько псевдопионов -

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

Я говорю, что временная сложность O (k 2) или O (k log k), потому что это зависит от того, насколько быстро вы можете искать и вставлять ваш контейнер для s. Если s - обычный список, одна из этих операций является линейной, и вы получаете k ^ 2. Однако, если вы хотите построить s как сбалансированное двоичное дерево, вы можете получить время O (k log k).

Ответ 10

два решения, которые я не думаю здесь, - это довольно длинный и содержит некоторые ссылки, однако я не думаю, что все должности связаны с проблемой выбора подстанции K elemetns из набора из N элементов. [Под "множеством" я ссылаюсь на математический термин, т.е. Все элементы появляются один раз, порядок не важен].

Sol 1:

//Assume the set is given as an array:
Object[] set ....;
for(int i=0;i<K; i++){
randomNumber = random() % N;
    print set[randomNumber];
    //swap the chosen element with the last place
    temp = set[randomName];
    set[randomName] = set[N-1];
    set[N-1] = temp;
    //decrease N
    N--;
}

Это похоже на ответ даниэля, но на самом деле это совсем другое. Это время выполнения O (k).

Другим решением является использование некоторой математики: рассмотрим индексы массива как Z_n, и поэтому мы можем произвольно выбрать 2 числа, x, которые являются взаимно простыми с n, т.е. chhose gcd (x, n) = 1, а другое, a, которое является "начальной точкой", - то ряд: a% n, a + x% n, a + 2 * x% n,... a + (k-1) * x% n - последовательность различных чисел (до тех пор, пока k <= n).