ruby アルゴリズム的に遅いみたい。どうしたら早くなるかが見当もつきません。

Question

とあるプログラムを組んでみましたが…
一応自力で（最終的に正解まで行けるプログラム）はくめました。

ただ、量が多いとあまりにも時間がかかってしまいます。

つまり、これはアルゴリズム的に間違っていると思いますが、どこをどう見直したらいいのかがわかりません…

コードは以下の通りです。

deal=gets.chomp
readys=[]
count=0
while n=gets.to_s.chomp!
	if n==""||n.nil?||n=="nil"
		break
	else
		readys.push(n)
		count+=1
	end
end
sets=readys.map{|x| x.to_i}
#p count
#p sets

all_combi=[]
sets.count.times{|i| all_combi+=sets.combination(i+1).to_a}
#p all_combi
nums=all_combi.length
last_count=0
for i in 0..nums-1 do
	conbis=all_combi[i]
	
	if conbis.one?
		last_count+=1 if conbis[0]>deal.to_i
	else
		last_count+=1 if conbis.inject{|sum,i| sum+i}>deal.to_i
	end
end

puts last_count

アルゴリズム的に良いコードを書くにはどうしたらいいのでしょうか？
また、アルゴリズムに関しては経験を積むよりも、基礎知識をしっかり押さえるほうが先決でしょうか？

Comments

[moke]

Ruby的にえってコードが、沢山あるので、何がしたいか、解読するのが大変です。出来れば何のアルゴリズムかも書いて下さい。

[garchomp]

入力で、一行目にホストとなる数字が与えられます。二行目以降にそれぞれ数が与えられます。あらかじめ何行とは書かれていません。　　二行目以降に与えられた数字で、一行目の数字を超える組み合わせはいくつあるのかを出力するプログラムです。

[garchomp]

今回の場合は、一行目に取得した数字をそのまま変数にセットし、二つ目以降の数字をループで回して、入力がなくならない限りは数字を配列にセットしています。取得した状態ではstringですので、intergerに変換し、all_combiで、多くの配列を一つの配列にまとめた次元配列にしています。その後配列の中身が一つだけならそのまま、二つ以上あるなら合計数を求め、それぞれホストの番号を上回っていたらカウントをしています。

[moke]

すみません今出先なので、全ての組み合わせをやる必要はありません。こえない数を数えて全体2^nから引くというのは如何でしょう

[moke]

最初に 文字列にしてというのもナンセンスです

[garchomp]

最初の取得時に数字のまま可能でしょうか？あるいはchompの後にto_iをつける感じでしょうか？

[moke]

帰りました、ところで、数字は重複があるのでしょうか？これでだいぶ変わります。

[garchomp]

一応ありを想定していますが、だいぶ変わるのであれば参考に2パターン見てみたいです。

[moke]

むむぬ、重複無しなら、数行にまとめられると思ったのですが...。重複ありだとまあ普通にやるしかないですね。suzukis様の回答でいいと思います

Answer 1

プロファイルしてませんがおそらく時間がかかってるのは

sets.count.times{|i| all_combi+=sets.combination(i+1).to_a}

ここではないかなと想像します。(本来は想像ではなくまずプロファイルを取るべきです)

可能な全ての組み合わせを生成して一旦保存し、あとからそれをスキャンして合計値を出していますが、これは2つの意味でまずいことがあります。

• 重要なのは合計なので、組み合わせそのものを保存しておく必要性はない
• 自明に条件に適合する、または自明に条件に適合しない組み合わせも生成する

後者をもう少し説明すると、たとえばdealが3で、readysが[1,3,5]であれば、5を含む組み合わせは自明に3を越えます。そこで「5を含む組み合わせ」+「5を含まない組み合わせ」に分割できないか、と考えられます。そして、「5を含む組み合わせ」の数を数学的に計算できれば、「5を含む組み合わせ」を生成するコストはほぼ0にできます。これが問題の分割と枝刈りの考え方です。

これは考え方の1例で分割の仕方や枝刈りの方法は他にも考えられます。こういうのは経験も知識も両方いります。割と数学の知識は要求されるので、勉強しておいて損はないと思います。「プログラマの数学」という本はタイトルの通りの本なので、一読をお勧めします。

(なお上の説明でこっそり入力が非負という前提を置いていますが、非負に限定しなくても数学的に非負に限定された問題に変換できます)

Answer 2

# encoding: utf-8

a = [1, 2, 3, 4, 5, 6, 7]
# a = Array.new(100).map { rand(1000) }
x = 4

begin
  c = 0
  a.size.times do |m|
    a.combination(m + 1).each do |e|
    c += 1 if e.inject(:+) > x
    end
  end
  puts "全パターン生成：#{c}" 
rescue
  # Do Nothing!!
end

all_patern = 0

a.size.times do |m|
  all_patern +=
  ((a.size - m)..a.size)
  .to_a.inject(:*) / (1..(m+1)).to_a.inject(:*)
end

b = a.select { |e| e <= x }

b.size.times do |m|
  b.combination(m+1).each do |n|
    all_patern -= 1 if n.inject(:+) <= x
  end
end

puts "計算併用：#{all_patern}" 

実行結果例

全パターン生成：121
計算併用：121

suzukis様のお話を参考に考えてみました。
私は数学が一切分からないので、正解かどうかは分かりません。

確認のために全パターンを生成して数えるコードも書いています。
a = Array.new(100).map { rand(1000) }を使用した場合、
全パターンを生成して数えるコードは動かなくなります。
下のコードは動く場合があります。
時間がかかるので、試す場合は全パターンを生成して
数えるコードを削除してください。

重複無しの全組み合わせの数を出してそこから
基準となる数字（一番初めに入力される数）以下の
数の組み合わせの内、合計したときに基準となる数字以下になる
組み合わせの数を引いています。

私のコードはある場合に組み合わせを行う
回数を減らしているだけなので

Array.new(100).map { rand(2) }
x = 4

等の場合、組み合わせを行う回数を減らせず
動かなくなります。