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

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

Даже если вы используете только один бит на значение (было ли это значение опробовано, да или нет), вам потребуется 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. Каждая партия может обрабатываться независимыми узлами.

Ссылка:

Map-reduce in Ruby

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

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

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

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

# 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 в разделе # параметры можно изменить на меньшее число, чтобы получить более быстрые результаты.

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

Но я не знаю, почему вас волнует двойное появление одного и того же числа. Если (0..99 ** 99) - это ваш диапазон, то, если вы можете генерировать 10 ^ 10 случайных чисел в секунду (если у вас процессор с тактовой частотой 3 ГГц и около 4 ядер, на которых вы генерируете одно случайное число число на цикл ЦП - что невозможно, а рубин даже сильно его замедлит), тогда потребуется около 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
}

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

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

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