интервалы отбора проб, а не числа, без замены

Question

рода проблемы, я имею дело с включает в себя несколько вещей, а именно:

1. Мне нужно, чтобы случайно выборки чисел из диапазона чисел.
2. Этот диапазон чисел действительно огромный, от 1 до 1 000 000 000.
3. Мне нужен процесс выборки, чтобы избежать выборки из интервалов в пределах диапазона, который уже был выбран. Поскольку использование массива слишком медленное, мои попытки использовать splice не собираются работать.

Начну с выбора номера от 1 до 1 000 000 000.

my $random = int(rand(1_000_000_000)) + 1; 

добавить значение, скажем, 100, к тому, чтобы сделать $random и $random + 100 определить интервал.

my $interval = $random + 100; 

Тогда я push как $random и $interval в другой массив. Этот другой массив должен хранить интервалы.

push (@rememberOldIntervals, $random, $interval); 

я шаг через массив @rememberOldIntervals используя for петли, потянув элементы в паре. Первая из пары - прежняя $random, а другая - $interval. Внутри этого цикла for я делаю еще одно случайное число. Но сгенерированное число не может быть между уже выполненным интервалом. Если да, держите выборку до тех пор, пока не будет найдено число, которое является уникальным. Кроме того, это новое случайное число должно быть не менее 100 от любого старого интервала.

for (my $i= 0; $i < (scalar @rememberOldIntervals)/2 ; $i=+2) { 
     $random = int(rand(1_000_000_000)) + 1; 
     my $new_random_low = $random - 100; 
     my $new_random_high = $random + 100; 

     if ($new_random_low <= $rememberOldIntervals[0] OR 
      $new_random_high >= $rememberOldIntervals[1] ){ 

      push(@rememberOldIntervals, $new_random_low, $new_random_high); 
     } 

     else { 
      until ($new_random_low <= $rememberOldIntervals[0] OR 
        $new_random_high >= $rememberOldIntervals[1] ) { 

        $random = int(rand(1_000_000_000)) + 1; 
        my $new_random_low = $random - 100; 
        my $new_random_high = $random + 100; 
      } 
     } 

} 

Этот последний цикл должен быть встроен в другой, чтобы водить его много раз, скажем, 10 000 раз.

Answer 1

Эта проблема может быть в вытягивать станут ассоциироваться 10000 случайных чисел от 0 до 1 млрд, где число не находится в пределах 100 другого.

Brute Force - 5 сек

Потому что вы только потянув 10000 номеров, и, вероятно, не нужно делать это очень часто, я предлагаю приближается к такого рода проблемы с использованием грубой силы на начальном этапе. Это пытается следовать шаблону проектирования Premature optimization is the root of all evil

В этом случае это означает просто потянуть случайные числа и сравнить их со всеми ранее выведенными числами.Это будет иметь скорость O(N^2), но также будет меньше кода.

use strict; 
use warnings; 

my $max = 1_000_000_000; 
my $dist = 100; 
my $count = 10_000; 

die "Too many numbers" if 2 * $dist * $count >= $max; 

my @numbers; 

while (@numbers < $count) { 
    my $num = int rand $max; 
    push @numbers, $num if ! grep {abs($num - $_) < $dist} @numbers; 
} 

print scalar(@numbers), "\n"; 

Выход занимает 5 секунд:

10000 

бинарный поиск для быстрого поколения - 0,14 ИКС

Теперь для более быстрого алгоритма, я согласен с ysth, что гораздо более эффективный метод для решения этой проблемы необходимо создать два списка ваших случайных чисел. Один из них - это бегущий список, а другой сортируется. Используйте отсортированный список, чтобы выполнить двойной поиск места размещения, а затем сравните его с соседними элементами, чтобы узнать, находится ли он в пределах 100.

Это уменьшает количество сравнений от O(N^2) до O(N log N). Следующее занимает всего 0,14 секунды для запуска в сравнении с 5 секундами метода грубой силы.

use strict; 
use warnings; 

my $max = 1_000_000_000; 
my $dist = 100; 
my $count = 10_000; 

die "Too many numbers" if 2 * $dist * $count >= $max; 

my @numbers; 
my @sorted = (-$dist, $max); # Include edges to simplify binary search logic. 

while (@numbers < $count) { 
    my $num = int rand $max; 

    # Binary Search of Sorted list. 
    my $binary_min = 0; 
    my $binary_max = $#sorted; 
    while ($binary_max > $binary_min) { 
     my $average = int(($binary_max + $binary_min)/2); 
     $binary_max = $average if $sorted[$average] >= $num; 
     $binary_min = $average + 1 if $sorted[$average] <= $num; 
    } 

    if (! grep {abs($num - $_) < $dist} @sorted[$binary_max, $binary_max - 1]) { 
     splice @sorted, $binary_max, 0, $num; 
     push @numbers, $num; 
    } 
} 

print scalar(@numbers), "\n"; 

Хэш дробей для быстрых - 0,05 сек

Я спросил в комментариях: "могли бы упростить эту задачу, чтобы выбрать случайное кратное 100, которая не будет гарантировать отсутствие дублирования, и тогда вам просто нужно выбрать случайное число от 1 до 10 миллионов без повторения, а затем просто умножить его на 100. «Вы не ответили, но мы все еще можем использовать группировку по кратным 100, чтобы упростить эту проблему ,

В принципе, если мы отслеживаем частное число, деленное на 100, нам нужно только его сравнить его с числами с частными и минус-единицами. Это уменьшает число сравнений для O(N), что не удивительно, является самым быстрым на 0,05 секунды:

use strict; 
use warnings; 

my $max = 1_000_000_000; 
my $dist = 100; 
my $count = 10_000; 

die "Too many numbers" if 2 * $dist * $count >= $max; 

my @numbers; 
my %num_per_quot; 

while (@numbers < $count) { 
    my $num = int rand $max; 

    my $quotient = int $num/$dist; 

    if (! grep {defined && abs($num - $_) < $dist} map {$num_per_quot{$quotient + $_}} (-1, 0, 1)) { 
     push @numbers, $num; 
     $num_per_quot{$quotient} = $num; 
    } 
} 

print scalar(@numbers), "\n"; 

Внимание, если вы на Windows,

Если запустить этот код на Windows, и используя версию perl меньше, чем v5.20, вам нужно использовать более качественное генерирование случайных чисел, чем встроенный rand. По причинам, пожалуйста, прочитайте avoid using rand if it matters.

Я использовал Math::Random::MT qw(rand); в этом коде, так как я на Strawberry Perl v5.18.2. Однако, начиная с Perl v5.20, это больше не будет проблемой, потому что rand now uses a consistent random number generator.

Answer 2

Вы можете ускорить его, используя хеши и индексы.

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

my $interval = 100; 
my $space = 1e9; 
my $interval_count = 1e4; 
my @values; 
my %index_taken; 
for(1..$interval_count) 
{ 
    my $index; 
    $index while $index_taken{$index = int rand $space/2/$interval }++; 
    my $start = $index*2*$interval + 1 + int rand $interval; 
    push @values, $start, $start+$interval; 
} 

Это гарантирует неперекрывающиеся интервалы, но между двумя интервалами будет недоступно пространство до 200.

Или, если вы хотите интервалы отсортированные:

@values = map {$_*=2*$interval; $_+=1+int rand $interval; ($_,$_+$interval)} 
    sort keys %index_taken;