2

Ruby 可能不是最适合的语言,但我对在终端中使用它感到很自在,所以这就是我要使用的。

我需要处理从 1 到 666666 的数字,因此我将所有包含 6 但不包含 7、8 或 9 的数字都固定出来。第一个数字是6,下一个16,然后26等等。然后我需要像这样打印它(6=6) (16=6) (26=6),当我有像这样的范围时6066我需要像这样打印(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) }

正如我所说,它适用于数以百万计的数字 - 但我想要一些关于如何使更漂亮和更高效的建议。

4

10 回答 10

4

我删除了我之前对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 位模数的 gen 数字(所以 base-7 数字)
  • 生成最后一位“智能”:这是压缩范围的原因

那么......时间是什么?这是用 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,我可以请你投票吗:)

你能说我很自豪吗?这是我第一次接触 ruby​​;我在 2 小时前开始使用 ruby​​ koans ......

由@johndoutath 编辑

非常好!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
于 2011-04-16T01:43:58.153 回答
3

利用数字中的模式,您可以使许多循环短路,如下所示:

如果将 a 定义prefix为 100 位及其之前的所有内容,并将 the 定义suffix为 10 和 1 位中的所有内容,则循环遍历每个可能的前缀:

  • 如果前缀为空(即您正在测试 0-99),则有 13 个可能的匹配项
  • 否则,如果前缀包含 7、8 或 9,则没有可能的匹配项。
  • 如果前缀包含 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) 

ETC...

于 2011-04-15T18:43:58.690 回答
2

注意我不会说 ruby​​,但我打算稍后做一个 ruby​​ 版本只是为了速度比较:)


如果您只是迭代从 0 到 117648 ( ruby <<< 'print "666666".to_i(7)') 的所有数字并以 base-7 表示法打印它们,那么您至少会丢弃任何包含 7、8、9 的数字。这包括 MrE 的优化建议,除了将问题提升为简单的 int 算术而不是字符序列操作。

剩下的就是检查是否存在至少一个 6。这将使算法最多连续跳过 6 个项目,所以我认为它不那么重要(总范围内可跳过项目的平均数量是 40% )。

6666666666的简单基准测试

(请注意,这意味着输出 222,009,073 (222M) 行 6 年数字)

为了接近这个想法,我编写了这段高度优化的 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”时的“旋转”
  • 代码只是更短......

运行时间: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
于 2011-04-15T22:04:53.973 回答
1
$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)" if $range_start > 0 # 没有范围,打印出之前的数字
    $range_start = $range_end = 我
  结尾
结尾

'1'.upto('666') 做 |n|
  next unless n =~ /6/ # 只保留包含 6 的数字
  next if n =~ /[789]/ # 删除包含 7、8 或 9 的数字
  output_number n.to_i
结尾
如果 $range_start < $range_end
  $f.puts "(#{$range_start} 到 #{$range_end})"
结尾
$f.close

放“红宝石很漂亮:)”
于 2011-04-15T19:50:23.747 回答
1

我想出了这段代码,我试图或多或少地保留 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)
于 2011-04-15T20:18:31.670 回答
1

我的第一个答案是试图太聪明。这是一个更简单的版本

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
于 2011-04-15T20:21:06.397 回答
0

基本观察:如果当前数字是(比如说)1900你知道你可以安全地跳到至少2000......

于 2011-04-15T18:26:00.637 回答
0

我在下面的回答并不完整,只是为了展示一条路径(我可能会回来继续回答):

只有两种情况:

1) 除最低位以外的所有数字要么不存在要么不存在 6

6、16、...

2) 除最低一位外,至少一位包括 6

60--66, 160--166, 600--606, ...

(1) 中的情况不包括任何连续数字,因为它们的最低位都有 6,并且彼此不同。(2) 中的情况都显示为连续范围,其中最低位从 0 到 6 连续。(2) 中的任何单个延续都不与 (2) 中的另一个延续或与 (1) 中的任何延续不连续,因为数字小于xxxxx0 将是 xxxy9,比 xxxxxx6 大一的数字将是 xxxxxx7,因此被排除在外。

因此,问题归结为以下几点:

3)

获取 "" 到 "66666" 之间不包含 "6" 的所有字符串
对于它们中的每一个 ("xxx"),输出字符串 "(xxx6=6)"

4)

获取 "" 到 "66666" 之间的所有字符串,其中至少包含一个 "6"
对于它们中的每一个 ("xxx"),输出字符串 "(xxx0 THRU xxx6=6)"

于 2011-04-15T21:05:05.753 回答
0

我没有费心更新我的 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 的版本运行(生成高达 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)
于 2011-04-15T23:22:46.887 回答
0

这里的杀手是

numbers = (1..666666).to_a

Range 支持迭代,因此通过遍历整个范围并累积包含块中的段的数字会更好。当一个块完成并被另一个块取代时,您可以将其写出来。

于 2011-04-16T08:12:18.463 回答