見栄え無視！とにかく軽くしたい

Question

rubyです。
０以上且つ９桁以下の整数値データを渡すと、加工して返す関数を作成しました。
行っている処理は

①送り値の数値を一桁ずつ調べていき、
１．その桁の数値が『１』 且つ
２．左右隣二ケタが『０』 の時、その桁の値を０にする。 (20011001 -> 20011000)
②数値の一の位が『０』の時、その桁が０にならなくなるまで削除する(１０で割る) (20011000 -> 20011)

です。

一応動くには動くのですが、
エンターキー一つで１００回くらい呼び出されることもあるので
出来る限り処理を軽くしたいです。

お知恵を拝借できればと思います。
よろしくお願いいたします。

尚、関係することはないと思いますが
各桁の数値は最高４で、５以上の数値は入りません。

def mj_arano(arano)
    maisu = [0,0,0,0,0,0,0,0,0,0,0,0,0] # 0 to 12
    maisu[2] = arano / 100000000
    maisu[3] = (arano / 10000000) % 10
    maisu[4] = (arano / 1000000) % 10
    maisu[5] = (arano / 100000) % 10
    maisu[6] = (arano / 10000) % 10
    maisu[7] = (arano / 1000) % 10
    maisu[8] = (arano / 100) % 10
    maisu[9] = (arano / 10) % 10
    maisu[10] =(arano / 1) % 10
    i = 2
    while i <= 10
        if maisu[i]==1 then
            if maisu[i-2]==0 && maisu[i-1]==0 && maisu[i+1]==0 && maisu[i+2]==0 then 
                maisu[i] = 0
                i = i + 2 #少しでもループを短くする
            end
        end
        i = i + 1
    end
    arano = 0
    arano = arano + (maisu[2] * 100000000)
    arano = arano + (maisu[3] * 10000000)
    arano = arano + (maisu[4] * 1000000)
    arano = arano + (maisu[5] * 100000)
    arano = arano + (maisu[6] * 10000)
    arano = arano + (maisu[7] * 1000)
    arano = arano + (maisu[8] * 100)
    arano = arano + (maisu[9] * 10)
    arano = arano + (maisu[10] * 1)
    
    #後ろ０の削除(2011200 -> 20112)
    while (arano % 10) == 0 && arano != 0
        arano = arano / 10
    end
    
    return arano
end

okuri=1010001 #数値は一例
mj_arano(okuri) # 101

okuri=200010100
mj_arano(okuri) # 200010100

okuri=10010001
mj_arano(okuri) # 0

▼▼追記10/03/21 17:46▼▼
▼▼改定10/03/23 20:57▼▼
下に長くなったのでまとめたコードを記載しておきます。

def mj_arano(arano)
    if "00#{arano}00".index('00100')
        if arano < 1000000 then
            arano = "00#{arano}00".gsub(/001(?=00)/, '000').to_i
        else
            maisu = [0,0,0,0,0,0,0,0,0,0,0,0,0] # 0 to 12
            maisu[2] = arano / 100000000
            maisu[3] = (arano / 10000000) % 10
            maisu[4] = (arano / 1000000) % 10
            maisu[5] = (arano / 100000) % 10
            maisu[6] = (arano / 10000) % 10
            maisu[7] = (arano / 1000) % 10
            maisu[8] = (arano / 100) % 10
            maisu[9] = (arano / 10) % 10
            maisu[10] =(arano / 1)
            i = 2
            while i <= 10
                if maisu[i]==1 then
                    if maisu[i-2]==0 && maisu[i-1]==0 && maisu[i+1]==0 && maisu[i+2]==0 then 
                        maisu[i] = 0
                        i += 2
                    end
                end
                i += 1
            end
            arano = 0
            arano += maisu[2] * 100000000
            arano += maisu[3] * 10000000
            arano += maisu[4] * 1000000
            arano += maisu[5] * 100000
            arano += maisu[6] * 10000
            arano += maisu[7] * 1000
            arano += maisu[8] * 100
            arano += maisu[9] * 10
            arano += maisu[10]
        end
    end
    #後ろ０の削除(2011200 -> 20112)
    arano /= 10 while (arano % 10) == 0 && arano != 0
