ruby枚举器:立即跳过多次迭代(或从n开始迭代)
ruby enumerators: immediately skip multiple iterations (or start iterating from 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
用于从以前保存的状态恢复所以它总是不同的但是几乎需要 200s 达到 2 亿所以我想知道是否有跳过多次迭代或从迭代 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
我首先构造一个辅助方法,change_base
,带有三个参数:
off
,给定数组arr
, 的重复排列序列中的以10为底的偏移量
m
,数制基数;和
p
,排列大小。
该方法执行三个步骤来构造一个数组off_m
:
- 将
off
转换为基数 m
(基数 m
);
- 将基
m
值的数字分隔成一个数组;和
- 如有必要,用前导
0
填充数组,使其大小为 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 为底的偏移量到排列序列中。方法 returns 一个排列,即大小为 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]
...
我正在迭代列表(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
用于从以前保存的状态恢复所以它总是不同的但是几乎需要 200s 达到 2 亿所以我想知道是否有跳过多次迭代或从迭代 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
我首先构造一个辅助方法,change_base
,带有三个参数:
off
,给定数组arr
, 的重复排列序列中的以10为底的偏移量
m
,数制基数;和p
,排列大小。
该方法执行三个步骤来构造一个数组off_m
:
- 将
off
转换为基数m
(基数m
); - 将基
m
值的数字分隔成一个数组;和 - 如有必要,用前导
0
填充数组,使其大小为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 为底的偏移量到排列序列中。方法 returns 一个排列,即大小为 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]
...