2

Ruby はこれに最適な言語ではないかもしれませんが、私は自分の端末でこれを使用することに少し慣れているので、それを使用しています。

1 から 666666 までの数字を処理する必要があるため、6 を含み 7、8、9 を含まないすべての数字をピンで留めます。最初の数字は6、次16は 、というようになり26ます。次に、このように印刷する必要があり(6=6) (16=6) (26=6)、範囲がある場合は(SPSS構文)のように印刷60する66必要があります。(60 THRU 66=6)

私はこのコードを持っていて動作しますが、美しくも効率的でもありません。どうすれば最適化できますか?

(ばかげたコードが続くかもしれません)

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のバージョンと比較

… 3行に減っています

... 204.2 倍高速 (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 を開始しました... )

@johndouthatによる編集

非常に素晴らしい!base7 の使用は非常に巧妙で、これは初めての Ruby の試用版として最適です :)

OutOfMemory エラーを発生させずに 10 桁以上をテストできるスニペットのわずかな変更を次に示します。

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 をprefix100 の位とその前のすべてsuffixとして定義し、 the を 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) 

等...

于 2011-04-15T18:43:58.690 に答える
2

私はルビーを話さないことに注意してください、しかし私は速度比較のために後でルビーバージョンをするつもりです:)


0から117648(ruby <<< 'print "666666".to_i(7)')までのすべての数値を繰り返し、7を底とする表記で出力すると、少なくとも7、8、9を含む数値はすべて破棄されます。これには、MrEによる最適化の提案が含まれますが、問題を文字シーケンス操作ではなく単純なint算術に持ち上げることは別としてです。

残っているのは、少なくとも1つの6の存在をチェックすることだけです。これにより、アルゴリズムは連続して最大6つのアイテムをスキップするため、重要性は低いと思います(全範囲でスキップ可能なアイテムの平均数は40%です)。 )。

6666666666への単純なベンチマーク

(これは、6-y番号の222,009,073(222M)行を出力することを意味することに注意してください)

このアイデアに近づきながら、この非常に高度に最適化されたCコード(ルビーは話せません)を作成して、アイデアを示しました。私はそれを282475248(66666666666(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 = i
  elsif $range_start < $range_end
    $f.puts "(#{$range_start} から #{$range_end})"
    $range_start = $range_end = i
  そうしないと
    $f.puts "(#{$range_start}=6)" if $range_start > 0 # 範囲なし、前の数値を出力
    $range_start = $range_end = i
  終わり
終わり

'1'.upto('666') do |n|
  next until 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

puts 「Ruby は美しい :)」
于 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

ここのキラーは

numbers = (1..666666).to_a

Rangeは反復をサポートしているため、範囲全体を調べて、セグメントをブロックに含む数値を累積することをお勧めします。1つのブロックが終了し、別のブロックに取って代わられたら、それを書き出すことができます。

于 2011-04-16T08:12:18.463 に答える
0

以下の私の答えは完全ではありませんが、パスを示すためだけです (私は戻って答えを続けるかもしれません):

次の 2 つのケースのみがあります。

1) 最下位桁以外のすべての桁が存在しないか、そうでない 6

6、16、...

2) 最下位桁以外に少なくとも 1 桁は 6 を含む

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

(1) の場合は、すべて最下位桁が 6 であり、互いに異なるため、連続する数は含まれません。(2) のケースはすべて、最下位桁が 0 から 6 まで続く連続した範囲として表示されます。(2) の単一の継続は、(2) の別の継続または (1) のいずれかと連続していません。 xxxxx0 は xxxxy9 になり、xxxxxx6 より 1 大きい数値は xxxxxx7 になるため、除外されます。

したがって、質問は次のようになります。

3)

"" から "66666" の間で "6" を含まないすべての文字列を取得します
。それぞれ ("xxx") に対して、文字列 "(xxx6=6)" を出力します。

4)

"" から "66666" までの文字列のうち、少なくとも 1 つの "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に決定させます。これが修正されたバージョンで、 x3roのバージョンと同じ18%の時間で実行されます(最大6666666(7x6)を生成する場合、17.0秒ではなく3.2秒)。

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

基本的な観察: 現在の数が (たとえば)1900である場合、少なくとも2000...まで安全にスキップできることがわかっています。

于 2011-04-15T18:26:00.637 に答える