Как я могу случайным образом перебирать большой диапазон?

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

1. Определите диапазон от 0 до некоторого числа N
2. Создать случайную начальную точку x[0] внутри N
3. Создать итератор Q менее N
4. Создавайте последовательные точки x[n], добавляя Q к предыдущей точке и при необходимости оборачиваясь. То есть x[n+1] = (x[n] + Q) % N
5. Повторяйте, пока не создадите новую точку, равную начальной точке.

Хитрость заключается в том, чтобы найти итератор, который позволит вам пройти весь диапазон, не генерируя одно и то же значение дважды. Если я правильно помню, любые относительно простые N и Q будут работать (чем ближе число к границам диапазона, тем менее «случайный» ввод). В этом случае должно работать простое число, которое не является множителем N. Вы также можете поменять местами байты/полубайты в результирующем числе, чтобы изменить шаблон, с которым сгенерированные точки «прыгают» в N.

Этот алгоритм требует только сохранения начальной точки (x[0]), текущей точки (x[n]), значения итератора (Q) и предела диапазона (N).

Возможно, кто-то еще помнит этот алгоритм и может проверить, правильно ли я его помню?

Как ответил @Turtle, у вашей проблемы нет решения. Решение @KandadaBoggu и @bta дает вам случайные числа в некоторых диапазонах, которые являются или не являются случайными. Вы получаете кластеры чисел.

Но я не знаю, почему вас волнует двойное появление одного и того же числа. Если (0..99**99) - ваш диапазон, то если бы вы могли генерировать 10^10 случайных чисел в секунду (если у вас процессор 3 ГГц и около 4 ядер, на которых вы генерируете одно случайное число за цикл ЦП - что невозможно, а ruby ​​даже замедлит это значительно меньше), то потребуется около 10^180 лет, чтобы исчерпать все числа. У вас также есть вероятность около 10^-180, что два одинаковых числа будут сгенерированы в течение целого года. В нашей Вселенной, вероятно, около 10 ^ 9 лет, поэтому, если бы ваш компьютер мог начать вычисления, когда началось время, то у вас была бы вероятность около 10 ^ -170, что были сгенерированы два одинаковых числа. Другими словами - практически это невозможно и вам не нужно об этом заботиться.

Даже если вы будете использовать Jaguar (первый из суперкомпьютеров www.top500.org) только для одной этой задачи, вы все еще нужно 10 ^ 174 лет, чтобы получить все числа.

Если ты мне не веришь, попробуй

tried = {} # store previous attempts
bigint = 99**99
bigint.times {
  x = rand(bigint)
  puts "Oh, no!" if tried[x]
  tried[x] = true
}

Я куплю тебе пива, если ты хоть раз увидишь "О, нет!" на вашем экране при жизни :)

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

Даже если вы используете только один бит на значение (было ли это значение опробовано да или нет), вам потребуется X/8 байтов памяти для хранения результата (где X — наибольшее число). Если предположить, что у вас есть 2 ГБ свободной памяти, у вас останется более 16 миллионов номеров.

Разбейте диапазон на управляемые партии, как показано ниже:

def range_walker range, batch_size = 100
  size = (range.end - range.begin) + 1
  n = size/batch_size 
  n.times  do |i|
    x = i * batch_size + range.begin
    y = x + batch_size
    (x...y).sort_by{rand}.each{|z| p z}
  end
  d = (range.end - size%batch_size + 1)
  (d..range.end).sort_by{rand}.each{|z| p z }
end

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

PS: Это хорошая проблема для уменьшения карты. Каждая партия может обрабатываться независимыми узлами.

Ссылка:

Map-reduce в Ruby

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

a = [1,2,3,4,5,6,7,8,9]
a.shuffle!
=> [5, 2, 8, 7, 3, 1, 6, 4, 9]

Вам нужен так называемый "итератор полного цикла"...

Вот псевдокод для самой простой версии, которая идеально подходит для большинства применений...

function fullCycleStep(sample_size, last_value, random_seed = 31337, prime_number = 32452843) {
if last_value = null then last_value = random_seed % sample_size
    return (last_value + prime_number) % sample_size
}

