僕はJavaのWeakHashMapを勘違いしていたというメモ
JavaにWeakHashMapというクラスがあって、僕はこれをvalueを弱参照で持てるHashMapだと思ってたんですけど、本当はkeyを弱参照で持つHashMapだったのでメモしておきます。
どういうことかって言うと、僕はこんなことを期待していたわけです。
Map<String, String> m = new WeakHashMap<String, String>(); String key = new String("hoge"); String value = new String("fuga"); m.put(key, value); System.out.println(m.containsKey("hoge")); // => true value = null; System.out.println(m.containsKey("hoge")); // => falseとおもってたらtrueだった
valueの強参照がなくなると、mapからそのエントリが削除されるイメージです。
でも、実際はこうでした。
Map<String, String> m = new WeakHashMap<String, String>(); String key = new String("hoge"); String value = new String("fuga"); m.put(key, value); System.out.println(m.containsKey("hoge")); // => true key = null; System.out.println(m.containsKey("hoge")); // => true/タイミング次第でfalse System.gc(); System.out.println(m.containsKey("hoge")); // => false
キーへの強参照をなくして、さらにGCが動いたあとにmapからエントリが削除されるようです。
ideoneに実際動作させたコードを置いておきます。
百人一首でパトリシア木を作った
パトリシア木とは - Wikipedia
ちはやふるのアニメが始まって、気が動転してつくった。後悔はしていない。これを頭に叩き込めばあなたも百人一首マスター?
あ き かせにたなひくくものたえまより もれいつるつきのかけのさやけさ のたのかりほのいほのとまをあらみ わかころもてはつゆにぬれつつ けぬれはくるるものとはしりなから なほうらめしきあさほらけかな さ ちふのをののしのはらしのふれと あまりてなとかひとのこひしき ほらけ ありあけのつきとみるまてに よしののさとにふれるしらゆき うちのかはきりたえたえに あらはれわたるせせのあしろき しひきのやまとりのをのしたりをの なかなかしよをひとりかもねむ は ちしまかよふちとりのなくこゑに いくよねさめぬすまのせきもり れともいふへきひとはおもほえて みのいたつらになりぬへきかな ひみてののちのこころにくらふれは むかしはものをおもはさりけり ふことのたえてしなくはなかなかに ひとをもみをもうらみさらまし ま つかせくものかよひちふきとちよ をとめのすかたしはしととめむ のはらふりさけみれはかすかなる みかさのやまにいてしつきかも ら さらむこのよのほかのおもひてに いまひとたひのあふこともかな しふくみむろのやまのもみちはは たつたのかはのにしきなりけり り あけのつれなくみえしわかれより あかつきはかりうきものはなし まやまゐなのささはらかせふけは いてそよひとをわすれやはする い にしへのならのみやこのやへさくら けふここのへににほひぬるかな ま こむといひしはかりになかつきの ありあけのつきをまちいてつるかな はたたおもひたえなむとはかりを ひとつてならていふよしもかな う かりけるひとをはつせのやまおろしよ はけしかれとはいのらぬものを らみわひほさぬそてたにあるものを こひにくちなむなこそをしけれ お くやまにもみちふみわけなくしかの こゑきくときそあきはかなしき とにきくたかしのはまのあたなみは かけしやそてのぬれもこそすれ ほ えやまいくののみちのとほけれは またふみもみすあまのはしたて けなくうきよのたみにおほふかな わかたつそまにすみそめのそて もひわひさてもいのちはあるものを うきにたへぬはなみたなりけり か くとたにえやはいふきのさしもくさ さしもしらしなもゆるおもひを ささきのわたせるはしにおくしもの しろきをみれはよそふけにける せ そよくならのをかはのゆふくれは みそきそなつのしるしなりける をいたみいはうつなみのおのれのみ くたけてものをおもふころかな き みかため おしからさりしいのちさへ なかくもかなとおもひけるかな はるののにいててわかなつむ わかころもてにゆきはふりつつ りきりすなくやしもよのさむしろに ころもかたしきひとりかもねむ こ ころ あてにおらはやおらむはつしもの おきまとはせるしらきくのはな にもあらてうきよになからへは こひしかるへきよはのつきかな ぬひとをまつほのうらのゆふなきに やくやもしほのみもこかれつつ のたひはぬさもとりあへすたむけやま もみちのにしきかみのまにまに ひすてふわかなはまたきたちにけり ひとしれすこそおもひそめしか れやこのゆくもかへるもわかれては しるもしらぬもあふさかのせき さひしさにやとをたちいててなかむれは いつくもおなしあきのゆふくれ し のふれといろにいてにけりわかこひは ものやおもふとひとのとふまて らつゆにかせのふきしくあきののは つらぬきとめぬたまそちりける すみのえのきしによるなみよるさへや ゆめのかよひちひとめよくらむ せをはやみいわにせかるるたきかはの われてもすゑにあはむとそおもふ た かさこのをのへのさくらさきにけり とやまのかすみたたすもあらなむ きのおとはたえてひさしくなりぬれと なこそなかれてなほきこえけれ このうらにうちいててみれはしろたへの ふしのたかねにゆきはふりつつ ちわかれいなはのやまのみねにおふる まつとしきかはいまかへりこむ まのをよたえなはたえねなからへは しのふることのよはりもそする れをかもしるひとにせむたかさこの まつもむかしのともならなくに ち きり おきしさせもかつゆをいのちにて あはれことしのあきもいぬめり きなかたみにそてをしほりつつ すゑのまつやまなみこさしとは はやふるかみよもきかすたつたかは からくれなゐにみつくくるとは つ きみれはちちにものこそかなしけれ わかみひとつのあきにはあらねと くはねのみねよりおつるみなのかわ こひそつもりてふちとなりぬる な か からむこころもしらすくろかみの みたれてけさはものをこそおもへ らへはまたこのころやしのはれむ うしとみしよそいまはこひしき け きつつひとりぬるよのあくるまは いかにひさしきものとかはしる けとてつきやはものをおもはする かこちかほなるわかなみたかな つのよはまたよひなからあけぬるを くものいつこにつきやとるらむ に しおははあふさかやまのさねかつら ひとにしられてくるよしもかな は えのあしのかりねのひとよゆゑ みをつくしてやこひわたるへき かたみしかきあしのふしのまも あはてこのよをすくしてよとや は な さそふあらしのにはのゆきならて ふりゆくものはわかみなりけり のいろはうつりにけりないたつらに わかみよにふるなかめせしまに る すきてなつきにけらししろたへの ころもほすてふあまのかくやま のよのゆめはかりなるたまくらに かひなくたたむなこそをしけれ ひ さかたのひかりのとけきはるのひに しつこころなくはなのちるらむ と はいさこころもしらすふるさとは はなそむかしのかににほひける もをしひともうらめしあちきなく よをおもふゆゑにものおもふみは ふくからにあきのくさきのしをるれは むへやまかせをあらしといふらむ ほとときすなきつるかたをなかむれは たたありあけのつきそのこれる み か きもりゑしのたくひのよるはもえ ひるはきえつつものをこそおもへ のはらわきてなかるるいつみかは いつみきとてかこひしかるらむ せはやなをしまのあまのそてたにも ぬれにそぬれしいろはかはらす ちのくのしのふもちすりたれゆゑに みたれそめにしわれならなくに よしののやまのあきかせさよふけて ふるさとさむくころもうつなり むらさめのつゆもまたひぬまきのはに きりたちのほるあきのゆふくれ めくりあひてみしやそれともわかぬまに くもかくれにしよはのつきかけ も もしきやふるきのきはのしのふにも なほあまりあるむかしなりけり ろともにあはれとおもへやまさくら はなよりほかにしるひともなし や すらはてねなましものをさよふけて かたふくまてのつきをみしかな へむくらしけれるやとのさひしきに ひとこそみえねあきはきにけり ま かはにかせのかけたるしからみは なかれもあへぬもみちなりけり さとはふゆそさびしさまさりける ひとめもくさもかれぬとおもへは ゆ うされはかとたのいなはおとつれて あしのまろやにあきかせそふく らのとをわたるふなひとかちをたえ ゆくへもしらぬこひのみちかな よ のなか はつねにもかもななきさこく あまのおふねのつなてかなしも よみちこそなけれおもひいる やまのおくにもしかそなくなる もすからものおもふころはあけやらぬ ねやのひまさへつれなかりけり をこめてとりのそらねははかるとも よにあふさかのせきはゆるさし わ か いほはみやこのたつみしかそすむ よをうちやまとひとはいふなり そてはしほひにみえぬおきのいしの ひとこそしらねかわくまもなし す らるるみをはおもはすちかひてし ひとのいのちのをしくもあるかな れしのゆくすゑまてはかたけれは けふをかきりのいのちともかな たのはら こきいててみれはひさかたの くもゐにまかふおきつしらなみ やそしまかけてこきいてぬと ひとにはつけよあまのつりふね ひぬれはいまはたおなしなにはなる みをつくしてもあはむとそおもふ をくらやまみねのもみちはこころあらは いまひとたひのみゆきまたなむ
Amazon Elastic MapReduceで日本語のwordcountを試した時のメモ #jawsug
Amazon Elastic MapReduceで日本語のwordcountを試したので、備忘録的な意味も込めてその時のメモをまとめます。pythonで書いてますが、形態素解析のライブラリがあればどの言語でも大丈夫だと思います。
目次
Amazon Elastic MapReduce Ruby Clientインストール
http://aws.amazon.com/developertools/2264 からダウンロードしてきます。
$ wget http://elasticmapreduce.s3.amazonaws.com/elastic-mapreduce-ruby.zip $ unzip -d elastic-mapreduce-ruby elastic-mapreduce-ruby.zip $ sudo cp -r elastic-mapreduce-ruby /opt/elastic-mapreduce-ruby $ export PATH=$PATH:/opt/elastic-mapreduce-ruby
credentials.json作成
以下の内容でcredentials.jsonを作成します。
$ cat /opt/elastic-mapreduce-ruby/credentials.json { "access-id" : "<AWSのアクセスキー>", "private-key" : "<AWSのシークレットアクセスキー>", "key-pair" : "<キーペアの名前>", "key-pair-file" : "<秘密鍵(***.pem)>", "log-url" : "s3n://<バケット名>/logs/" }
key-pairを指定してると後述の方法でマスターノードにSSH接続ができるので、指定してたほうが便利に使えます。
hadoopの設定
今回はS3にファイルを転送するためにhadoopコマンドを使います。別の方法で出来る人はそれでもいいと思います。
hadoopインストール
http://hadoop.apache.org/common/releases.html#Download から辿って適当なバージョンを拾ってきて解凍してパスを通せば、とりあえず今回必要な機能は使えます。僕は0.20.204を使いました。
$ wget http://ftp.kddilabs.jp/infosystems/apache//hadoop/common/hadoop-0.20.204.0/hadoop-0.20.204.0-bin.tar.gz $ tar xvf hadoop-0.20.204.0-bin.tar.gz $ sudo cp -r hadoop-0.20.204.0/ /opt/hadoop $ export PATH=$PATH:/opt/hadoop/bin
HDFSのバックエンドにS3を使う
Elastic MapReduceを使う前にやっとくと幸せになるかもしれない設定 を参考に、HDFSのバックエンドにS3が使えるようにします。
形態素解析エンジンIgo用の辞書構築
http://igo.sourceforge.jp/ を参考に、辞書ファイルを構築します。
http://sourceforge.jp/projects/igo/releases/ から igo-0.4.3.jar を選んでダウンロードして下さい。
http://sourceforge.net/projects/mecab/files/mecab-ipadic/2.7.0-20070801/ から mecab-ipadic-2.7.0-20070801.tar.gz を選んでダウンロードして下さい。
$ tar xvf mecab-ipadic-2.7.0-20070801.tar.gz $ java -cp igo-0.4.3.jar net.reduls.igo.bin.BuildDic ipadic mecab-ipadic-2.7.0-20070801 EUC-JP
できた辞書ファイルをS3に配置します
$ hadoop fs -put ipadic s3n://<バケット名>/ipadic
bootstrap.sh作成
Elastic MapReduceのjobflowを作る際に、最初に一度だけ実行されるスクリプトを作成します。このスクリプトの中で、必要なファイルをS3から持ってきたり、モジュールをインストールすることができます。
#!/bin/bash WORKDIR=/mnt/var/lib/hadoop/tmp S3ROOT=s3n://<バケット名> # 必要なファイルをDLする cd $WORKDIR hadoop fs -get $S3ROOT/ipadic . # 実行環境を整える sudo easy_install igo-python
bootstrap.shをS3に配置します
$ hadoop fs -put bootstrap.sh s3n://<バケット名>/bootstrap.sh
mapper.py作成
MapReduceのMapの部分を行うプログラムを記述します。今回は名詞だけを取り出すようにしました。
# *-* coding: utf-8 *-* import sys import codecs from igo.Tagger import Tagger sys.stdin = codecs.getreader('utf-8')(sys.stdin) sys.stdout = codecs.getwriter('utf-8')(sys.stdout) dic = '/mnt/var/lib/hadoop/tmp/ipadic' tagger = Tagger(dic) for line in sys.stdin: line.strip() tokens = tagger.parse(line) for token in tokens: if not u"名詞" in token.feature continue print "%s\t1" % token.surface
mapper.pyをS3に配置します。
$ hadoop fs -put mapper.py s3n://<バケット名>/mapper.py
reducer.py作成
MapReduceのReduceの部分を行うプログラムを記述します。Mapの出力がそのまま入力になって入ってきます。
# *-* coding: utf-8 *-* import sys import codecs sys.stdin = codecs.getreader('utf-8')(sys.stdin) sys.stdout = codecs.getwriter('utf-8')(sys.stdout) tokens = {} for line in sys.stdin: token, count = line.split("\t") tokens[token] = tokens.get(token, 0) + int(count) for token, count in tokens.items(): print "%s\t%d" % (token, count)
reducer.pyをS3に配置します。
$ hadoop fs -put reducer.py s3n://<バケット名>/reducer.py
入力ファイル作成
解析したい文章をファイルに書いて保存します。僕は以下の内容にしました。
$ cat input.txt 今日の天気は晴れです。 天気がいいので歌を歌います。 お腹が空いたので今日は帰ります。 お腹が痛くなりそうなので明日は遅刻するつもりです。 天気予報を信じるなら、明日の天気は曇りでしょう。
input.txtをS3に配置します。
$ hadoop fs -put input.txt s3n://<バケット名>/input/input.txt
jobflow作成
jobflowを作成すると、EC2のインスタンスが起動して待機状態になります。
$ elastic-mapreduce --create --alive --bootstrap-action s3n://<バケット名>/bootstrap.sh <JobFlowIDが表示される>
step追加
jobflowにstepを追加すると、自動的に実行されます。
$ elastic-mapreduce --jobflow <JobFlowID> --stream --input s3n://<バケット名>/input/input.txt --mapper "python s3n://<バケット名>/mapper.py" --reducer "python s3n://<バケット名>/reducer.py" --output s3n://<バケット名>/out
処理結果確認
処理の結果がS3に保存されているので、内容を確認します。
$ hadoop fs -cat s3n://<バケット名>/out/* | sort -rk 2 天気 4 明日 2 今日 2 お腹 2 予報 1 遅刻 1 晴れ 1 歌 1 つもり 1 そう 1
jobflow停止
無事に処理がすんだらjobflowを停止しましょう。停止しないとEC2のインスタンスが起動したままになり、ずっと課金されます。
$ elastic-mapreduce --jobflow <JobFlowID> --terminate
Tips
簡易テスト
mapperとreducerができたら以下のコマンドで動作確認をしておくとGoodです。
$ echo "すもももももももものうち" | python mapper.py | python reducer.py うち 1 すもも 1 も 2 もも 2 の 1
jobflowの一覧や、stepの実行状態を確認する
以下のコマンドで確認することができます。
$ elastic-mapreduce --list
マスターノードへのSSH接続
credentials.jsonにkey-pairの情報を正しく設定していれば、以下のコマンドでマスターノードに接続することができます。一度ログインして、どういう環境になっているかを確認してみるといいでしょう。
$ elastic-mapreduce --ssh <JobFlowID>
ログはマスターノードの以下のパスに出力されます。syslogをtailすることで実行状態をリアルタイムに見ることができます。
$ ls /mnt/var/log/hadoop/steps/<step番号>/ controller stderr stdout syslog $ tail -f /mnt/var/log/hadoop/steps/<step番号>/syslog
クイックリファレンス
http://aws.amazon.com/jp/documentation/elasticmapreduce/ のAmazon Elastic MapReduce Quick Reference Cardを印刷して持っておくと、何かと便利です。
AOJ 0030 Sum of Integers
import java.util.Scanner; public class Main { private static Scanner s = new Scanner(System.in); public static void main(String[] args) { while (true) { int[] in = nextInput(); if (in[0] == 0 && in[1] == 0) { break; } System.out.println(soi(in[0], in[1], -1)); } } static int soi(int n, int s, int i) { if (n == 0) { return (s == 0) ? 1 : 0; } int a = 0; int l = Math.min(s, 9); for (i = i + 1; i <= l; i++) { a += soi(n - 1, s - i, i); } return a; } static int[] nextInput() { int[] input = new int[2]; for (int i = 0; i < 2; i++) { input[i] = s.nextInt(); } return input; } }
AOJ 0033 Balls
頻出典型アルゴリズムの演習問題としてよさげなやつ を上から順に解いていこう企画。
最初の問題は「AOJ 0033 Balls」
深さ優先探索って書いてあったけど、これでいいのかな。
import java.util.Scanner; public class Main { private static Scanner s = new Scanner(System.in); public static void main(String[] args) { int n = s.nextInt(); for(int i=0; i<n; i++) { int[] ballSet = nextInput(); System.out.println(isSortable(ballSet) ? "YES" : "NO"); } } public static boolean isSortable(int[] ballSet) { int bufB = 0; int bufC = 0; for(int ball : ballSet) { if(ball > bufB) { bufB = ball; } else if(ball > bufC) { bufC = ball; } else { return false; } } return true; } public static int[] nextInput() { int[] input = new int[10]; for(int i=0; i<10; i++) { input[i] = s.nextInt(); } return input; } }
isSortableという名前が気に食わない。
#jawsug Elastic MapReduceを使う前にやっとくと幸せになるかもしれない設定
Elastic MapReduceを使ってると何でもかんでもS3にアップロードさせられるので、いちいちManagementConsoleからアップロードするのは結構面倒です。ローカルにHadoopをインストールして、$HADOOP_HOME/conf/core-site.xmlに以下の設定を追加すると、HDFSのバックエンドにS3を使うことができて便利ですよ。
<?xml version="1.0"?> <?xml-stylesheet type="text/xsl" href="configuration.xsl"?> <configuration> <property> <name>fs.s3n.awsAccessKeyId</name> <value>[AWS_ACCESSKEY_ID]</value> </property> <property> <name>fs.s3n.awsSecretAccessKey</name> <value>[AWS_SECRET_ACCESSKEY]</value> </property> </configuration>
使い方
$ # S3にファイルを置く場合 $ hadoop fs -put <S3に置きたいファイル> s3n://<バケット名>/<ファイルを置きたい場所> $ # S3のファイルの内容を表示したい場合 $ hadoop fs -cat s3n://<バケット名>/<表示したいファイル>
具体的にはこんな感じで使えます。
$ # S3に置くファイルはこんな感じ $ cat hogehoge.txt hello elastic mapreduce $ # 実際にS3に置いて内容を表示してみる $ hadoop fs -put hogehoge.txt s3n://yourbucket/any/prefix/of/hogehoge.txt $ hadoop fs -cat s3n://yourbucket/any/prefix/of/hogehoge.txt hello elastic mapreduce
機械学習の基礎、パーセプトロンをRubyで作って学んだ
機械学習超入門III 〜機械学習の基礎、パーセプトロンを30分で作って学ぶ〜 を読んでRubyで書いてみました。
以下ソースコード
module MachineLearning class Perceptron attr_reader :w def initialize w={} @w = w end def predict vector_x vector_x.reduce(0) do |y, v| k, x = v (w[k]) ? y + (w[k]*x) : y end end def train vector_x, t y = predict(vector_x) return unless (y*t) < 0 vector_x.each do |k, x| w[k] += t * x end end end end # 訓練データ # 暖色 => 1 # 寒色 => -1 train_data = [ [{:R => 255, :G => 0, :B => 0, :bias => 1}, 1], [{:R => 0, :G => 255, :B => 255, :bias => 1}, -1], [{:R => 0, :G => 255, :B => 0, :bias => 1}, -1], [{:R => 255, :G => 0, :B => 255, :bias => 1}, 1], [{:R => 0, :G => 0, :B => 255, :bias => 1}, -1], [{:R => 255, :G => 255, :B => 0, :bias => 1}, 1], ] machine = MachineLearning::Perceptron.new({:R => 0, :G => 0, :B => 0, :bias => 1}) # 訓練パート 10.times do train_data.each do |x, t| machine.train(x, t) end end # 推定パート puts "color codeを入力して下さい (例) 102 204 255" while (print "> "; input = gets) do input = input.chomp.strip break if input == 'q' next unless input =~ /^\d{1,3} +\d{1,3} +\d{1,3}$/ r,g,b = input.split(' ').map{|s| s.to_i} x = {:R => r, :G => g, :B => b, :bias => 1} t = machine.predict(x) case when t >= 0 puts "=> 暖色 [#{t}]" else puts "=> 寒色 [#{t}]" end end
機械学習って本を読んでもあんまりイメージわかなかったんですけど、こうやって手を動かすとなんとなくわかるもんですね。