end

Comments

[NCC1701]

問題文読解力不足のため削除

Answer 1

正規表現を使うのは処理が重そうな気がしたので、
数値計算だけでおこなってみた版 (mj_arano2) をつくりました。
でも質問文のコードより速くはなりませんでした。

そこで質問文にコードを少しだけ変更してみました。
こころもち速くなったかなという程度の変化でした。

以下のコードは 次の３つのメソッドを含んでいます。
mj_arano() // 0m15.652
mj_arano2() // 0m24.595s
mj_arano3() // 0m14.966s
mj_arano4() // 0m31.371s (raccy さんの回答の方法)
(質問ページにあった幾つかの入力と変換結果の例については、結果が一致することを確認するコードも入れてあります)

def mj_arano2(val)
  nums = []
  ans = 0

  work = val * 100
  while true
    work -= 100 if work % 100000 == 100
    work, r = [work / 10, work % 10]
    nums << r
    break if work == 0
  end

  # 後ろの 0 の削除(2011200 -> 20112)
  ans = 0
  nums.reverse_each do |x|
    ans = ans * 10 + x
  end
  ans /= 10 while (ans % 10) == 0 && ans != 0
  ans
end

def mj_arano3(arano)
  maisu = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 0 to 12
  maisu[2] = arano / 100000000
  maisu[3] = (arano / 10000000) % 10
  maisu[4] = (arano / 1000000) % 10
  maisu[5] = (arano / 100000) % 10
  maisu[6] = (arano / 10000) % 10
  maisu[7] = (arano / 1000) % 10
  maisu[8] = (arano / 100) % 10
  maisu[9] = (arano / 10) % 10
  maisu[10] = (arano / 1) % 10
  i = 2
  while i <= 10
    if maisu[i] == 1
      if maisu[i - 2] == 0 && maisu[i - 1] == 0 && maisu[i + 1] == 0 && maisu[i + 2] == 0
        maisu[i] = 0
        i += 2 # 少しでもループ回数を少なくする
      end
    end
    i += 1
  end

  arano = 0
  arano += maisu[2] * 100000000
  arano += maisu[3] * 10000000
  arano += maisu[4] * 1000000
  arano += maisu[5] * 100000
  arano += maisu[6] * 10000
  arano += maisu[7] * 1000
  arano += maisu[8] * 100
  arano += maisu[9] * 10
  arano += maisu[10]

  # 後ろの 0 の削除 (2011200 -> 20112)
  arano /= 10 while (arano % 10) == 0 && arano != 0
  arano
end

def mj_arano4(i)
  "00#{i}00".gsub(/001(?=00)/, '000').reverse.sub(/\A0+/, '').reverse.to_i
end

def mj_arano(arano)
  maisu = [0,0,0,0,0,0,0,0,0,0,0,0,0] # 0 to 12
  maisu[2] = arano / 100000000
  maisu[3] = (arano / 10000000) % 10
  maisu[4] = (arano / 1000000) % 10
  maisu[5] = (arano / 100000) % 10
  maisu[6] = (arano / 10000) % 10
  maisu[7] = (arano / 1000) % 10
  maisu[8] = (arano / 100) % 10
  maisu[9] = (arano / 10) % 10
  maisu[10] =(arano / 1) % 10
  i = 2
  while i <= 10
    if maisu[i]==1 then
      if maisu[i-2]==0 && maisu[i-1]==0 && maisu[i+1]==0 && maisu[i+2]==0 then
        maisu[i] = 0
        i = i + 2 #少しでもループを短くする
      end
    end
    i = i + 1
  end
  arano = 0
  arano = arano + (maisu[2] * 100000000)
  arano = arano + (maisu[3] * 10000000)
  arano = arano + (maisu[4] * 1000000)
  arano = arano + (maisu[5] * 100000)
  arano = arano + (maisu[6] * 10000)
  arano = arano + (maisu[7] * 1000)
  arano = arano + (maisu[8] * 100)
  arano = arano + (maisu[9] * 10)
  arano = arano + (maisu[10] * 1)

  #後ろ０の削除(2011200 -> 20112)
  while (arano % 10) == 0 && arano != 0
    arano = arano / 10
  end

  return arano