Если вы называете это так:

sample = 10
For i = 1 to sample
    last_value = fullCycleStep(sample, last_value)
    print last_value
next

Он будет генерировать случайные числа, циклически перебирая все 10, никогда не повторяясь. все равно никогда не будет дубликатов.

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

Насколько «случайным» должен быть ваш заказ? Если вам не нужно конкретное распределение ввода, вы можете попробовать рекурсивную схему, подобную этой, чтобы минимизировать использование памяти:

def gen_random_indices
  # Assume your input range is (0..(10**3))
  (0..3).sort_by{rand}.each do |a|
    (0..3).sort_by{rand}.each do |b|
      (0..3).sort_by{rand}.each do |c|
        yield "#{a}#{b}#{c}".to_i
      end
    end
  end
end

gen_random_indices do |idx|
  run_test_with_index(idx)
end

По сути, вы строите индекс, случайным образом генерируя по одной цифре за раз. В худшем случае потребуется достаточно памяти для хранения 10 * (количество цифр). Вы встретите каждое число в диапазоне (0..(10**3)) ровно один раз, но порядок будет псевдослучайным. То есть, если первый цикл устанавливает a=1, то вы столкнетесь со всеми трехзначными числами формы 1xx до того, как увидите изменение разряда сотен.

Другим недостатком является необходимость вручную создавать функцию на заданную глубину. В вашем случае (0..(99**99)) это, вероятно, будет проблемой (хотя я полагаю, вы могли бы написать скрипт для генерации кода для вас). Я уверен, что, вероятно, есть способ переписать это в рекурсивной манере с полным состоянием, но я не могу придумать это в голове (идеи, кто-нибудь?).

[Изменить]: Принимая во внимание ответы @klew и @Turtle, лучшее, на что я могу надеяться, это наборы случайных (или близких к случайным) чисел.

Это рекурсивная реализация чего-то похожего на решение KandadaBoggu. По сути, пространство поиска (как диапазон) разбито на массив, содержащий N диапазонов одинакового размера. Каждый диапазон возвращается в случайном порядке как новое пространство поиска. Это продолжается до тех пор, пока размер диапазона не достигнет нижней границы. На данный момент диапазон достаточно мал, чтобы его можно было преобразовать в массив, перетасовать и проверить.

Несмотря на то, что это рекурсивно, я еще не взорвал стек. Вместо этого возникает ошибка при попытке разбить область поиска, размер которой превышает 10^19 ключей. Я связан с тем, что числа слишком велики, чтобы преобразовать их в long. Вероятно, это можно исправить:

# partition a range into an array of N equal-sized ranges
def partition(range, n)
    ranges = []
    first = range.first
    last = range.last
    length = last - first + 1
    step = length / n # integer division
    ((first + step - 1)..last).step(step) { |i|
        ranges << (first..i)
        first = i + 1
    }
    # append any extra onto the last element
    ranges[-1] = (ranges[-1].first)..last if last > step * ranges.length
    ranges
end

Я надеюсь, что комментарии к коду помогут пролить свет на мой первоначальный вопрос.

pastebin: полный исходный код

Примечание: PW_LEN под # options можно изменить на меньшее число, чтобы получить более быстрые результаты.

Для непомерно большого пространства, например

space = -10..1000000000000000000000

Вы можете добавить этот метод в Range.

class Range

  M127 = 170_141_183_460_469_231_731_687_303_715_884_105_727

  def each_random(seed = 0)
    return to_enum(__method__) { size } unless block_given?
    unless first.kind_of? Integer
      raise TypeError, "can't randomly iterate from #{first.class}"
    end

    sample_size = self.end - first + 1
    sample_size -= 1 if exclude_end?
    j = coprime sample_size
    v = seed % sample_size
    each do
      v = (v + j) % sample_size
      yield first + v
    end
  end

protected

  def gcd(a,b)
    b == 0 ? a : gcd(b, a % b)
  end

  def coprime(a, z = M127)
    gcd(a, z) == 1 ? z : coprime(a, z + 1)
  end

