monoとXamarin StudioでC#
C# を使ってみたかったので，Xamarinで試してみる．
Xamarin とは
Xamarinは，.NETと互換性のある iOS, Android, Mac, WindowsアプリをC#で書くことが可能な，クロスプラットフォーム開発環境です．.NETとの互換は有償ではあるもの、小さいサイズのアプリケーションの開発環境は無償で提供されています。（料金表）
付属する，Xamarin Studioは名前から類推できますが, IDEです．Windows, Mac版が存在しています．
monoとは
monoは，Mac環境におけるC#コンパイラーです．OSSのC#コンパイラで良さげなものはあるのだろうか...
余談１
Xamarinの経緯．Xamarin - wikipediaより．
2000年6月、マイクロソフトは.NET Frameworkをはじめて公表した。Ximianのミゲル・デ・イカザはこのLinux版が実現可能か調査を開始した。その後、2001年6月19日、Monoというオープンソースプロジェクトが立ち上げられた。MonoをサポートしていたXimianは2003年8月4日、ノベルにより買収された。
2011年4月のAttachmate（英語版）によるノベルの買収ののち、Attachmateは数百名にも上るノベル従業員のレイオフを発表した。この中にはMonoの開発者が含まれていた。
同年5月16日、ミゲルは彼のブログにて、Monoを新しい企業Xamarinで開発ならびにサポートすると発表した。
余談2
C# より C Sharp の方が，個人的には字面が良い．
また，googleしてるとC Sharpの表記が多い気もします．
C Sharpを書いてみる
今回は C Sharp を書いてみるのが目的です（ので，Xamarinである必要もないのですが...）．
Xmarin Studioを起動してみるとこんな感じです．
New... より新しいプロジェクトを作ります．
C# > コンソールプロジェクト より新しいプロジェクトを作成します． IDEは割とすっきりした印象 ．
今回は，シンプルにフィボナッチ数を求めるアルゴリズムを実装してみる．
再帰
とりあえず再帰な実装．O(2n)．
public static int fibonacciRecur (int n) { return (n < 2) ? n : fibonacciRecur (n - 1) + fibonacciRecur (n - 2); }
動的計画法
わかりにくいが動的計画法．O(n)．
public static int fibonacciDp (int n) { int a = 0, b = 1; int tmp = 1; for (int i = 1; i < n; i++) { tmp = a + b; a = b; b = tmp; } return (n==0) ? 0 : tmp; }
一般式
いわゆるビネの公式で求められる．O(1)．
public static int fibonacciGe (int n) { return (int)Math.Round(( Math.Pow ((1.0 + Math.Sqrt (5.0)) / 2.0, (double)n) - Math.Pow ((1.0 - Math.Sqrt (5.0)) / 2.0, (double)n) ) / Math.Sqrt (5.0)); }
完全なコード
using System; namespace Fibonacci { class MainClass { public static void Main (string[] args) { if (args.Length != 1) { Console.WriteLine ("Error : Required one integer arg."); return; } int n; try { n = Convert.ToInt32 (args[0]); if (n < 0) { throw new Exception( "Error : Required positive integer." ); }; } catch (InvalidCastException e) { throw e; } Console.WriteLine (fibonacciRecur (n)); // Recursive approach Console.WriteLine (fibonacciDp (n)); // Dynamic programming approach Console.WriteLine (fibonacciGe (n)); // General expression approach } public static int fibonacciRecur (int n) { return (n < 2) ? n : fibonacciRecur (n - 1) + fibonacciRecur (n - 2); } public static int fibonacciDp (int n) { int a = 0, b = 1; int tmp = 1; for (int i = 1; i < n; i++) { tmp = a + b; a = b; b = tmp; } return (n==0) ? 0 : tmp; } public static int fibonacciGe (int n) { return (int)Math.Round(( Math.Pow ((1.0 + Math.Sqrt (5.0)) / 2.0, (double)n) - Math.Pow ((1.0 - Math.Sqrt (5.0)) / 2.0, (double)n) ) / Math.Sqrt (5.0)); } } }
実行
実行方法は，コンソールプロジェクトなので，exeファイルを直接実行する．
# build target によるので，下記のいづれかにexeがあります PROJECT_ROOT/PROJECT_NAME/bin/Debug PROJECT_ROOT/PROJECT_NAME/bin/Release
$ mono Fibonacci.exe 12 144 // Recursive approach 144 // Dynamic programming approach 144 // General expression approach
余談3
新しい言語を学ぶ際に効率的な，Learn X in Y minutes をやろうとしたのですが，接続できず．
仕方ないので，最速マスターシリーズを読んでみた．
おわりに
少しだけ C Sharp を書いてみましたが，この程度ではC Sharpっぽさは分からず．
関連記事
【書評】イシューからはじめよ
大学の図書館で発見したので，手に取ってみた．
要点をかなり簡単にまとめてみる．
バリュー(価値)のある仕事とは何か
本書ではバリューを具体的に定義している．
まずイシューの定義を下記に示す．
イシューとは
A) ２つ以上の集団の間で決着のついていない問題
B) 根本に関わる，もしくわ白黒がはっきりしていない問題
解の質とは
問題解決の方法として素晴らしさ，あるいは時間・労力等
本書では，"問題"をいくつか挙げてみると，その中で実際に解く価値のある問題はごく僅かであり，イシュー度の低い（解く必要のない）問題に対して精一杯努力しても非効率的であると述べている．
つまり，解決すべき問題を明らかにし，その問題に対して取り組むことによりバリューの高い仕事を行うことができると言える．
関連記事
PythonでN-gram
大学の課題で出たので，簡易に実装してみた．
N-gramとは
自然言語処理の素性として良く使われる数量． 1-gram(uni-gram)だと，単語の頻度．2-gram(bi-gram)だと連続する二つの単語の出現頻度，3-gram(tri-gram)だと連続する三つの単語の出現頻度である．
Web文書を対象として，解析してみる．
クローラー
シードとなるURLから，HTML中のhref属性のURLを取得し，深さDまで繰り返し行う．
# coding:utf-8 import json import urllib2 from urlparse import urljoin from BeautifulSoup import * def crawl(pages, depth=2): setpages = set() for i in range(depth): newpages = set() for page in pages: try: c = urllib2.urlopen(page) except: print "Could not open %s" % page continue soup = BeautifulSoup(c.read()) setpages.add(page) links = soup('a') for link in links: if ('href' in dict(link.attrs)): url = urljoin(page, link['href']) if url.find("'") != -1: continue url = url.split('#')[0] if url[0:4] == 'http' and not url in setpages: newpages.add(url) pages = newpages return list(setpages) if __name__ == "__main__": urls = ["http://news.yahoo.co.jp/"] pages = crawl(urls) f = open("./urls.json", "w") json.dump(pages, f) f.close()
N-gram
任意のNを指定し，N以下について計算する．
ベーシックに，形態素解析にはMeCabを，DOM解析にはBeautifulSoup．
# coding: utf-8 import sys import json import MeCab import urllib2 from collections import defaultdict from operator import itemgetter from BeautifulSoup import * class Ngram(): def __init__(self, N=3): self.N = N self.tagger = MeCab.Tagger("-O wakati") def get(self, text, ngram=None): seq = self.tagger.parse(text.encode('utf-8')).split() if ngram is None: ngram = [defaultdict(int) for x in range((self.N + 1))] ngram[0] = None for i in range(len(seq)): for n in range(1, self.N + 1): idx = i - n + 1 # check ngram is valid range if idx >= 0: key_words = [] for j in range(idx, i+1): key_words.append(seq[j]) key = '_'.join(key_words) ngram[n][key] += 1 return ngram class HTMLParser(): def get(self, url): try: c = urllib2.urlopen(url) except: print "Could not open %s" % url return "" soup = BeautifulSoup(c.read()) text = '\n'.join(self.__getNavigableStrings(soup)) return text def __getNavigableStrings(self, soup): if isinstance(soup, NavigableString): if type(soup) not in (Comment, Declaration) and soup.strip(): yield soup elif soup.name not in ('script', 'style'): for c in soup.contents: for g in self.__getNavigableStrings(c): yield g if __name__ == "__main__": f = open("urls.json", "r") urls = json.load(f) f.close() print "Count of urls : " + str(len(urls)) N = 10 hp = HTMLParser() ng = Ngram(N) ngram = None for url in urls: text = hp.get(url) ngram = ng.get(text, ngram) for n in range(1, (N + 1)): f = open('outputs/{:02d}.tsv'.format(n), 'w') out = "" for k, v in sorted(ngram[n].items(), key=itemgetter(1), reverse=True): out += "{}\t{}\n".format(k, v) f.write(out) f.close()
おわりに
とりあえずな実装です．
本当は，先頭と終端に記号が必要だけども...
関連記事
ACM-ICPCアジア地区予選@会津に行って来た．
7月に行われたACM-ICPC2013国内予選を勝ち進み，アジア地区予選に参加してきました．
訳あって，オープン参加となりましたが，充実した３日間を過ごせました．
1日目
今年の会場は会津大学．
夜行バスと電車で，奈良-京都-郡山（福島）-会津・若松まで移動．
郡山駅（福島）
会津・若松駅
初日は，コンテストの説明や，Java challenge, 懇親会等々．
2日目
朝9時から５時間のコンテスト．
四苦八苦しましたが，なんとか最低ラインはクリアできたと思います．
ところで，ICPCのロゴは下記なんですが，これの風船の意味を始めて知りました．
アジア地区予選では，問題と風船の色が対応していて，問題を回答したチームには問題と対応した色の風船が上がるという仕組みになっています．
ですので，左から"悩む"，"アイデアが浮かぶ"，"風船が上がる（回答する）"という意味だと思います．
3日目
帰りの時間まで，会津・若松を散策．
会津武家屋敷
鶴ヶ城
お疲れ様でした．
次世代の”英文を理解する方法”を提供するサービス『Grasphy』
Mashup Awards 9 で，FinalStageに進出 !!
Students賞, 株式会社ハートレイルズ賞を受賞しました．ありがとうございます．
Grasphy とは
Grasphyは，英語での情報収集を効率的に行うことを目的として開発された，次世代の英語読解方法です．英語で書かれた情報を効率的に取得するため，単語の意味情報に加えて，英文法の構造を視覚的に表示します．
英和辞書を主軸とした英文の読解は，文の構造の把握と日本語文の生成を人の脳内で行っていますが，Grasphyは単語の英訳と文構造の把握を，自然言語処理を用いて自動で行い，日本語文の生成だけをユーザにゆだねます．その結果，英語情報の効率的な取得を可能にしています．
さらに，機械翻訳と比べ，文の構造をユーザが把握し，ユーザ自身が日本語文を生成するので，英語の学習や教育といった分野への応用も期待できます．
Grasphy のこれから
英文の文法解析に様々な言語処理技術を導入することや図示方法を工夫することで，より時間効率の高い読解支援を提供することを目指しています．また，Grasphyの基盤技術を活用して，教育向けアプリケーションの開発を視野に入れています．現在は，英日でのユースケースを想定していますが，今後，中，独など多言語への拡張も考えています．
Grasphy の使い方
英文のURLかテキストを入力しEnterを押すだけ．
関連記事
R を用いた相関係数と無相関検定
無相関検定
帰無仮説を「両変数間に相関がない」とする．
p値が p < 0.01, あるいは，p < 0.05 であれば，帰無仮説が棄却され，「両変数間に相関がないとはいえない」となる．
Rでの例
サンプルデータとして，下記の data.tsv を用いる．
下記のデータの一列目と二列目は，明らかに負の相関である．
10 1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 10
次に，Rを用いて無相関検定を行う．
$ R
> data <- read.table('data.tsv', sep='\t')
> cor.test(data[,1], data[,2], method="pearson")
Pearson's product-moment correlation
data: data[, 1] and data[, 2]
t = -134217728, df = 8, p-value < 2.2e-16
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
-1 -1
sample estimates:
cor
-1
p-value は最小値を取り，相関係数は -1 となる．
Rを用いた無相関検定の方法
methodオプションには次の三つがあります．
- "pearson" : ピアソンの積率相関係数
- "kendall" : ケンドールの順位相関係数
- "spearman" : スピアマンの順位相関係数
遺伝的アルゴリズムをやってみた
遺伝的アルゴリズムを Cython で実装してみたGithub．
遺伝的アルゴリズムとは
ざっくりと説明すると，
- 初期値として，N個の個体を無作為に生成する
- 評価関数を用いて，上位のM個の個体を選ぶ（エリート主義）
- 一定の確率に従い，交差や突然変異を行い，N個まで増やす
- 一定回数2~3を繰り返す
今回は交差，突然変異を次のように実装している．
選択の仕方や，交差の仕方などはいくつかの種類があります．
交差
個体A, Bの要素に対して，乱数Rを0~要素数-1の間で発生させ，
A[Begin to R-1] + B[R to End]
上記のよう繋ぎ合わせることで，新たな個体を生成．
突然変異
個体Xのある要素に対して，STEP数（正の整数）を同等の確率で可算または減算する．
X[R] += STEP or X[R] -= STEP
例
Githubに置いている例を紹介．
タスク
５冊の本の中から，読みたい本２冊を１０人に上げてもらう．
それぞれの本は，２冊づつしかない．
全体の満足度を最大化するためには，どのように分配すればよいか？
それぞれが上げた本の組
prefs = [('Alicia', ("The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).", 'Something Wicked This Way Comes')), ('Caesar', ('Do Androids Dream of Electric Sheep?', "I Was Told There'd Be Cake")), ('June', ('Pride and Prejudice and Zombies', 'Do Androids Dream of Electric Sheep?')), ('Gaston', ('Do Androids Dream of Electric Sheep?', "I Was Told There'd Be Cake")), ('Edgar', ('Pride and Prejudice and Zombies', "The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).")), ('Claire', ('Something Wicked This Way Comes', "I Was Told There'd Be Cake")), ('Lana', ("I Was Told There'd Be Cake", 'Pride and Prejudice and Zombies')), ('Kevin', ("The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).", 'Something Wicked This Way Comes')), ('Aaron', ("The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).", 'Something Wicked This Way Comes')), ('Nina', ('Something Wicked This Way Comes', 'Pride and Prejudice and Zombies'))]
出力例
$ python src/example.py (8, [7, 5, 0, 0, 0, 1, 2, 1, 1, 0]) (8, [7, 5, 0, 0, 0, 1, 2, 1, 1, 0]) (8, [7, 5, 0, 0, 0, 1, 2, 1, 1, 0]) (8, [7, 1, 0, 2, 0, 4, 3, 0, 1, 0]) (8, [6, 5, 0, 0, 0, 1, 3, 2, 1, 0]) (7, [7, 1, 0, 0, 0, 1, 2, 1, 1, 0]) (7, [6, 1, 0, 0, 0, 1, 2, 1, 1, 0]) (6, [7, 1, 0, 0, 0, 4, 3, 1, 1, 0]) (6, [6, 1, 0, 0, 0, 4, 3, 1, 1, 0]) (2, [7, 1, 1, 0, 0, 4, 3, 1, 1, 0]) (2, [6, 1, 1, 0, 0, 4, 3, 1, 1, 0]) … Alicia Something Wicked This Way Comes Caesar Do Androids Dream of Electric Sheep? June Pride and Prejudice and Zombies Gaston Do Androids Dream of Electric Sheep? Edgar Pride and Prejudice and Zombies Claire I Was Told There'd Be Cake Lana I Was Told There'd Be Cake Kevin The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy). Aaron The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy). Nina Something Wicked This Way Comes
