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

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

Вопрос

У меня есть набор объектов в векторе, из которого я хотел бы выбрать случайное подмножество (например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())));
}

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

Это было полезно?

Решение

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

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

Другие советы

@Джонатан,

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

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 книги Джона Бентли Programming Pearls и основано на реализации Кнута.

Редактировать:Я только что увидел еще одно изменение на странице 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 элементы массива..."

Если вы пытаетесь выбрать 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.

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

Он основан на реализации Дерстенфельдом метода перетасовки Фишера-Йейтса.

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

Сколько стоит удаление?Потому что, если для этого потребуется переписать массив в новый фрагмент памяти, то вы выполнили 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) при перетасовке, но никаких коллизий от внутренней проверки while и меньше, чем потенциальная стоимость O (5n), которую может стоить удаление.

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

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

Это это очень похожий вопрос по stackoverflow.

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

  • O (n) решение:Выполните итерацию по вашему списку и скопируйте элемент (или ссылку на него) с вероятностью (#необходимо / # осталось).Пример:если k = 5 и n = 100, то вы берете первый элемент с вероятностью 5/100.Если вы скопируете этот вариант, то выберете следующий с проблемой 4/99;но если вы не выбрали первое, вероятность равна 5/99.
  • O(k log k) или O(k2):Создайте отсортированный список из 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 (k2) или O (k log k) потому что это зависит от того, насколько быстро вы сможете выполнить поиск и вставить в свой контейнер s.Если s - обычный список, то одна из этих операций линейна, и вы получаете k ^ 2.Однако, если вы готовы построить s как сбалансированное двоичное дерево, вы можете использовать время O (k log k).

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

Сол 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, т.е.если gcd(x, n)= 1, и еще один, a, который является "отправной точкой", - тогда ряд:a % n, a + x % n, a +2*x % n, ... a+(k-1)*x%n - последовательность различных чисел (длиной до k<=n).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top