end

Вы могли бы тогда

space.each_random { |i| puts i }

729815750697818944176
459631501395637888351
189447252093456832526
919263002791275776712
649078753489094720887
378894504186913665062
108710254884732609237
838526005582551553423
568341756280370497598
298157506978189441773
27973257676008385948
757789008373827330134
487604759071646274309
217420509769465218484
947236260467284162670
677052011165103106845
406867761862922051020
136683512560740995195
866499263258559939381
596315013956378883556
326130764654197827731
55946515352016771906
785762266049835716092
515578016747654660267
...

С хорошей степенью случайности, если ваше пространство на несколько порядков меньше, чем M127.

Кредит @nick-steele и @bta за подход.

На самом деле это не специфичный для Ruby ответ, но я надеюсь, что это разрешено. Эндрю Кенслер приводит функцию C++ permute(), которая делает именно это в своей Коррелированная выборка с множественными дрожаниями. отчет.

Насколько я понимаю, точная функция, которую он предоставляет, действительно работает, только если ваш массив имеет размер до 2 ^ 27, но общую идею можно использовать для массивов любого размера.

Я сделаю все возможное, чтобы как-то объяснить это. Первая часть заключается в том, что вам нужен хеш, который является обратимым для любого домена с размером, равным степени двойки. Рассмотрим x = i + 1. Независимо от того, что такое x, даже если ваше целое число переполняется, вы можете определить, что такое i. Более конкретно, вы всегда можете определить младшие n битов числа i по младшим n битам числа x. Сложение — это обратимая хэш-операция, как и умножение на нечетное число, как и побитовое исключающее ИЛИ на константу. Если вы знаете определенный домен степени двойки, вы можете скремблировать биты в этом домене. Например. x ^= (x & 0xFF) >> 5) действителен для 16-битного домена. Вы можете указать этот домен с маской, например. mask = 0xFF, и ваша хеш-функция станет x = hash(i, mask). Конечно, вы можете добавить начальное значение в эту хэш-функцию, чтобы получить различные рандомизации. Кенслер излагает в статье более достоверные операции.

Итак, у вас есть обратимая функция x = hash(i, mask, seed). Проблема в том, что если вы хэшируете свой индекс, вы можете получить значение, превышающее размер вашего массива, то есть вашего домена. Вы не можете просто по модулю это или вы получите столкновения.

Обратимый хеш — это ключ к использованию метода, называемого циклическим ходьбой, представленного в Ciphers. с произвольными конечными доменами. Поскольку хэш является обратимым (т. е. 1-к-1), вы можете просто многократно применять один и тот же хэш, пока ваше хэш-значение не станет меньше, чем ваш массив! Поскольку вы применяете один и тот же хеш, а сопоставление — один к одному, любое значение, которое вы получите, будет отображаться ровно на один индекс, поэтому у вас не будет коллизий. Таким образом, ваша функция может выглядеть примерно так для 32-битных целых чисел (псевдокод):

fun permute(i, length, seed) {
  i = hash(i, 0xFFFF, seed)
  while(i >= length): i = hash(i, 0xFFFF, seed)
  return i
}

Чтобы добраться до вашего домена, может потребоваться много хэшей, поэтому Кенслер применяет простой трюк: он держит хеш в домене следующей степени двойки, что требует очень мало итераций (в среднем ~ 2), маскируя из ненужных битов. Окончательный алгоритм выглядит так:

fun next_pow_2(length) {
  # This implementation is for clarity.
  # See Kensler's paper for one way to do it fast.
  p = 1
  while (p < length): p *= 2
  return p
}

permute(i, length, seed) {
  mask = next_pow_2(length)-1
  i = hash(i, mask, seed) & mask
  while(i >= length): i = hash(i, mask, seed) & mask
  return i
}

Вот и все! Очевидно, что здесь важно выбрать хорошую хеш-функцию, которую Кенслер предоставляет в статье, но я хотел разобрать объяснение. Если вы хотите каждый раз иметь разные случайные перестановки, вы можете добавить начальное значение в функцию перестановки, которая затем передается хеш-функции.