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

Question

Я бы хотел случайным образом перебрать диапазон. Каждое значение будет посещено только один раз, и все значения будут в конечном итоге посещены. Например:

class Array
    def shuffle
        ret = dup
        j = length
        i = 0
        while j > 1
            r = i + rand(j)
            ret[i], ret[r] = ret[r], ret[i]
            i += 1
            j -= 1
        end
        ret
    end
end

(0..9).to_a.shuffle.each{|x| f(x)}

, где f(x) - некоторая функция, которая работает с каждым значением. * * * * * * * * * * * * * * * * * * * * * * * * * * * * *1006*

Моя проблема в том, что shuffle должен работать с массивом, что не здорово, потому что я работаю с астрономически большими числами. Ruby быстро потребляет большой объем оперативной памяти, пытаясь создать чудовищный массив. Представьте себе замену (0..9) на (0..99**99). По этой же причине следующий код не будет работать:

tried = {} # store previous attempts
bigint = 99**99
bigint.times {
    x = rand(bigint)
    redo if tried[x]
    tried[x] = true
    f(x) # some function
}

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

Какой алгоритм может выполнить то, что я пытаюсь сделать?

[Edit1] : Почему я хочу это сделать? Я пытаюсь исчерпать пространство поиска алгоритма хеширования для входной строки N-длины в поисках частичных коллизий. Каждое число, которое я генерирую, эквивалентно уникальной входной строке, энтропии и всему. По сути, я "считаю", используя пользовательский алфавит .

[Edit2] : Это означает, что f(x) в вышеприведенных примерах является методом, который генерирует хэш и сравнивает его с постоянным целевым хешем для частичных коллизий. Мне не нужно сохранять значение x после вызова f(x), поэтому память должна оставаться постоянной с течением времени.

[Edit3 / 4/5/6] : дальнейшие разъяснения / исправления.

[Решение] : следующий код основан на решении @ bta. Для краткости next_prime не отображается. Он производит приемлемую случайность и посещает каждое число только один раз. См. Фактическое сообщение для более подробной информации.

N = size_of_range
Q = ( 2 * N / (1 + Math.sqrt(5)) ).to_i.next_prime
START = rand(N)

x = START
nil until f( x = (x + Q) % N ) == START # assuming f(x) returns x

Answer 1

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

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).

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

Answer 2

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

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

Даже если бы вы использовали Jaguar (топ 1 из 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
}

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

Answer 3

Вы хотите то, что называется "итератором полного цикла" ...

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

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, никогда не повторяясь. Если вы измените random_seed, который может быть чем угодно, или prime_number, который должен быть больше, а не делиться равномерно sample_size, вы получите новый случайный порядок , но вы все равно никогда не получите дубликат.

Answer 4

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

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

Answer 5

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

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: Это хорошая проблема для уменьшения карты. Каждая партия может обрабатываться независимыми узлами.

Справка:

Карта-уменьшение в Ruby

Answer 6

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

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

Answer 7

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

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 за подход.

Answer 8

[Редактировать] : Учитывая ответы @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 можно изменить на меньшее число, чтобы получить более быстрые результаты.

Answer 9

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

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

Answer 10

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