Я хочу реализовать равномерно случайный доступ к определенной коллекции с N числами, так как каждый элемент в коллекции будет доступен с одинаковой вероятностью 1/N. Я поместил все элементы в измененный двойной связанный список. затем циклически сдвигайте его со случайным временем, удаляйте последний элемент, а затем добавляйте его как первый. наконец, выберите первый элемент. Я использовал его, чтобы проверить, сколько вызовов потребуется, чтобы охватить весь элемент, не удаляя элемент из списка. Общее необходимое количество мин постоянно на единицу меньше, чем ожидалось. Хотите знать, действительно ли реализация равномерно случайна? как вы думаете, моя реализация действительно случайна? Я отлаживал это в течение довольно долгого времени, но до сих пор не понял.
public Item callout(){
for (int j=0; j<StdRandom.uniform(N); j++)
{
this.addFirst(this.removeLast());
// circular shift the queue by StdRandom.uniform(N)times, always return the first item;
}
return first.item;
}
public void addFirst(Item item){
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.previous = null;
if (last == null)
{last = first; first.next = null;} //if it's the first element added. if last.next = null == last = null;!!!!
else
{
first.next = oldfirst;
oldfirst.previous = first;
}
N++;
}
public Item removeLast(){
if (last == null) throw new RuntimeException();
Item item = last.item;
// if right now only one element exists in the container
if (first == last)
{
first=null;
last=null;
}
else{
last =last.previous;
last.next = null;
// old first becomes first; optional operation, easy way to tell if it's the header.
}
N--;
return item;
}
Следующий класс вычисляет количество вызовов, необходимых для достижения всеобъемлющего вызова, он получает RandomCollection с n элементами в нем. По сути, это коллекция с целыми числами от 1 до N, я использую массив флагов int [] для пометки, если элемент ранее вызывался.
private static int getNumberOfCallsForComprehensiveCallout(RandomCollection<Integer> test, int n){
// create an array of the same number of items in collection, each with a Flag indicating whether it has beeen called
int calltimes =0; // calltimes stands for the numofcalls needed to reach a comprehensive call
int flag = 1; // flag used to indicate if this item has been called
int [] c = new int [n];
Arrays.fill(c, flag);
int NumberOfFlags = n;
while(NumberOfFlags != 0){
int numbercalled = test.callout();
if (c[numbercalled-1]==1) {NumberOfFlags--; c[numbercalled-1]=0;}
else; // indicate this item has been called earlier.
calltimes++;
// System.out.println(calltimes);
}
return calltimes; // return the number of calls for comprehensive callout each time this method is called.
}
StdRandom.uniform(N)
. Обратите внимание, что «настоящего случайного» действительно добиться трудно; Когда люди говорят о «генераторах случайных чисел» (ГСЧ), они часто имеют в виду псевдо генераторы случайных чисел (ГСЧ). Хороший PRNG кажется случайным, но его последовательность полностью определяется начальным начальным значением. Это полностью зависит от предполагаемого использования, является ли «случайный» достаточно случайным. Вам могут быть интересны «крепкие» тесты на случайность, если вы хотите знать, насколько случайным является ваш код. - person pauluss86   schedule 10.02.2014