2011/01/18

Twitterのリツイートの広がり具合を表現しようとしてみた

本日何気なくつぶやいた以下の発言が、リツイートによりどんどん再帰的に広まり、今のところ46人の方にリツイートして頂きました。
自分の中の言語擬人化像。 C++:ツンツン優等生, Java:メガネ委員長, JavaScript:おてんば人気者, Perl:活発八重歯, Ruby:腹黒妹, PHP:パンツ担当, Pascal:メガネ地味, Haskell:ぺろぺろ担当, Erlang:金髪ツインテール双子
リツイートというのは一旦起こると、それが多くの人の興味を引くものであった場合、再帰的に行われ、まるで連鎖反応のようにすごい勢いで広まるようです。
今回は簡単なセルオートマトンモデルを作り、その広まりの様子を視覚的に見てみましょう。
なんかキモイのでちょっと注意してください。

Threshold:





一つ一つのピクセルは一人のツイッターユーザーを表し、その近傍は8近傍とします。
あるユーザーがつぶやいたとき、その近傍のユーザーは一定確率でそのつぶやきをリツイートするものとします。ここで定める確率が、つぶやきの「面白さ」のようなものです。Thresholdの値を変えていろいろ試してみてください。大きいとあっというまに広まりますし、小さいとすぐ止まってしまいます。だいたい0.41付近が広まるか、萎むかの境目のようです。黒ピクセルがリツイートしなかったユーザー。ピンク色がリツイートしたユーザーをあらわしています。

山火事とかがこんなふうに広まるかと思うとちょっと怖いですね。

2011/01/05

Haskellでlist monadを使って完全順列を生成してみました

完全順列(撹乱順列とも)とは順列を置換と見た場合、不動点をもたない置換のことをいいます。順列の要素数を無限大にした極限をとったとき、完全順列の個数(モンモール数)とすべての順列の個数(n!)の比が1:e(eは自然対数の底)になり、世の中の物好きを惹きつけています。
前回のN-Queens問題につづいてlist monadを利用して関数型言語のHaskellで完全順列を生成するコードを書いてみましょう。
*Main> derangement ['c','o','n','s']
>>["ocsn","onsc","oscn","ncso","nsco","nsoc","scon","snco","snoc"]
こんな感じになって欲しいのです。順列を生成した後にfilterを掛けるのは非効率的なのでやめておきます。
書いてみると以下のようになりました。
import Data.List

derangement xs = drg xs xs

drg [] ys = return []
drg xs (y:ys) =
  delete y xs >>=
  \x -> map (x:) (drg (delete x xs) ys)

Monadを利用することを考えると、こんなに簡単に書けるんですね。
素晴らしきかな、Haskell、Monad!

2011/01/03

Haskellでlist monadを使ってN-Queens問題を解いてみました

N-Queens問題は8-Queens問題の一般形で、 N x N のチェスのボード上にN個のクイーンが互いに攻撃しあわないような配置を求める問題です。バックトラッキングアルゴリズムで解くと非常に効率よく解ける例として有名です。
今回はHaskellでlist monadを使って解いてみましょう。List monadを用いることで簡単に楽しく書けるという利点があります。
動機は、いろいろ調べたのですが、Haskellで単純で速そうなものが見つからなかったためです。
アルゴリズムとしては当然バックトラッキング。
クイーンの配置を表すデータ構造としては [Int] を用いましょう。[(Int, Int)]としてしまうと冗長な感があります。経験上データ構造はなるべくダイエットして必要十分に近いものが理想的だと思います。そのほうが簡単に楽しく書けます。

まずlist monadの定義を確認しましょう。List は Monad型クラスのインスタンスです。その定義はGHC.Baseに記載されています。

instance  Monad []  where
  m >>= k             = foldr ((++) . k) [] m
  m >> k              = foldr ((++) . (\ _ -> k)) [] m
  return x            = [x]
  fail _              = []

bind関数>>= がfoldrを使って書かれていますが、xs >>= f = concat (map f xs)と同じことです。
以上から書いてみると、こんな感じになりました。

import Data.List

type Queens = [Int]

nQueens :: Int -> [Queens]
nQueens n = solve [1..n] []

solve :: Queens -> Queens -> [Queens]
solve [] ys = return ys
solve xs ys = 
  xs >>= func 
  where
    func x 
      | isOK (x:ys)  = solve (delete x xs) (x:ys)
      | otherwise    = fail "failed!" 

isOK :: Queens -> Bool  
isOK []  = True
isOK (q:qs)  =  (all (/= 0) . zipWith (-) [1..(length qs)] . (map (abs . (-) q))) qs

速度計測

比較対象
LiteratePrograms.org
pi8027
上のLiteratePrograms.org(以下LPと呼称)のものは同じくバックトラッキングとリストモナドを用いたもの、下のものはしらみ潰し探索法を用いたものです。しらみつぶし探索法は一般には遅いのですが、とてもコーディングしやすいという利点があります。

計測結果(単位:sec)

NEtsukataLPpi8027
90.230.732.73
101.063.8427.33
115.4423.83--

なんで速いの?
しらみ潰し探索法よりもバックトラッキングのほうが速いのは明らかです。
LPよりも自分のものが速いのは、確かめる必要の無い組み合わせを予め省いているからです。メモリの使用量も半分以下で済みます。

もっと速くてわかりやすい書き方がある場合は是非おしえてください!