Ruby中的数字运算(需要优化)
Ruby可能不是最佳语言,但我很乐意在终端中使用它,这就是我的目标。
我需要处理从1到666666的数字,所以我列出了所有包含6但不包含7,8或9的数字。第一个数字是6
,接下来的数字是16
,然后是26
等等。 然后我需要它打印像这样(6=6) (16=6) (26=6)
,当我有60
到66
范围时,我需要打印像(60 THRU 66=6)
(SPSS语法)。
我有这个代码它可以工作,但它既不漂亮也不高效,所以我怎么能优化它?
(可能会跟随愚蠢的代码)
class Array def to_ranges array = self.compact.uniq.sort ranges = [] if !array.empty? # Initialize the left and right endpoints of the range left, right = array.first, nil array.each do |obj| # If the right endpoint is set and obj is not equal to right's successor # then we need to create a range. if right && obj != right.succ ranges << Range.new(left,right) left = obj end right = obj end ranges << Range.new(left,right) unless left == right end ranges end end write = "" numbers = (1..666666).to_a # split each number in an array containing it's ciphers numbers = numbers.map { |i| i.to_s.split(//) } # delete the arrays that doesn't contain 6 and the ones that contains 6 but also 8, 7 and 9 numbers = numbers.delete_if { |i| !i.include?('6') } numbers = numbers.delete_if { |i| i.include?('7') } numbers = numbers.delete_if { |i| i.include?('8') } numbers = numbers.delete_if { |i| i.include?('9') } # join the ciphers back into the original numbers numbers = numbers.map { |i| i.join } numbers = numbers.map { |i| i = Integer(i) } # rangify consecutive numbers numbers = numbers.to_ranges # edit the ranges that go from 1..1 into just 1 numbers = numbers.map do |i| if i.first == i.last i = i.first else i = i end end # string stuff numbers = numbers.map { |i| i.to_s.gsub(".."," thru ") } numbers = numbers.map { |i| "(" + i.to_s + "=6)"} numbers.each { |i| write << " " + i } File.open('numbers.txt','w') { |f| f.write(write) }
正如我所说,即使数以百万计的数字也适用于数字 – 但我想就如何制作更漂亮,更高效的方法提出一些建议。
我之前删除了parlez-vous-ruby的尝试? 并弥补了这一点。 我知道有一个优化版本的x3ro的优秀示例 。
$,="\n" puts ["(0=6)", "(6=6)", *(1.."66666".to_i(7)).collect {|i| i.to_s 7}.collect do |s| s.include?('6')? "(#{s}0 THRU #{s}6=6)" : "(#{s}6=6)" end ]
与x3ro的版本相比
……它下降到三行
… 204.2 x更快(至66666666)
…具有字节相同的输出
它使用我的所有想法进行优化
- 基于模7位数的基数(所以基数为7的数字)
- 生成最后一个数字’smart’:这是压缩范围的原因
所以……时间是什么? 这是测试8位数(到66666666,或823544行输出):
$ time ./x3ro.rb > /dev/null real 8m37.749s user 8m36.700s sys 0m0.976s $ time ./my.rb > /dev/null real 0m2.535s user 0m2.460s sys 0m0.072s
虽然性能实际上很好,但它甚至不接近我之前发布的C优化版本 :由于OutOfMemory,我无法将my.rb运行到6666666666(6×10)。 当运行到9位数时,这是比较结果:
sehe@meerkat:/tmp$ time ./my.rb > /dev/null real 0m21.764s user 0m21.289s sys 0m0.476s sehe@meerkat:/tmp$ time ./t2 > /dev/null real 0m1.424s user 0m1.408s sys 0m0.012s
C版本仍然快了15倍……考虑到它在裸机上运行,这是公平的。
希望你喜欢它,如果只是为了学习Ruby,我可以请你的投票:)
( 你能告诉我我很自豪吗?这是我第一次遇到ruby;我2小时前开始使用rubykoans …… )
由@johndouthat编辑 :
非常好! 使用base7非常聪明,这对你的第一次ruby试用来说非常棒:)
以下是对您的代码段的轻微修改,可让您测试10位数而不会出现OutOfMemory错误:
puts ["(0=6)", "(6=6)"] (1.."66666666".to_i(7)).each do |i| s = i.to_s(7) puts s.include?('6') ? "(#{s}0 THRU #{s}6=6)" : "(#{s}6=6)" end # before: real 0m26.714s user 0m23.368s sys 0m2.865s # after real 0m15.894s user 0m13.258s sys 0m1.724s
利用数字中的模式,可以使许多循环短路,如下所示:
如果您将prefix
定义为100s位置及其前面的所有内容,并将suffix
定义为10s和1s中的所有内容,则循环遍历每个可能的前缀:
- 如果前缀为空(即您正在测试0-99),则有13种可能的匹配
- elsif前缀包含7,8或9,没有可能的匹配。
- elsif前缀包含6,有49种可能的匹配(7×7网格)
- 否则,有13种可能的比赛。 (见下图)
(该代码尚未排除不在该范围内的数字,但它非常接近)
number_range = (1..666_666) prefix_range = ((number_range.first / 100)..(number_range.last / 100)) for p in prefix_range ps = p.to_s # TODO: if p == prefix_range.last or p == prefix_range.first, # TODO: test to see if number_range.include?("#{ps}6".to_i), etc... if ps == '0' puts "(6=6) (16=6) (26=6) (36=6) (46=6) (56=6) (60 thru 66) " elsif ps =~ /7|8|9/ # there are no candidate suffixes if the prefix contains 7, 8, or 9. elsif ps =~ /6/ # If the prefix contains a 6, then there are 49 candidate suffixes for i in (0..6) print "(#{ps}#{i}0 thru #{ps}#{i}6) " end puts else # If the prefix doesn't contain 6, 7, 8, or 9, then there are only 13 candidate suffixes. puts "(#{ps}06=6) (#{ps}16=6) (#{ps}26=6) (#{ps}36=6) (#{ps}46=6) (#{ps}56=6) (#{ps}60 thru #{ps}66) " end end
其中打印出以下内容:
(6=6) (16=6) (26=6) (36=6) (46=6) (56=6) (60 thru 66) (106=6) (116=6) (126=6) (136=6) (146=6) (156=6) (160 thru 166) (206=6) (216=6) (226=6) (236=6) (246=6) (256=6) (260 thru 266) (306=6) (316=6) (326=6) (336=6) (346=6) (356=6) (360 thru 366) (406=6) (416=6) (426=6) (436=6) (446=6) (456=6) (460 thru 466) (506=6) (516=6) (526=6) (536=6) (546=6) (556=6) (560 thru 566) (600 thru 606) (610 thru 616) (620 thru 626) (630 thru 636) (640 thru 646) (650 thru 656) (660 thru 666) (1006=6) (1016=6) (1026=6) (1036=6) (1046=6) (1056=6) (1060 thru 1066) (1106=6) (1116=6) (1126=6) (1136=6) (1146=6) (1156=6) (1160 thru 1166) (1206=6) (1216=6) (1226=6) (1236=6) (1246=6) (1256=6) (1260 thru 1266) (1306=6) (1316=6) (1326=6) (1336=6) (1346=6) (1356=6) (1360 thru 1366) (1406=6) (1416=6) (1426=6) (1436=6) (1446=6) (1456=6) (1460 thru 1466) (1506=6) (1516=6) (1526=6) (1536=6) (1546=6) (1556=6) (1560 thru 1566) (1600 thru 1606) (1610 thru 1616) (1620 thru 1626) (1630 thru 1636) (1640 thru 1646) (1650 thru 1656) (1660 thru 1666)
等等…
注意我不会说ruby,但我打算 以后做一个ruby版本只是为了速度比较:)
如果你只是迭代从0到117648的所有数字( ruby <<< 'print "666666".to_i(7)'
)并以base-7表示法打印它们,你至少会丢弃任何包含7,8的数字, 9。 这包括MrE的优化建议,除了将问题解释为简单的int算术而不是char序列操作。
剩下的就是检查是否存在至少一个6.这将使算法连续跳过最多6个项目,所以我认为它不那么重要(总范围内的可跳过项目的平均数量是40% )。
6666666666的简单基准
(注意,这意味着输出222,009,073(222M)行的6-y数字)
接近这个想法,我写了这个非常优化的C代码(我不会说ruby)来演示这个想法。 我把它运行到282475248(一致到6666666666(mod 7))所以它更像是一个衡量标准: 0m26.5s
#include static char buf[11]; char* const bufend = buf+10; char* genbase7(int n) { char* it = bufend; int has6 = 0; do { has6 |= 6 == (*--it = n%7); n/=7; } while(n); return has6? it : 0; } void asciify(char* rawdigits) { do { *rawdigits += '0'; } while (++rawdigits != bufend); } int main() { *bufend = 0; // init long i; for (i=6; i<=282475248; i++) { char* b7 = genbase7(i); if (b7) { asciify(b7); puts(b7); } } }
我还对另一种方法进行了基准测试,这种方法在不到一半的时间内就出现了不足为奇的原因
- 此版本直接以ascii字符串forms处理结果,准备显示
- 此版本将
has6
标志快捷方式用于更深层次的递归级别 - 当需要为'6'时,这个版本还优化了最后一个数字的'twiddling'
- 代码简短......
运行时间: 0m12.8s
#include #include inline void recursive_permute2(char* const b, char* const m, char* const e, int has6) { if (m
基准衡量标准:
gcc -O4 t6.c -o t6 time ./t6 > /dev/null
$ range_start = -1 $ range_end = -1 $ f = File.open('numbers.txt','w') def output_number(i) if $ range_end == i-1 $ range_end = i elsif $ range_start <$ range_end $ f.puts“(#{$ range_start} thru#{$ range_end})” $ range_start = $ range_end = i 其他 $ f.puts“(#{$ range_start} = 6)”如果$ range_start> 0#无范围,打印出前一个数字 $ range_start = $ range_end = i 结束 结束 '1'.upto('666')do | n | 接下来除非n =〜/ 6 /#只保留包含6的数字 如果n =〜/ [789] /#删除包含7,8或9的nubmers output_number n.to_i 结束 if $ range_start <$ range_end $ f.puts“(#{$ range_start} thru#{$ range_end})” 结束 $ f.close 把“Ruby很漂亮:)”
我想出了这段代码,我试图在FP-styling中保持或多或少。 可能效率不高(正如已经说过的那样,使用基本数字逻辑,你将能够提高性能,例如直接从19xx跳到2000,但我会留给你:)
def check(n) n = n.to_s n.include?('6') and not n.include?('7') and not n.include?('8') and not n.include?('9') end def spss(ranges) ranges.each do |range| if range.first === range.last puts "(" + range.first.to_s + "=6)" else puts "(" + range.first.to_s + " THRU " + range.last.to_s + "=6)" end end end range = (1..666666) range = range.select { |n| check(n) } range = range.inject([0..0]) do |ranges, n| temp = ranges.last if temp.last + 1 === n ranges.pop ranges.push(temp.first..n) else ranges.push(n..n) end end spss(range)
我的第一个答案是试图太聪明。 这是一个更简单的版本
class MutablePrintingCandidateRange < Struct.new(:first, :last) def to_s if self.first == nil and self.last == nil '' elsif self.first == self.last "(#{self.first}=6)" else "(#{self.first} thru #{self.last})" end end def <<(x) if self.first == nil and self.last == nil self.first = self.last = x elsif self.last == x - 1 self.last = x else puts(self) # print the candidates self.first = self.last = x # reset the range end end end
以及如何使用它:
numer_range = (1..666_666) current_range = MutablePrintingCandidateRange.new for i in numer_range candidate = i.to_s if candidate =~ /6/ and candidate !~ /7|8|9/ # number contains a 6, but not a 7, 8, or 9 current_range << i end end puts current_range
基本观察:如果当前的数字是(比方说) 1900
你知道你可以安全地跳过至少2000
…
( 我没有费心更新我的C解决方案进行格式化。相反, 我选择了x3ro优秀的ruby版本并对其进行了优化 )
取消删除:
我仍然不确定改变的范围 – 符号行为是否实际上不是OP想要的:这个版本改变了破坏实际连续模6的范围的行为; 我不会对OP实际预期感到惊讶 。
.... (555536=6) (555546=6) (555556 THRU 666666=6)
代替
.... (666640 THRU 666646=6) (666650 THRU 666656=6) (666660 THRU 666666=6)
我将让OP决定,这里是修改版本,它在18%的时间内作为x3ro的版本运行(3.2s而不是17.0s,当生成6666666(7×6)时)。
def check(n) n.to_s(7).include?('6') end def spss(ranges) ranges.each do |range| if range.first === range.last puts "(" + range.first.to_s(7) + "=6)" else puts "(" + range.first.to_s(7) + " THRU " + range.last.to_s(7) + "=6)" end end end range = (1..117648) range = range.select { |n| check(n) } range = range.inject([0..0]) do |ranges, n| temp = ranges.last if temp.last + 1 === n ranges.pop ranges.push(temp.first..n) else ranges.push(n..n) end end spss(range)
我的答案不完整,但只是为了显示一条路径(我可能会回来继续回答):
只有两种情况:
1)除最低位之外的所有数字要么不存在,要么不存在6
6,16,……
2)除最低的一个数字外,至少有一个数字包括6个数字
60–66,160–166,600–606,……
(1)中的情况不包括任何连续数字,因为它们都具有最低位数的6,并且彼此不同。 (2)中的情况都显示为连续范围,其中最低位从0到6继续。(2)中的任何单个延续不与(2)中的另一个连续或与(1)中的任何一个连续,因为小于1 xxxxx0将是xxxxy9,比xxxxxx6更多的数字将是xxxxxx7,因此被排除在外。
因此,问题减少到以下几点:
3)
获取不包含“6”的“”到“66666”之间的所有字符串
对于它们中的每一个(“xxx”),输出字符串“(xxx6 = 6)”
4)
获取包含至少一个“6”的“”到“66666”之间的所有字符串
对于它们中的每一个(“xxx”),输出字符串“(xxx0 THRU xxx6 = 6)”
这里的杀手是
numbers = (1..666666).to_a
范围支持迭代,因此您可以通过遍历整个范围并累积包含块中的段的数字来获得更好的效果。 当一个块完成并被另一个块取代时,您可以将其写出来。