2013-12-31

Barnes-Hutのアルゴリズムについて

はじめに

グラフを描こうと思い、力学モデルについて調べていたらBarnes-Hutのアルゴリズムという手法を見つけたのでためしに書いてみたメモ。
ノード間の相互作用を計算するときに計算量を減らすためのアルゴリズム。
多体問題のシミュレーションに使うのかなと期待したけどそんなことはなかった。(計算が全く厳密でない)

サンプルをgistに上げました。(https://gist.github.com/domitry/7214402)
Processingがあればそのまま動きます。
Processingというか、Javaを初めてまともに書いたので使い勝手がよくわからなかった。
Rubyで書き直そうかなあと思いつつrcairoでウィンドウに描画するのが予想以上にめんどくさかったので挫折。

参考url

The Barnes-Hut Algorithm - arborjs.org
http://arborjs.org/docs/barnes-hut
詳しい解説が載っているのでこれを読めばわかります。

A hierarchical O(N log N) force-calculation algorithm - nature
http://www.nature.com/nature/journal/v324/n6096/abs/324446a0.html
元の論文。

アルゴリズム

空間を再帰的に4分割していき、1つの領域に1つの質点が収まるようにする。
この分割を元に4分木を作る。
ある質点より十分離れた領域に所属する質点との相互作用を計算するときは、領域に属する質点の重心との相互作用として計算する。

詳しくは参考url1(http://arborjs.org/docs/barnes-hut)をご覧ください。

サンプル

f:id:domitry_h:20131231181223p:plain
初期条件が悪いと汚いグラフができるのでKamada-Kawaiのアルゴリズム等でうまい初期条件を見つける工夫が必要。

2013-12-23

mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの?② (完結編, mrubyとLuaの文字列連結の違い)

VM mruby

これはカーネル/VM Advent Calendar 2013の記事です。

最近本業(大学生)の方が忙しくなかなかコードが書けない@domitryです。
当初はmrubyとLuaを比較してみて似ている点や違う点を挙げて記事にしようと思っていたのですが、時間と知識が足りず断念しました。
前回の記事(http://domitry.hatenablog.jp/entry/2013/12/08/002426)の続きになります。
続き物の記事の2つ目をAdvent Calendarのネタにしてしまいましたが、前回の内容とほとんど関連のない記事ですのでご容赦ください。

2013-12-08

mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの? ① (あるいはJavaの文字連結最適化について)

VM mruby 論文の記録

前置き

最近色々ありましてmrubyやKopiLua(C#によるLua実装)のソースコードを読んだりしております。
ちょうどVM部分を読んでいたら、面白い部分を見つけました。

mrubyのバイトコードにOP_STRCAT(文字連結)っていうのがあるのに驚いてたけど, LuaVM読んでたらOP_CONCATとかあったし文字連結系のオペコード用意するのって普通なんです…?
— どみとり (@domitry) 2013, 12月 5

これまでx86のアセンブラしか読んだことがなかったので特殊かどうかよくわからない…
そこでふとLL言語でない, 例えばJavaのVMはどうなってるんだろうなーと思い調べてみました。

昨日のお話、Javaのバイトコードを見てみたらstrcatやらconcatはなかった… キャストとかオブジェクト指向な要素(newとかclass method呼び出しとか)とかは含まれてた。
— どみとり (@domitry) 2013, 12月 6

とそこで

@domitry はやく String Concatenation Optimization on Java. Bytecodeとかいう論文を読むんだ！
— こんにちは。0x19歳です (@naota344) 2013, 12月 6

というわけでこの論文を読んでみたのでメモも兼ねてまとめてみます。

2013-08-30

セキュリティ・キャンプ2013中央大会に参加してきました③

参加記

最後にセキュリティキャンプで作ったものの説明を付けて終わりにします。

2013-08-30

セキュリティ・キャンプ2013中央大会に参加してきました②

参加記

ちょっと忙しくなって①から間が空いてしまいましたが続きを書きます。
特に来年度以降参加しようと思っている人たちに何かの参考にしていただけるとうれしいです。

2013-08-20

セキュリティ・キャンプ2013中央大会に参加してきました①

参加記

突然ですが8/13～17の5日間、セキュリティ・キャンプ2013に参加してきました。

セキュリティ・キャンプとはIPAとセキュリティ・キャンプ実施協議会が毎年行っている、将来のセキュリティ人材を育てることを目的としたイベントです。
様々な場所で関連イベントがあり、夏には千葉の幕張で中央大会が開かれました。
くわしくはこちらをご覧ください。
https://www.ipa.go.jp/jinzai/renkei/camp2013/index.html

私はこの中のセキュアなシステムをつくろうクラス、セキュアなOSをつくろうゼミに所属していました。
朝から夜までコーディングしたりプレゼンの内容を考えたりその資料を作ったりと頭をフルにつかった5日間でした。
事前学習期間を含めた3か月間ずっとOSとセキュリティについて考えることで勉強になりましたし、すごい実力を持った人たちの作業を間近で見ることで大変な刺激になりました。

本当はかなり詳しく書かないといけないのですが、夜にそんな文章を書くと下手な自分語りのようになってしまう傾向があるのでとりあえずまず報告の記事だけ書かせていただきます。

2013-06-11

Rubyで形態素解析

Ruby 自然言語処理

最近そこそこに忙しくてなかなか自由時間がとれないのでコード書きたい欲が大分溜まっています。

そんなところに大学の自然言語処理を扱う授業の輪講の順番が回ってきたので、スライドを作るついでにデモプログラムを書くことにしました。

どうも自然言語処理の分野ではPythonが強くRubyにはあまりライブラリが充実していないらしいのですが、父親から授けられた「まつもとゆきひろコードの世界」が本棚からオーラを放っていたのでRubyで書いてみることに。

やっていること

形態素解析。辞書データをもとに文章をばらばらにします。

NAIST辞書
http://sourceforge.jp/projects/naist-jdic/

から単語のデータをいただいて、見出し語と単語コストだけ抜き出して辞書ファイルを作りました。
それをHashに読み込んで使っています。

以下メソッドの説明。

longestMatch(string)

最長一致法。その名の通り文中で一番長い単語から確定していく手法。
再帰で実装。

smallestCost(string)

接続コスト最小法の似非実装。
単語の接続にかかるコストの和が最小になるように分割します。
NAIST辞書から文法の情報をごっそり抜き取ってるので品詞間のコストを全く考えていません。
DPを使って実装している、はず。

これらの手法について詳しくは輪講の資料をご覧ください。
http://www.slideshare.net/domitry/8-22801849

問題点

未知語への対応をほとんど考えていない

最長一致法では未知語には一応かっこをつけていますが、接続コスト最小法に至っては適当に1文字で分割しているだけです。
しかしこれの対策だけでひとつ分野があるくらいなので今回はパス。

動詞の活用展開ができない

これは実用面で致命的。辞書データを変換するときについでに展開しておくべきだった？

使い方

辞書をカレントフォルダに置いて適当にNltkのインスタンスを作ってつっこんでもらえれば動きます。
辞書データは[見出し語,コスト]の順番。

class Nltk
	def initialize
	  file = open(File.expand_path("../normal.dic",__FILE__),"r:UTF-8")
	  @dic = Hash.new
	  file.each{|line|
	    line.chomp!
            line =~ /(\W+),(\d+)/
            @dic[Regexp.last_match(1)] = Regexp.last_match(2).to_i
	  }
	end

	def longestMatch(string)
          if string.empty?
	    return []
	  end
	  max_len = string.length<5 ? string.length : 5
          max_len.downto(1) {|len|
	    for seek in 0..(string.length-len) do
	      tmp = string[seek,len]
	      if @dic.key?(tmp.encode("UTF-8"))
                prefix = longestMatch(string[0,seek])
	        safix = longestMatch(string[seek+len,string.length-seek-len])
                return prefix + [tmp] + safix
	      end
	    end
	  }
	  #not found in dic
	  return ["("+string+")"]
	end


        def getAllWords(string)
            #get all words contained in string
            words = Array.new(string.length)
            for seek in 0..string.length-1 do
              words[seek] = Array.new
              max_len = string.length-seek < 5 ? string.length-seek : 5
              max_len.downto(1){|len|
                tmp = string[seek,len]
                if @dic.key?(tmp.encode("UTF-8"))
                  words[seek].push(tmp)
                end
              }
            end
            return words
        end

	def smallestCost(string)
          words = getAllWords(string)
          #get all combinations
          combs = Array.new(string.length)
          (string.length-1).downto(0){|seek|
            combs[seek]=Array.new
            #unresistered word
            if words[seek].empty?
              words[seek].push(string[seek])
            end
            words[seek].each do |word|
              cost = @dic[word.encode("UTF-8")]
              if cost == nil
                cost　=　0
              end
              if seek + word.length == string.length
                combs[seek].push([word,cost])
              else
                combs[seek+word.length].each do |comb|
                  tmp = [word]+comb
                  cost_sum = tmp.pop + cost
                  tmp.push(cost_sum)
                  combs[seek].push(tmp)
                end
              end
            end
          }
          return combs[0]
          end
    end

2013-04-28

5月目標

最近やりたいことが発散気味なのでまとめ。

1.必須

・avr・cadのお勉強(ロボコン関連)

・opencvでpocky箱認識(ロボコン関連)

・大学の課題を処理する

2.努力

・Rubyのお勉強

・アルゴリズムのお勉強

・C++の書き方を改良する(EffectiveC++？)

3.できれば

・アセンブラのお勉強