end

(91000000..99000000).each do |x|
  mj_arano4(x)
  # mj_arano2(x)
end

TESTS = [
  1010001,
  200010100,
  10010001,
  100100001,
  100010010
]
TESTS.each do |test|
  p "#{test} -> #{mj_arano(test)}, #{mj_arano2(test)}, #{mj_arano3(test)}, #{mj_arano4(test)}"
end

計測結果が以下です。３回ずつ走らせています。

mj_arano() 
$ time ruby 1.rb
real	0m15.751s
user	0m15.447s
sys	0m0.175s

$ time ruby 1.rb
real	0m15.969s
user	0m15.652s
sys	0m0.179s

$ time ruby 1.rb
real	0m16.191s
user	0m15.837s
sys	0m0.190s

mj_arano2
$ time ruby 1.rb
real	0m25.015s
user	0m24.334s
sys	0m0.315s

$ time ruby 1.rb
real	0m24.865s
user	0m23.923s
sys	0m0.354s

$ time ruby 1.rb
time ruby 1.rb
real	0m24.595s
user	0m23.969s

mj_arano3
time ruby 1.rb
real	0m15.448s
user	0m15.114s
sys	0m0.168s

$ time ruby 1.rb
real	0m15.261s
user	0m14.966s
sys	0m0.162s

$ time ruby 1.rb
real	0m16.440s
user	0m15.713s
sys	0m0.278s

mj_arano4
$ time ruby 1.rb
real	0m33.492s
user	0m32.190s
sys	0m0.504s

$ time ruby 1.rb
real	0m31.454s
user	0m30.628s
sys	0m0.360s

$ time ruby 1.rb
real	0m31.371s
user	0m30.673s
sys	0m0.310s

Comments

[torisan]

+= や /= や条件式を右に置く、などの記述は
個人的にあまり使っていなかったので失念していました。
そして、こちらの環境でも若干ながら早く処理が動いていることを確認しました。
調査頂いた計測値についても、似たか寄ったかの値が出ています。

二つ隣り二つ隣り……で考えていたので、計算で結果を出すなど考えてもいませんでした。いろんな記述があるものですね……。

②の記述を使用させていただきます。
回答ありがとうございました。

[katoy]

work, r = [work / 10, work % 10]
nums << r
と書くより
nums << work % 10
work /= 10
と書いたほうが、すこしだけ速くなりました。(23 秒台になった)
配列のオブジェクトを new する処理がなくなるからと思われます。

[torisan]

こちらでも確認しました。
記載のコードにおいて、処理時間半分……とまでは行きませんでしたが
1000000回の試行において、0.12秒ほどの削減となっています。

私が使用しようとしているコードでは１回につき１００回程度ですが
再帰の回数によっては差が出そうですね。

[katoy]

num[] の配列を使う必要がないことがわかりました。
次のコードでは 14秒台がでました。(質問文のコードよりほんの少しだけ速い)
def mj_arano21(val)
ans = 0
work = val * 100
while true
work -= 100 if work % 100000 == 100
ans = ans * 10 + (work % 10)
work /= 10
break if work == 0
end
ans = "#{ans}.reverse".to_i
end

[katoy]

"".to_i は 0 になることも利用して、
break をつかわないようにかきかえたら 13秒台がでました。
def mj_arano22(val)
ans = 0
work = val * 100
while work > 0
work -= 100 if work % 100000 == 100
ans = ans * 10 + (work % 10)
work /= 10
end
ans = "#{ans}".reverse.to_i
end

[torisan]

お手数おかけしております。
ここにきて(私の)テスト方法に問題があることがわかりました。

今まで、1から1000000までの数値の処理を実行時間として見ていたのですが
質問文にもありますように最大で９桁の数値が送り値になります。
９桁の数値で1000000回の試行を行った所、
質問文にある最初のコードが一番早いという困ったこと(？)になりました。
なので現在、送り値の値を見て処理をわける、という香ばしいコードになっています。

Answer 2

