質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！

質問する

ただいまの
回答率

88.22%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 3
  • VIEW 755
garchomp

garchomp

score 128

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

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

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

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

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

more_vert9 件の質問への追記・修正依頼

質問への追記・修正、ベストアンサー選択の依頼

  • moke

    moke

    2017/07/28 22:07

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

    キャンセル

  • garchomp

    garchomp

    2017/07/28 22:23

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

    キャンセル

  • moke

    moke

    2017/07/29 00:18 編集

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

    キャンセル

回答 2 件

link

+3

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

link

checkベストアンサー

+1 

# 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


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう！

  • ただいまの回答率 88.22%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる
質問する

関連した質問

同じタグがついた質問を見る

SNSアカウントでログイン

teratailアカウントでログイン

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る