Help us understand the problem. What is going on with this article?

[プログラミング作法]マルコフ連鎖アルゴリズムをrubyで実装してみた

More than 5 years have passed since last update.

最近「プログラミング作法」という本を読んでいます。基本C言語ベースで話が進んでいくんですが、アルゴリズム自体は言語問わず勉強になると思いましたので、rubyで「マルコフ連鎖アルゴリズム」を実装してみました。きっともっといいアルゴリズムがあるはずなので、教えてください(他力本願)

markov.rb
# 番兵(NONWORD)を定義
NONWORD = "\n"

# 標準入力から文章を取得。先頭と末尾に番兵を配置し
# 後処理を単純化
text = [NONWORD, NONWORD] +  STDIN.read.split + [NONWORD]

# == 入力フェーズ
# プレフィクスをキーとし、サフィックスをバリューとするハッシュ配列を作成
# text内の連続する2ワードがプレフィックス。それに続く1ワードがサフィックス
# となるのでtextを3つずつに分割してeachで回す。
h = {}
text.each_cons(3).each do |pre_suf|
  suffix = pre_suf.pop
  prefix = pre_suf
  h[prefix] ||= []
  h[prefix] << suffix
end

# == 出力フェーズ
# 初期値をNONWORDに設定し、それをキーとしてランダムにサフィックスを表示する。
# プレフィクスの先頭を削除、表示したサフィックスを末尾に追加、次のキーとする。
# 上記をサフィックスにNONWORDがくるまで繰り返す。
prefix = [NONWORD, NONWORD]
loop do
  break if h[prefix].last == NONWORD

  suffix = h[prefix][rand(h[prefix].size)]

  print("#{suffix} ")

  prefix.delete_at(0)
  prefix << suffix
end
puts

追記

入力フェーズでサフィックスを+=を使って代入していましたが、<<を使うことで高速化することができたので、修正しました。
本書記載のperlスクリプトとの速度比較で約8倍の差があったので、何かおかしいんだろうと思い調べていたところ、こちらの記事を見つけました。+=は内部処理の関係で配列のインスタンスを再生成するようです。<<に変更したところ、perlスクリプトと同等の速度になりました。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away