発想自体はraccyさんと全く同じですが、０以上且つ９桁以下の整数値 で 一桁ずつ調べていき という要件からすると一括で変換するのは難しく、発生し得るパターンを考慮しながら順番に "1" を消しこんで行かねばならないのだと思います。

ruby初心者なのでコーディング方法には無駄やイケていない点があるかもしれませんが、下記のようにすると一応動作するのではないかと思います。

def mj_arano2(arano)
  onara = arano.to_s.reverse
  onara.sub!(/^1$/, '0')
  onara.sub!(/^01$/, '00')
  onara.sub!(/^001$/, '000')
  onara.sub!(/^100/, '000')
  onara.sub!(/^(.)001$/){"#{$1}000"}
  onara.sub!(/^0100/, '0000')
  onara.sub!(/^(..)001$/){"#{$1}000"}
  onara.sub!(/^00100/, '00000')
  onara.sub!(/^(...)001$/,){"#{$1}000"}
  onara.sub!(/^(.)00100/,){"#{$1}000"}
  onara.sub!(/^(....)001$/,){"#{$1}000"}
  onara.sub!(/^(..)00100/,){"#{$1}000"}
  onara.sub!(/^(.....)001$/,){"#{$1}000"}
  onara.sub!(/^(...)00100/,){"#{$1}000"}
  onara.sub!(/^(......)001$/,){"#{$1}000"}
  onara.sub!(/^0+/, '').sub!(/0+$/, '')
  onara.sub!(/^$/, '0')
  return onara.reverse.to_i
end

ひょっとしたら考慮漏れがあるかもしれませんが…
桁数が9桁に満たない場合も含めつつ、reverseすることで下位の桁から順に、条件に当てはまる "1" を消し込んでいます。
処理の終わった下位の桁は、後方参照を利用して保存しています。

結構な行数になってしまったので、どれだけ高速化されるか不明ですが、乗算や除算を何度も繰り返したりループを使用したりするよりは速いのではないかと思います。

Comments

[torisan]

回答ありがとうございます。

正規表現については今までほとんど使う機会がなかったので
少々解読に時間が掛かっております。取り急ぎ、分かった事だけ記述します。

確認した所、時々不要な１が残る時があるようです。
例）
100100001 ->1
100010010 ->1

また、こちらも条件はわかっていないのですが
onara.sub!(/^0+/, '').sub!(/0+$/, '')　の行でエラーになる場合があるようです。
こちらについては２行に分ける事で
(なぜか)通るようなのでそれで対応しました。
onara.sub!(/^0+/, '')
onara.sub!(/0+$/, '')

肝心の時間についてですが、少々掛かってしまう感じでした。
他の方の回答でも書いたのですが
sub! という処理が重いのかもしれませんね。

[torisan]

1が残る原因ですが、
onara.sub!(/^(.)00100/,){"#{$1}000"}など
『00100』などの置き換え後の値が『000』になっていた事が原因のようでした。

onara.sub!(/^(.)00100/,){"#{$1}00000"}などに『00000』に修正した所
(１０件程度しかテストしていませんが)正しい値を返すようになりました。

記号が入り混じっていて難しい印象ですが、対象となるデータが多い時に
非常に役に立ってくれそうな記述ですね。
勉強になりました、ありがとうございました。

Answer 3

うーん、動作要件がいまいちわかりませんが、こんなのでしょうか？

def mj_arano2(i)
  "00#{i}00".gsub(/001(?=00)/, '000').reverse.sub(/\A0+/, '').reverse.to_i
end

たぶん、これでいけると思います。
【修正箇所】
先読みにすることで、孤立した1が出ないようにしました。
subをreverseすることで、たぶん、遅くなる問題は解決したと思います。(正規表現は後方から探すと遅いけど、前方から探すは早い)

Comments

[torisan]

いろいろ試してみた結果、
subの動きが若干ながら重いようでしたのでgsubの記述だけ引用させて頂きました。
最終的なコードは以下になります。

def mj_arano(arano)
arano = "00#{arano}00".gsub(/00100/, '00000').to_i
while (arano % 10) == 0 && arano != 0
arano = arano / 10
end
return arano
end

しかしまさか一行とは……すごいですね。。

[torisan]

