Блог

У меня есть список, связанный в одном направлении, без знания его размера.

Я хочу получить случайный элемент в этом списке, и у меня есть только один разовый шанс просмотреть список. (Мне не разрешено проходить дважды или более)

Каков алгоритм решения этой проблемы? Спасибо!

Это просто выборка из резервуара с резервуаром размером 1.

По сути, это действительно просто

1. Выберите первый элемент независимо (для списка длиной 1 первый элемент всегда является образцом).
2. Для каждого другого элемента с вероятностью 1 / n, где n — количество элементов, наблюдаемых на данный момент, вы заменяете уже выбранный элемент текущим элементом, на котором вы находитесь.

Выборка выполняется равномерно, поскольку вероятность выбора любого элемента в конце дня равна 1 / n (упражнение для читателя).

Вероятно, это вопрос из интервью.Сбор выборки из резервуара используется data scientist для хранения соответствующих данных в ограниченном хранилище из большого потока данных.

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

1) Сохраните первые k элементов в хранилище. 2) Когда следующий элемент (k 1) поступает из потока, очевидно, что у вас больше нет места в вашей коллекции.Сгенерируйте случайное число от o до n, если сгенерированное случайное число меньше k, предположим, l, замените storage[l] элементом (k 1) из stream.

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

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

В википедии есть понятный алгоритм, который я цитирую ниже:

 array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k 1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done
  

Для вопроса требуется только 1 значение, поэтому мы принимаем k = 1.

Реализация на C :

https://ideone.com/txnsas

Это самый простой способ, который я нашел, он отлично работает и понятен:

 public int findrandom(Node start) {
    Node curr = start;
    int count = 1, result = 0, probability;
    Random rand = new Random();

    while (curr != null) {
        probability = rand.nextInt(count)   1;
        if (count == probability)
            result = curr.data;
        count  ;
        curr = curr.next;
    }
    return resu<
}