рубиновые перечислители: сразу пропустить несколько итераций (или начать итерацию с n)

Я повторяю перестановки списка (18 элементов) следующим образом:

List = [item0..item18] # (unpredictable)
Permutation_size = 7
Start_at = 200_000_000

for item, i in List.repeated_permutation(Permutation_size).each_with_index
  next if i < Start_at
  # do stuff
end

Start_at используется для возобновления работы из ранее сохраненного состояния, поэтому оно всегда отличается, но для достижения 200 миллионов требуется почти 200 с, поэтому мне интересно, есть ли более быстрый способ пропустить несколько итераций или начать с итерации n (преобразование перечислителя в массив занимает еще больше времени). Если нет, то также будет оценен способ создания пользовательского repeated_permutation(n).each_with_index (который дает результаты в том же порядке).

Не стесняйтесь перенаправить меня на существующий ответ (я не нашел ни одного)

PS. (что я придумал)

class Array
  def rep_per_with_index len, start_at = 0
    b = size
    raise 'btl' if b > 36
    counter = [0]*len
    # counter = (start_at.to_s b).split('').map {|i| '0123456789'.include?(i) ? i.to_i : (i.ord - 87)} #this is weird, your way is way faster
    start_at.to_s(b).chars.map {|i| i.to_i b}
    counter.unshift *[0]*(len - counter.length)
    counter.reverse!
    i = start_at
    Enumerator.new do |y|
      loop do
        y << [counter.reverse.map {|i| self[i]}, i]
        i += 1
        counter[0] += 1
        counter.each_with_index do |v, i|
          if v >= b
            if i == len - 1
              raise StopIteration
            else
              counter[i] = 0
              counter[i + 1] += 1
            end
          else
            break
          end
        end
      end
    end
  end
end

ruby next skip enumerator continue
person Asone Tuhid    schedule 27.06.2017    source источник
comment
Каков примерный максимальный размер list?   -  person Cary Swoveland    schedule 28.06.2017
comment
В идеале хотелось бы общее решение, но сейчас размер всегда 18   -  person Asone Tuhid    schedule 28.06.2017

Ответы (1)


arrow_upward
2
arrow_downward

Сначала я создаю вспомогательный метод change_base с тремя аргументами:

  • off, смещение базы 10 в последовательность повторяющихся перестановок данного массива arr,
  • m, основание системы счисления; а также
  • p, размер перестановки.

Метод выполняет три шага для построения массива off_m:

  • преобразует off в основание m (основание m);
  • разделяет цифры базового значения m в массив; а также
  • если необходимо, дополняет массив ведущими 0s, чтобы сделать его размером p.

При установке m = arr.size каждая цифра off_m является смещением в arr, поэтому off_m сопоставляет смещение по основанию 10 с уникальной перестановкой размера p.

def change_base(m, p, off)
  arr = off.to_s(m).chars.map { |c| c.to_i(m) }
  arr.unshift(*[0]*(p-arr.size)) 
end

Некоторые примеры:

change_base(16, 2, 32)
  #=> [2, 0]
change_base(16, 3, 255)
  #=> [0, 15, 15]
change_base(36, 4, 859243)
  #=> [18, 14, 35, 31]
18*36**3 + 14*36**2 + 35*36**1 + 31  
  #=> 859243

Эта реализация change_base требует, чтобы m <= 36. Я предполагаю, что этого будет достаточно, но доступны алгоритмы для преобразования чисел с основанием 10 в числа с произвольно большими основаниями.

Теперь мы создаем метод, который принимает заданный массив arr, размер каждой перестановки p и заданное смещение по основанию 10 в последовательности перестановок. Метод возвращает перестановку, а именно массив размером p, элементы которого являются элементами arr.

def offset_to_perm(arr, p, off)
  arr.values_at(*change_base(arr.size, p, off))
end

Теперь мы можем попробовать это на примере.

arr = (0..3).to_a
p = 2

(arr.size**p).times do |off|
  print "perm for off = "
  print " " if off < 10
  print "#{off}: "
  p offset_to_perm(arr, p, off)
end

perm for off =  0: [0, 0]
perm for off =  1: [0, 1]
perm for off =  2: [0, 2]
perm for off =  3: [0, 3]
perm for off =  4: [0, 1]
perm for off =  5: [1, 1]
perm for off =  6: [2, 1]
perm for off =  7: [3, 1]
perm for off =  8: [0, 2]
perm for off =  9: [1, 2]
perm for off = 10: [2, 2]
perm for off = 11: [3, 2]
perm for off = 12: [0, 3]
perm for off = 13: [1, 3]
perm for off = 14: [2, 3]
perm for off = 15: [3, 3]

Если мы хотим начать, скажем, со смещения 5, мы можем написать:

i = 5
p offset_to_perm(arr, p, i)
[1, 1]
i = i.next #=> 6
p offset_to_perm(arr, p, i)
[2, 1]
...
person Cary Swoveland    schedule 27.06.2017
comment
Я сделал то же самое (в качестве счетчика), но мой примерно в 6 раз медленнее только при повторении, чем [...].repeated_permutation(n).with_index, вы проверяли скорость? - person Asone Tuhid; 28.06.2017
comment
Признаюсь, я не смотрел на ваш код до сих пор. Да, подходы очень похожи. Поскольку у вас есть рабочий код, я предлагаю вам перенести его из вашего вопроса в ответ (и, желательно, добавить некоторые тесты). Я не проводил никаких тестов производительности. - person Cary Swoveland; 28.06.2017