お礼を言い忘れるとか……。
回答ありがとうございました！

[torisan]

あわただしくてすみません。
どうも時々孤立した１が残る時があるようです。

説明が難しいのですが、置き換えた箇所は判定から外されるようです。
10010001 ->
001001000100 ->左右に00を加える
000001000100 ->一番左の00100を置き換える、
　　　　　　　　　この時点で置き換えた１～５桁目はgsub判定から外され
　　　　　　　　　次は６～１０桁目から判定する
000001000000 ->次の対象の８～１２桁目を置き換える、最終的に１が残る

６桁目の１も置き換え対象なのですが、
何かいい知恵がありましたら教えていただけると幸いです。

[raccy]

修正しました。先読みにすることでポイントが進まなくなるので、うまくいくと思います。また、subが遅い部分も工夫してみました。どれだけ早くなるかはちょっとわかりませんが…。

[torisan]

お手数おかけしております。
確認しました所、正しい値を返しているようでした。
しかし、subについてはreverse前との変化は残念ながら感じられませんでした。
(尚、for i in 1..1000000 で1000000回の試行のタイムスタンプで判断しています。)
ほぼ同じですが今のコードを載せておきます。
def mj_arano(arano)
arano = "00#{arano}00".gsub(/001(?=00)/, '000').to_i
while (arano % 10) == 0 && arano != 0
arano = arano / 10
end
return arano
end
追記(16/03/21 16:56:00)
{i}になっていたのを{arano}に修正

[raccy]

正規表現ではなくて、標準ライブラリのstrscanを使えばもう少し速くなるかも知れません。ただ、数値計算はかなり速いので単純なところはそちらのコードの方がいいかと思います。

[torisan]

strscanについて調べたのですが
require 'strscan' が通らなかったり(ファイルが必要？)
標準ライブラリ？？？だったり
よしんば通ったとしても置き換え方がわからなかったりで今回は見送ることにしました。
教えていただいたのに申し訳ありません。

gsubについては処理時間の３・４割を削減でき、一番効果があったため
再度BAを付けさせていただきます。ありがとうございました。

Answer 4

#!/usr/bin/env ruby
# -*- encoding:utf-8 -*-

def mj_arano(arano)
    arano_a = ["0", "0", "0", "0"]
    arano_a.insert(2, *arano.to_s.scan(/./))
    temp = []
    arano_a.each_cons(5) do |item|
        if item == ["0", "0", "1", "0", "0"]
            temp << "0"
        else
            temp << item[2]
        end
    end

    #後ろ０の削除(2011200 -> 20112)
    arano_s = temp.join.to_s.sub!(/0+$/,'')

    return arano_s.to_i
end

Comments

[torisan]

いろいろ勉強になる記述がたくさんあって興味深い回答でした。
each_consとか初めて見ました。こんなのもあるんですね。
処理的には少々重めのようでしたので、BAはもう一人の方に付けさせていただきます。
ともあれ、回答ありがとうございました。

Answer 5

私の以前の回答へのコメントで書いた mj_arano22() より速い版 mj_arano23() ができました。
ループ範囲を (100000000..110000000)にした場合の時間は次のようになりました。

mj_arano: 0m22.408s
mj_arano100: 0m35.629s
mj_arano23: 0m11.107s

PAT = '00100'
def mj_arano23(val)
  if "00#{val}00".index(PAT)
    ans = 0
    work = val * 100
    while work > 0
      work -= 100 if work % 100000 == 100
      ans = ans * 10 + (work % 10)
      work /= 10
    end
    return "#{ans}".reverse.to_i
  end

  val /= 10 while (val % 10) == 0 && val != 0
  val
end

def mj_arano100(arano)
  # 孤立の１を削除
  arano = "00#{arano}00".gsub(/001(?=00)/, '000').to_i
  # 後ろ０の削除(2011200 -> 20112)
  arano /= 10 while (arano % 10) == 0 && arano != 0
  arano
end

