Ruby中的数字运算（需要优化）

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

正如我说的那样，它甚至可以用于数以百万计的数字-但是我想就如何使自己更漂亮，更高效提供一些建议。

已邀请:

10 个回复

逆捐凶撤小

我删除了之前的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倍（至66666666） ...具有字节相同的输出它使用了我所有的想法进行优化 gen数字基于模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（6x10）。当运行到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的目的，请允许我投票：) （你能告诉我我很自豪吗？这是我第一次与红宝石相遇； 2个小时前，我开始了红宝石可汗...）由@johndouthat编辑：非常好！ base7的用法非常聪明，这对于您的第一次红宝石试用来说是一件很棒的事情:) 这是对代码段的略微修改，可让您测试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

锹缄

利用数字中的模式，您可以使许多环路短路，如下所示：如果您将ѭ12定义为100位及其之前的所有内容，并将ѭ13定义为10s和1s处的所有内容，然后循环通过每个可能的前缀：如果前缀为空（即您正在测试0-99），则可能有13个匹配项否则，如果前缀包含7、8或9，则没有可能的匹配项。 elsif如果前缀包含6，则有49个可能的匹配项（7x7网格）否则，有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)

等等...

盟犯涩沟都

注意我不会说红宝石，但是我打算稍后做一个红宝石版本，只是为了比较速度:) 如果您只是迭代从0到117648（ruby <<< \'print \"666666\".to_i(7)\'）的所有数字，并以7为基数的打印方式，那么您将至少丢弃所有包含7,8,9的数字。这包括MrE的优化建议，除了将问题提升为简单的整型算术而不是字符序列处理。剩下的就是检查是否至少有6个项目。这将使算法连续最多跳过6个项目，因此我认为它的重要性降低了（总范围内可跳过项目的平均数量为40％）。简单基准达到6666666666 （请注意，这意味着输出6位数的222,009,073（222M）行）紧贴这个想法，我编写了这个经过高度优化的C代码（我不会说ruby）来演示这个想法。我将其运行到282475248（与6666666666（mod 7）一致），因此它更像是一个衡量基准：0m26.5s

#include <stdio.h>

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字符串形式处理结果，准备显示此版本将has6标志快捷方式缩短了递归级别当要求为\'6 \'时，此版本还会优化最后一位的'twiddling' 该代码只是更短... 播放时间：0m12.8s

#include <stdio.h>
#include <string.h>

inline void recursive_permute2(char* const b, char* const m, char* const e, int has6)
{
    if (m<e)
        for (*m = \'0\'; *m<\'7\'; (*m)++)
            recursive_permute2(b, m+1, e, has6 || (*m==\'6\'));
    else
        if (has6)
            for (*e = \'0\'; *e<\'7\'; (*e)++)
                puts(b);
        else /* optimize for last digit must be 6 */
            puts((*e=\'6\', b));
}

inline void recursive_permute(char* const b, char* const e)
{
    recursive_permute2(b, b, e-1, 0);
}

int main()
{
    char buf[] = \"0000000000\"; 
    recursive_permute(buf, buf+sizeof(buf)/sizeof(*buf)-1);
}

基准测试：

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）如果$ range_end == i-1 $ range_end =我 elsif $ range_start <$ range_end $ f.puts \“（＃{$ range_start}至＃{$ range_end}）\” $ range_start = $ range_end =我其他 $ f.puts \“（＃{$ range_start} = 6）\”如果$ range_start> 0＃没有范围，则打印出前一个数字 $ range_start = $ range_end =我结束结束 \'1 \'。upto（\'666 \'）做| n | 除非n =〜/ 6 /＃仅保留包含6的数字如果n =〜/ [789] /＃，则删除包含7、8或9的数字小数输出编号n.to_i 结束如果$ range_start <$ range_end $ f.puts \“（＃{$ range_start}至＃{$ range_end}）\” 结束 $ f.close 写道：“ Ruby很漂亮：）\”

凰葱崎济邯

我想出了这段代码，试图或多或少地保留FP样式。可能效率不高（如前所述，使用基本数字逻辑，您可以提高性能，例如，直接从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决定，这是修改后的版本，它的运行时间是x3ro版本的18％（生成6666666（7x6）时为3.2s而不是17.0s）。

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）获取\“ \”到\“ 66666 \”之间的所有不包含\“ 6 \”的字符串对于它们每个（\“ xxx \”），输出字符串\“（xxx6 = 6）\” 4）获取\“ \”到\“ 66666 \”之间的所有字符串，其中包括至少一个\“ 6 \” 对于它们每个（\“ xxx \”），输出字符串\“（xxx0 THRU xxx6 = 6）\”

疏腔傻小雹

这里的杀手是

numbers = (1..666666).to_a

范围支持迭代，因此遍历整个范围并累积将您的细分包括在块中的数字会更好。当一个块完成并被另一个替换时，您可以将其写出。

要回复问题请先登录或注册

Ruby中的数字运算（需要优化）

10 个回复

发起人

ruby

numbers

spss

问题状态

Ruby中的数字运算（需要优化）

与内容相关的链接

10 个回复

发起人

ruby

numbers

spss

问题状态