def mj_arano(arano)
  maisu = [0,0,0,0,0,0,0,0,0,0,0,0,0] # 0 to 12
  maisu[2] = arano / 100000000
  maisu[3] = (arano / 10000000) % 10
  maisu[4] = (arano / 1000000) % 10
  maisu[5] = (arano / 100000) % 10
  maisu[6] = (arano / 10000) % 10
  maisu[7] = (arano / 1000) % 10
  maisu[8] = (arano / 100) % 10
  maisu[9] = (arano / 10) % 10
  maisu[10] =(arano / 1) % 10
  i = 2
  while i <= 10
    if maisu[i]==1 then
      if maisu[i-2]==0 && maisu[i-1]==0 && maisu[i+1]==0 && maisu[i+2]==0 then
        maisu[i] = 0
        i = i + 2 #少しでもループを短くする
      end
    end
    i = i + 1
  end
  arano = 0
  arano = arano + (maisu[2] * 100000000)
  arano = arano + (maisu[3] * 10000000)
  arano = arano + (maisu[4] * 1000000)
  arano = arano + (maisu[5] * 100000)
  arano = arano + (maisu[6] * 10000)
  arano = arano + (maisu[7] * 1000)
  arano = arano + (maisu[8] * 100)
  arano = arano + (maisu[9] * 10)
  arano = arano + (maisu[10] * 1)

  #後ろ０の削除(2011200 -> 20112)
  while (arano % 10) == 0 && arano != 0
    arano = arano / 10
  end

  return arano
end

(100000000..110000000).each do |x|
  mj_arano23(x)
  # mj_arano(x)
end

TESTS = [
  0,
  1,
  10,
  100,
  1010001,
  200010100,
  10010001,
  100100001,
  100010010,
  100100001
]
TESTS.each do |test|
  p "#{test} -> #{mj_arano(test)}, #{mj_arano23(test)}, #{mj_arano100(test)}"
end

実行結果例：

 time ruby 2.rb
"0 -> 0, 0, 0"
"1 -> 0, 0, 0"
"10 -> 0, 0, 0"
"100 -> 0, 0, 0"
"1010001 -> 101, 101, 101"
"200010100 -> 2000101, 2000101, 2000101"
"10010001 -> 0, 0, 0"
"100100001 -> 0, 0, 0"
"100010010 -> 0, 0, 0"
"100100001 -> 0, 0, 0"

real	0m11.107s
user	0m10.713s
sys	0m0.111s

追記： 2016-03-23 22:40
torisan さんの 2016/03/23 20:54 のコメントへのコメントです。

(100000000..110000000).each do |x| ... end
とした場合は、
00100 のパターンがある数字は10万回に1度しか出現しません。
つまり、00100 の処理の時間ではなく、末尾の0 をとる処理のベンチマークになってします。
従って、いかに 00100 が現れていないかを判定して、末尾の 0 をとるかを工夫するだけでベンチマークの成績は良くなってしまうわけです。

そこで、常に 00100 のパターンが現れるように次のようにループさせて計測してみました。

 (1..100).each do |y|
  (100000000..100100000).each do |x|
    ...
  end
 end

その結果は次のようになりました。
mj_arano: 0m22.990s
mj_aranoX: 0m23.718s # 質問文にある 10/03/22 21:44 のコード
mj_arano100: 1m11.066s
mj_arano23: 0m25.935s
mj_arano22: 0m18.171s

mj_arano23 でつかっている
if "00#{val}00".index(PAT)
はそれなりに重い処理なのです。

純粋に 00100 を 00000 に置換して、さらに末尾の 0 をとる処理として一番速いのは mj_arano2 でした。
念のため anaba22() の内容を書いておきます。

def mj_arano22(val)
  ans = 0
  work = val * 100
  while work > 0
    work -= 100 if work % 100000 == 100
    ans = ans * 10 + (work % 10)
    work /= 10
  end
  "#{ans}".reverse.to_i
end

処理するデータの特性 (00100 が現れる割合が判明するば、それに応じてさらに最適化したコードをつくれる気がします)

Comments

[torisan]

なるほど！
対象でない時は処理を行わないというわけですね、盲点でした。
組み込むプログラム上、テストほど対象でないケースが多いわけではないのですが
処理に組み込ませて頂きます。

[katoy]

コメントに書くと長くなるので、回答に追記として書きました。