2010年12月15日水曜日

pythonのリストでunique(修正)

バイナリ辞書を作る処理でリストをsort+uniqueする必要があり、pythonでどうやろうか考えてみた。

sortする必要があるため、元のリストの順番を維持する必要がないので、itertools.groupbyを使って素直に出来た。そのあとset+sortでもっと素直に出来た…

ついでに順番の維持が必要な場合も考えた。ソート済みの配列に既にその要素があるか、または(性能的な理由から)setで覚えて確認するのがすぐ思いついたのでやってみた。

テストプログラム
import itertools
import hotshot, hotshot.stats
from random import randint


f1 = lambda l: [i for i, g in itertools.groupby(sorted(l))]

def f2(l):
    l2 = []
    for i in l:
        if not i in l2:
            l2.append(i)
    return l2

def f3(l):
    l2 = []
    s = set()
    for i in l:
        if not i in s:
            s.add(i)
            l2.append(i)
    return l2

f4 = lambda l: sorted(set(l))


for l in ([5,4,3,2,1,1,2,3,4,5,10,5,4,3,2,1,10] * 100000,
          [randint(0, x) for x in range(500)],
          [randint(0, x) for x in range(1000)],
          [randint(0, x) for x in range(10000)],
          [randint(0, x) for x in range(50000)]):
    print "orig:", l[:10], "size:", len(l)
    for f in (f1, f2, f3, f4):
        prof = hotshot.Profile('uniq.prof')
        l2 = prof.runcall(f, l)
        prof.close()
        print "result:", l2[:10], "size:", len(l2)
        stats = hotshot.stats.load('uniq.prof')
        stats.strip_dirs()
        stats.print_stats(5)


  • わざとuniqueな件数が減るようにしています(小さい数の方が多くなる)
  • f1とf4がsortedかつunique
  • f2とf3が順番を維持するunique
  • f1 sorted+groupby
  • f2 リストを使って追加済み要素をチェック
  • f3 setで追加済み要素をチェック
  • f4 setにしてsorted


結果要約
  • f4がやっぱり速い
  • f2は予想通り遅くなる
  • f1はそれほど悪くない気がするが、f4には負ける
表にしたもの

6/1700000 251/500 501/1000 5007/10000 24967/50000
f1 0.514 0 0 0.005 0.055
f2 0.303 0.001 0.004 0.468 11.787
f3 0.19 0 0 0.003 0.023
f4 0.069 0 0 0.001 0.014

結果全文
hideaki@siduxbox:~$ python uniq.py 
orig: [5, 4, 3, 2, 1, 1, 2, 3, 4, 5] size: 1700000
result: [1, 2, 3, 4, 5, 10] size: 6
         1 function calls in 0.514 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.514    0.514    0.514    0.514 uniq.py:6(<lambda>)
        0    0.000             0.000          profile:0(profiler)


result: [5, 4, 3, 2, 1, 10] size: 6
         1 function calls in 0.303 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.303    0.303    0.303    0.303 uniq.py:8(f2)


result: [5, 4, 3, 2, 1, 10] size: 6
         1 function calls in 0.190 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.190    0.190    0.190    0.190 uniq.py:15(f3)


result: [1, 2, 3, 4, 5, 10] size: 6
         1 function calls in 0.069 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.069    0.069    0.069    0.069 uniq.py:24(<lambda>)


orig: [0, 1, 1, 3, 3, 4, 4, 0, 3, 8] size: 500
result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 251
         1 function calls in 0.000 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 uniq.py:6(<lambda>)
        0    0.000             0.000          profile:0(profiler)


result: [0, 1, 3, 4, 8, 11, 9, 12, 5, 16] size: 251
         1 function calls in 0.001 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.001    0.001 uniq.py:8(f2)


result: [0, 1, 3, 4, 8, 11, 9, 12, 5, 16] size: 251
         1 function calls in 0.000 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 uniq.py:15(f3)


result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 251
         1 function calls in 0.000 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 uniq.py:24(<lambda>)


orig: [0, 1, 1, 0, 3, 3, 4, 7, 2, 8] size: 1000
result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 501
         1 function calls in 0.000 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 uniq.py:6(<lambda>)
        0    0.000             0.000          profile:0(profiler)


result: [0, 1, 3, 4, 7, 2, 8, 9, 5, 17] size: 501
         1 function calls in 0.004 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.004    0.004    0.004    0.004 uniq.py:8(f2)


result: [0, 1, 3, 4, 7, 2, 8, 9, 5, 17] size: 501
         1 function calls in 0.000 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 uniq.py:15(f3)


result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 501
         1 function calls in 0.000 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 uniq.py:24(<lambda>)


orig: [0, 1, 1, 1, 0, 1, 4, 2, 5, 2] size: 10000
result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 5007
         1 function calls in 0.005 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.005    0.005    0.005    0.005 uniq.py:6(<lambda>)
        0    0.000             0.000          profile:0(profiler)


result: [0, 1, 4, 2, 5, 3, 14, 11, 16, 18] size: 5007
         1 function calls in 0.468 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.468    0.468    0.468    0.468 uniq.py:8(f2)


result: [0, 1, 4, 2, 5, 3, 14, 11, 16, 18] size: 5007
         1 function calls in 0.003 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.003    0.003    0.003    0.003 uniq.py:15(f3)


result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 5007
         1 function calls in 0.001 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.001    0.001 uniq.py:24(<lambda>)


orig: [0, 0, 1, 1, 4, 3, 4, 6, 3, 8] size: 50000
result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 24967
         1 function calls in 0.055 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.055    0.055    0.055    0.055 uniq.py:6(<lambda>)
        0    0.000             0.000          profile:0(profiler)


result: [0, 1, 4, 3, 6, 8, 11, 5, 2, 19] size: 24967
         1 function calls in 11.787 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1   11.787   11.787   11.787   11.787 uniq.py:8(f2)


result: [0, 1, 4, 3, 6, 8, 11, 5, 2, 19] size: 24967
         1 function calls in 0.023 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.023    0.023    0.023    0.023 uniq.py:15(f3)


result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] size: 24967
         1 function calls in 0.014 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.014    0.014    0.014    0.014 uniq.py:24(<lambda>)

2010年12月11日土曜日

DnD ダウンロードブックマークレット

いまIgoの辞書作成部をPythonに移植中ですが、移植作業は割と一気にやらないとはかどらないので、ちょっと開いた時間で前から実験したかったDnDダウンロードをやってみました。

かなり手抜きですが、ブックマークレットに纏めました。多分Chrome専用です。

  • アンカータグに対してイベントハンドラを設定します(なにも考えず全て)
  • アンカーのhrefをみてダウンロード元に設定します
  • ダウンロードするファイル名は最後のスラッシュから後の文字列
  • MIMEタイプは全てapplication/octet-streamです


javascript:(function(){var t,h,i,el=document.getElementsByTagName("a"),n=el.length;for(i=0;i<n;i++){el[i].addEventListener("dragstart",function(e){t=e.currentTarget;h=t.href;e.dataTransfer.setData("DownloadURL","application/octet-stream:"+h.replace(/.*\//g,'')+":"+h)},false);}})()

ちょっと整形した版
var el = document.getElementsByTagName("a");
var n = el.length;
for (var i = 0; i < n; i++) {
  el[i].addEventListener("dragstart",
    function(e){
      var t = e.currentTarget;
      var h = t.href;
      e.dataTransfer.setData("DownloadURL", "application/octet-stream:" + h.replace(/.*\//g, '') + ":" + h);
    }, false);
}

2010年12月7日火曜日

pythonで一行ごとにファイルを読む

Pythonで一行ごとにファイルを読むとき
for l in sys.stdin:
  print l 
だと改行が含まれてしまうので、改行を落としたいことが良くあります。

いままで、
for l in sys.stdin:
    print l.rstrip()
などとやっていたのですが(1)、なんか美しくないので考えてみました。


数秒考えた結果、ジェネレータを使うのが良さそうな感じがしました。(2)
for l in (x.rstrip() for x in sys.stdin):
    print l


このような場合リスト内包は向きません。(3)
for l in [x.rstrip() for x in sys.stdin]:
    print l


あんまり遅くなってしまっては仕方ないので、この3パターンを比較してみました。
(/usr/bin/timeを使用。手元にあった一番大きいテキストファイルはmecab-ipadicのmatrix.def(1731857行)だったのでそれを使用した)
方法usersyselapsedmaxresidentpagefaults
(1)1.450.011.4813434946
(2)1.610.011.6313450947
(3)1.750.051.8231959120141

こうみると、多少遅くなってるけど、まあ許容できるかなといった感じでした。メモリ使用量はほとんど増えていません。

2010年11月28日日曜日

Igo-pythonの導入メモ

igo-pythonを導入する一連の手順を書いてなかったので、ここに纏めておきます。

インストール

$ easy_install igo-python
もしくはhttp://pypi.python.org/pypi/igo-python/からソース配布物をダウンロード&展開して
python setup.py install

辞書のコンパイル

辞書作成はJava版のIgoで行うのでJavaが必要です。
ローカル版
Igoのサイトの手順そのままです。
準備
  • igo-0.4.2.jarの入手
  • 辞書のダウンロードと展開
$ java -cp igo-0.4.2.jar net.reduls.igo.bin.BuildDic コンパイル済み辞書出力先 ダウンロードした辞書を展開したところ 辞書の文字セット
$ java -cp igo-0.4.2.jar net.reduls.igo.bin.BuildDic ipadic mecab-ipadic-2.7.0-20070801 EUC-JP
GAE版
igo-gaeの手順です。 ローカル版との違いは使用するjarがigo-0.4.2-gae.jarなだけ。igo-0.4.2-gae.jarはigo-gaeのgithubから入手できます。

動作確認

ローカル版
$ python
Python 2.6.6 (r266:84292, Oct  9 2010, 11:40:09) 
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from igo.Tagger import Tagger
>>> for m in Tagger('ipadic').parse(u'すもももももももものうち'):
...   print m.surface, m.feature, m.start
... 
すもも 名詞,一般,*,*,*,*,すもも,スモモ,スモモ 0
も 助詞,係助詞,*,*,*,*,も,モ,モ 3
もも 名詞,一般,*,*,*,*,もも,モモ,モモ 4
も 助詞,係助詞,*,*,*,*,も,モ,モ 6
もも 名詞,一般,*,*,*,*,もも,モモ,モモ 7
の 助詞,連体化,*,*,*,*,の,ノ,ノ 9
うち 名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ 10
>>>
GAE版辞書をローカルで
>>> for m in Tagger('ipadic_gae', gae=True).parse(u'すもももももももものうち'):
...   print m.surface, m.feature, m.start... 
すもも 名詞,一般,*,*,*,*,すもも,スモモ,スモモ 0
も 助詞,係助詞,*,*,*,*,も,モ,モ 3
もも 名詞,一般,*,*,*,*,もも,モモ,モモ 4
も 助詞,係助詞,*,*,*,*,も,モ,モ 6
もも 名詞,一般,*,*,*,*,もも,モモ,モモ 7
の 助詞,連体化,*,*,*,*,の,ノ,ノ 9
うち 名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ 10
GAEで
@norioさんが置かれた gist: 716998 - igo-python gae test- GitHub https://gist.github.com/716998 で試すのが良いと思います。

Google App Engineでメモリを節約する

igo-pythonがGAEでもやっと動くようになったと思ったら、メモリの使いすぎで毎回インスタンスが終了されてしまう状態でした。メモリ使用量を削減したものをリリースしました(最初に出したのはバグってた。やっぱり文字と文字コードの扱いだった。@norioさんありがとうございます)

辞書の読み込みが問題(*)であることは見当がついていたので、幾つか思い当たる点をあたってみた。
  1. 文字列の連結で全部ロードしてからjoinするのをやめた
    • 少し減ったがほとんど効果なし
  2. バイト列で読んでからunicode化するのをStreamReaderで直にunicodeで読むようにした
    • 思ったより減らない
  3. Unicode文字列を使うのやめてarrayを使うようにした
    • 効果大
GAEのPythonはUCS4モードになっているので、大きいunicode文字列を持つとメモリの使用量が思った以上に増えてしまうことが分かった。それを連結したりしていたため最終的な文字列が出来ときに許容量をオーバーしていたと考えられる。
また、同じくメモリ節約のためarray.fromstringではなく、array.fromfileで読みたいため、いったんmmapは使わないようにした。pythonのmmapはコピーを作ってしまうので全部シーケンシャルに読んでしまうような使い方ではあまり効果がなさそうと判断した。

(*) 読み込みが終わっている状態では70MB程度で何度もインスタンスを作ったり、parseしても特に増えていく様子はなかった。

2010年11月27日土曜日

Igo for Pythonを使ってGoogle App Engineで形態素解析が出来た

@norioさんからコメントでGAEではos.fstatが存在していないことを教えていただきました。os.fstatが存在すればos.fstatを、そうでなければos.statを使うようにしたものをリリースしました。

これで、GAEにデプロイするアプリでもigo-pythonを使って形態素解析が出来るようになりました!ただ、メモリとCPUを使いすぎてしまうようなので、もう少し改善できないかみてみたいと思います。

2010年11月26日金曜日

PyPIに登録

Igo for PythonをPyPIに登録した。
これでeazy_install igo-pyでインストールできるようになりました。


登録方法は、Python Hack-a-thon 4 ハンズオン 中級コースPyPIデビューを参考にした。必要な情報は一通り書いてあるので困らなかった。

はまったのは、ReSTでかけるはずのlong_descriptionがどうしてもただのテキスト扱いになってしまうこと。litteral blockの最初の空行がなかったのが原因だったのだが、rst2htmlでの確認では気づかなかった。

2010年11月24日水曜日

Pythonはまりメモなど

移植時にはまったデフォルト引数の挙動。

>>> def f(a=[]):
...     print a
...     a.append('a')
... 
>>> f()
[]
>>> f()
['a']
>>> f()
['a', 'a']
>>> 
関数定義時に固定されるからと言うのが理由。すっかり忘れてた。


モジュール名を差し替えるやりかた。Python Hack-a-thonでPyQt4のHands Onに出たときから何とか出来ないかなーと思っていたもの(LinuxではPyQt4, WindowsでPySideをつかっているので)
まあこれでも長いけど…

sys.modules['モジュール名'] = モジュールオブジェクトでできる。

import sys
try:
    import PyQt
except:
    import PySide
    sys.modules['PyQt'] = PySide
from PyQt import QtCore
from PyQt import QtGui

形態素解析器IgoのPython版を作るときにはまったこと

IgoPythonへの移植がとりあえずのところまで来たので、メモをかねて記録。

何で移植しようかと思ったかと言えば

  1. Wooshを知って、WooshがせっかくPurePythonなら形態素解析器もPurePythonでと思った
  2. IgoはJavaで書かれているので、MeCabを移植するよりは移植が簡単だと思った
  3. PurePythonでそれなりの形態素解析器があれば、いろいろ遊んでくれる人も多いだろうと考えた

取りかかる前は、バイナリ辞書の扱いが一番面倒だと思ったけど、意外と問題なくすんだ。文字列もUTF-16でそのまま読むだけで動いている。
それよりは、javaではcharは整数なのに対して、pythonの文字は整数ではないのでordで整数値にしないといけないところがあり面倒だった気がする。

GAE版辞書対応はとりあえず出来てから取りかかったけど、思った以上に簡単にできた。

普段あまり使わない、struct, arrayと初めて使ったmmapもドキュメントがあるのでそれほど迷わず使えた。一番間抜けなのは、デフォルト引数の挙動で悩んでしまったこと。昔はまったことは解決したときに思い出した。

2010年11月21日日曜日

形態素解析器IgoのPython版作った

Java(とCL)で書かれた形態素解析器であるIgoをPythonにほぼそのまま移植しました。
Java版で作った辞書がそのまま使えるようにしたので、辞書を作る部分は(まだ)移植してません。
mmapしてるのでGAEでは動きません。すぐ取りかかる予定です。
またGAE版の辞書はBigEndianなのでそこらへんも対応する予定です。

https://code.launchpad.net/~hideaki-t/+junk/igo-pyに置きました。
簡単なテストしかしてません。問題があったら教えてください!

簡単なサンプル
# coding: utf-8
import igo.Tagger

t = igo.Tagger.Tagger('/mnt/dev/ipadic')
l = t.parse(u'こんにちは世界')
for m in l:
 print m.surface, m.feature, m.start

結果
~/works/igo-py $ python test.py
こんにちは 感動詞,*,*,*,*,*,こんにちは,コンニチハ,コンニチワ 0
世界 名詞,一般,*,*,*,*,世界,セカイ,セカイ 5


追記
  • mmapが使えなければFile IOで処理するようにしました
  • GAE版辞書モード追加しました
  • 複数回parse/wakatiすると結果がつながる問題を直しました
  • PyPIに登録しました
  • Python 2.5 on Linux, Python 2.6 on Windows/Linuxで動作を確認しました

2010年10月22日金曜日

DnD, FileAPI使ったブックマークレット再び

ChromeがFile APIをサポートしたので、前書いたブックマークレットを試してみたら動かなかったので、FirefoxでもChromeでも動くように手直ししてみた。
(dev使ってるので前から出来たはずだけど、忘れてた)

ブックマークレット用
javascript:(function(){var f,i,r,a=function(n,f){document.querySelector("#t").addEventListener(n,f,0)};a('dragover',function(e){e.preventDefault()});a('drop',function(e){f=e.dataTransfer.files;for(i=0;i<f.length;i++){r=new FileReader();r.onloadend=function(e){t.value=r.result};r.readAsText(f[i],"UTF-8");}e.stopPropagation()})})();

少し見やすい状態
javascript:(function(){
 var f,i,r;
 var a=function(n,f){document.querySelector("#t").addEventListener(n,f,0);};
 a('dragover',function(e){e.preventDefault();});
 a('drop',function(e){
   f=e.dataTransfer.files;
   for(i=0;i<f.length;i++){
    r=new FileReader();
    r.onloadend=function(e){t.value=r.result};
    r.readAsText(f[i],"UTF-8");
   }
   e.stopPropagation();
  });
})();

2010年10月16日土曜日

wikkid wikiのcreoleと日本語ファイル名など

Wikkid wikiを使ってみるの続き。適当にいじったので、日本語ファイル名/フォルダ名、WikiCreole書式、そしてWindowsでも使えるようになったので、スクリーンショットを取ってみた。

日本語ファイル名でcreoleで書いてみる。先頭に
# creole
と書くとcreole書式として処理される。
creole書式で編集
保存すると、期待通り表示されました。
うまく表示された

jinja2を使っているので、日本語にも出来そう。

Wikkid wikiをいじる

まだ、勝手にやってる段階だけど、次のような感じでいじってみた。
  • creoleが動くようにした
  • 日本語ファイル名を使えるようにした(unicode化してるから、bzrで扱える文字なら多分全部いけるはず)
  • Windowsでも動くようにした
launchpadにブランチ作っておいてあります。

2010年10月7日木曜日

Wikkid wikiを使ってみる

Wikkid wikiBazzarブランチ上で使うWikiエンジンです。
渋日記: Bitbucket買収?そもそもそれ何?という人のためのBitbucket紹介をみて、そういえば最近debianパッケージにBazaarバックエンドのやつが入った記憶があるなと思って、調べたらwikkidだった。
なので、debianでexperimentalも見るようにしてあればapt-get wikkidだけでインストールできる。

ちょっとだけ使ってみたので、メモ代わりに置いておく。

使い方

新規のブランチでやっているが、既存のブランチでもやれば出来るんじゃないかと思う。
bzrのブランチなので、分散管理できるはずですが試してません。

ブランチの作成

適当にbzr init wikiとかしてブランチを作る。

サーバ起動

bzr wikkid または wikkid-serveで起動する(オプション無指定時には8080をListenする)。
hideaki@siduxbox:~/works/wiki$ bzr wikkid
2010-10-06 23:40:45 INFO    Using: <WorkingTree6 of /home/hideaki/works/wiki>
2010-10-06 23:40:45 INFO    Using bzr identity: "Takahashi Hideaki", "mail addr"
2010-10-06 23:40:46 INFO    Listening on port 8080

ブラウザでアクセスして編集

最初は何もないのでページを作成する。
最初は何もないのでページの作成
編集画面になる
ReSTで書きます。下のセーブボタンを押せば保存。
結果を見る
保存すると書いた内容が表示されます
右上のBrowseボタンを押すとファイルリストが見られる
ブラウズボタンを押すと、ファイル一覧が見えます

テキストエディタで編集

ただのテキストファイルなので、当然普通に編集できます。
Emacsで編集して保存します
編集結果をブラウザで見る
編集結果はブラウザで見られます
確認したら、コミットするかブラウザの方で保存します。

Creoleにも対応しているはずなのだが、同梱されているパーサーが古い(0.1.1)ためうまく動かなかった。

2010年10月3日日曜日

JDK7のString in switch(2)

文字列リテラルのhashCodeがぶつかったときどうなるか調べた。
予想通り、最初のhashCodeでのジャンプの後でequalsでそれぞれ確認して実際の処理に分岐するための値を設定していた。


java.lang.Stringを書き換えてbootclasspath(-J-Xbootclasspath/-bootclasspathの両方)で指定してもうまくいかなかったので、検索して見つけたテストコードを参考にやってみた。hashCodeが0になるパターンをいくつか指定している。


public class Test {
    public static void main(String[] args) {
        String s  = "\u0000";
        switch (s) {
        case "":
            System.out.println("empty");
            break;
        case "\u0000":
            System.out.println("\\u0000");
            break;
        }
    }
}

28-34で""か判定して、""じゃなければ42-48で"\u0000"か判定してる。
8: invokevirtual #3                  // Method java/lang/String.hashCode:()I
        11: lookupswitch  { // 1
                       0: 28
                 default: 53
            }
        28: aload_2
        29: ldc           #2                  // String
        31: invokevirtual #4                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
        34: ifeq          42
        37: iconst_1
        38: istore_3
        39: goto          53
        42: aload_2
        43: ldc           #5                  // String
        45: invokevirtual #4                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
        48: ifeq          53
        51: iconst_0
        52: istore_3
        53: iload_3
        54: lookupswitch  { // 2
                       0: 80
                       1: 91
                 default: 99
            }
        80: getstatic     #6                  // Field java/lang/System.out:Ljava/io/PrintStream;
        83: ldc           #7                  // String empty
        85: invokevirtual #8                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
        88: goto          99
        91: getstatic     #6                  // Field java/lang/System.out:Ljava/io/PrintStream;
        94: ldc           #9                  // String \u0000
        96: invokevirtual #8                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
        99: return

2010年9月23日木曜日

JDK7のString in switch

ちょっと前に試してみて、どうやって実現されているか調べたのでメモっておく。
ちゃんと仕様、ソースを見たわけではないので嘘かも知れない。

テストのソースコード
public class Test {
    public static void main(String[] args) {
        String s  = "xyz";
        switch (s) {
        case "abc":
            System.out.println("abc");
            break;
        case "lmn":
            System.out.println("lmn");
            break;
        case "xyz":
            System.out.println("xyz");
            break;
        }
    }
}

javapでバイトコードを出力してみてみたら、分かった気がする。
文字列のhashCodeを得ている
8: invokevirtual #3                  // Method java/lang/String.hashCode:()I
謎の数値でジャンプ先を決めている
11: lookupswitch  { // 3
                   96354: 44
                  107277: 58
                  119193: 72
                 default: 83
            }
追記 - 各文字列のhashCodeを調べた結果
js> java.lang.String("abc").hashCode()
96354
js> java.lang.String("lmn").hashCode()
107277
js> java.lang.String("xyz").hashCode()
119193

これを見る限り、switchする文字列のhashCodeをみて分岐するようだ。
caseの文字列は前もってその文字列のHashCodeに置き換えられて、
整数でのswitch/caseで実現できている。

ただ、ハッシュ値はぶつかることがあるので、
分岐した後本当に正しいかどうかequalsでチェックしてさらに分岐させている。

今回だとabcなら44-55でチェックして0, lmnなら58-69でチェックして1, xyzなら72-82でチェックして2が設定され、
その数字でさらに飛び先が決まる(初期値はiconst_m1/istore_3なので-1) 。
javapの出力(今回不要なところは削った)
{
  public static void main(java.lang.String[]);
    Signature: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    LineNumberTable:
      line 3: 0
      line 4: 3
      line 6: 112
      line 7: 120
      line 9: 123
      line 10: 131
      line 12: 134
      line 15: 142
    LocalVariableTable:
      Start  Length  Slot  Name   Signature
             0     143     0  args   [Ljava/lang/String;
             3     140     1     s   Ljava/lang/String;
    Code:
      stack=2, locals=4, args_size=1
         0: ldc           #2                  // String xyz
         2: astore_1
         3: aload_1
         4: astore_2
         5: iconst_m1
         6: istore_3
         7: aload_2
         8: invokevirtual #3                  // Method java/lang/String.hashCode:()I
        11: lookupswitch  { // 3
                   96354: 44
                  107277: 58
                  119193: 72
                 default: 83
            }
        44: aload_2
        45: ldc           #4                  // String abc
        47: invokevirtual #5                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
        50: ifeq          83
        53: iconst_0
        54: istore_3
        55: goto          83
        58: aload_2
        59: ldc           #6                  // String lmn
        61: invokevirtual #5                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
        64: ifeq          83
        67: iconst_1
        68: istore_3
        69: goto          83
        72: aload_2
        73: ldc           #2                  // String xyz
        75: invokevirtual #5                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
        78: ifeq          83
        81: iconst_2
        82: istore_3
        83: iload_3
        84: tableswitch   { // 0 to 2
                       0: 112
                       1: 123
                       2: 134
                 default: 142
            }
       112: getstatic     #7                  // Field java/lang/System.out:Ljava/io/PrintStream;
       115: ldc           #4                  // String abc
       117: invokevirtual #8                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       120: goto          142
       123: getstatic     #7                  // Field java/lang/System.out:Ljava/io/PrintStream;
       126: ldc           #6                  // String lmn
       128: invokevirtual #8                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       131: goto          142
       134: getstatic     #7                  // Field java/lang/System.out:Ljava/io/PrintStream;
       137: ldc           #2                  // String xyz
       139: invokevirtual #8                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       142: return
}

2010年9月19日日曜日

ブログ移行した

Vox(http://hide-t.vox.com/)からとりあえずbloggerに移行した。
ブログの記事もあんまり書いてないけど、ないと長いの置く場所がないので。

typepadに移して、そこからエクスポート&ツールで変換で終了。
画像もflickrに移行して記事内のリンクはとりあえず直した。
インポートを大量投稿と判定されたせいか、いきなり確認を求められて面倒くさいね。

2010年8月22日日曜日

エスケープ解析とfinalize

ARMについて調べているときに、エスケープ解析でスタックに割り付けられたオブジェクトのfinalizeがちゃんと呼ばれるなら、確実なリソースの開放が出来るんじゃないかと思って調べてみた。

まずエスケープ解析でスタックに割り当てられるようなオブジェクトを作って動作を確認する。
その後、そのオブジェクトでfinalizeをoverrideしてみたところ、スタックに割り当てられなくなったっぽい。
(GCログで確認)

finalizeを実行するスレッドを確認すると、通常通りFinalizerスレッドで実行されていた。これだと、非同期に実行されるのでメソッドを抜けたときに開放できないし(finalizeが実行されるまで待つなら出来るが…)、Finalizerスレッドからfinalizeを呼び出すためにオブジェクトが漏れてしまっている。
Javaの理論と実践: ガベージコレクションとパフォーマンスにもそのようなことが書いてある。

エスケープ解析はJVMの最適化オプションであってVMが満たすべき仕様ではないからか、VM仕様に書かれてはいないようだが、エスケープ解析の論文を適当に幾つか読むと、finalizeをoverrideしていたらどうしても漏れる(Global Escape)から最初からエスケープ解析する対象から省いてしまうらしい。
ただ、java.lang.ref.Finalizer$FinalizerThreadを使うこと自体もSunのJVM実装仕様だったはずなので、他のVMだったら違うかもしれない。



2010年8月21日土曜日

Java7のjavac新機能を試した

jdk1.7.0 b105でARM(Automatic Resource Management/try-with-resources)が入ったので試してみた。
リソースを自動で閉じてくれるもので、Pythonとかのwithみたいな感じに使える。
ARMで自動で閉じられるようにするには、java.lang.AutoCloseableを実装している必要がある
ARMはclose/finallyより使う側の負荷が低いのでよいと思う。

理由

  • 使う側のコード量が少なくなる
  • コードが少なくなる理由でもあるが、複数のリソースを確実に閉じられる。

試しに作ってみたもの。マルチキャッチも使ってみた。

public class Test {
  private static class AC implements AutoCloseable {
    public void close() throws java.io.IOException {
      throw new java.io.IOException();
    }
  }

  private static class AC2 implements AutoCloseable {
    public void close() throws InterruptedException {
      throw new InterruptedException();
    }
  }

  public static void main(String... args) {
    try {
      try(AC ac = new AC(); AC2 ac2 = new AC2()) { }
    } catch (final java.io.IOException | InterruptedException e) {
      e.printStackTrace();
    }
  }
}

これを実行すると

java.lang.InterruptedException
        at Test$AC2.close(Test.java:10)
        at Test.main(Test.java:16)
        Suppressed: java.io.IOException
                at Test$AC.close(Test.java:4)
                ... 1 more

AC1, AC2がそれぞれブロックを抜けるときのcloseで例外を投げるが、とりあえず全部closeされる。

ここでcloseが投げる例外が無ければ外側のtry/catchは不要だし、
例外に継承関係があれば(java.io.IOExceptionとjava.io.FileNotFoundExceptionとか)があれば親側でcatchするのでも可能。

追記
finallyの場合RuntimeExceptionでもfinallyは実行されるので、ARMではどうか確認したら、途中でRuntimeExceptionが起きた場合もちゃんと全部closeが呼び出された。
これならfinallyでRuntimeExceptionが発生して、全部後処理しきれないとかの問題は回避できるな。



2010年5月26日水曜日

はてなのキーワードリンクを削除するブックマークレット

Evernoteにクリップするときにちょっとうるさい(+容量節約)ので書いてみた。
140文字にならなかったのでやっぱりこっちに貼る。


javascript:(function(){var d=document,a=d.getElementsByClassName("keyword"),v,n=a.length;while(n--){v=a[0];v.parentNode.replaceChild(d.createTextNode(v.innerHTML), v)}})()


javascript:(function(){var d=document,a=d.getElementsByClassName("keyword"),v;while(a.length){v=a[0];v.parentNode.replaceChild(d.createTextNode(v.innerHTML),v)}})()




2010年4月6日火曜日

HTML5 File API使ってみた

Print Text JS http://ta2o.net/tools/printtext/ でHTML5 DnDとFileAPIでファイル読めるようするbookmarkletつくってみた

と書いたやつ。
詰めてみたけど僕の技術では140文字までは短くできなかったのでここに貼ってみる。

javascript:(function(){var t=document.getElementById("t"),a=t.addEventListener,f,i,r;a('dragover',function(e){e.preventDefault()},false);a('drop',function(e){f=e.dataTransfer.files;for(i=0;i<f.length;i++){r=new FileReader();r.onloadend=function(e){t.value=r.result};r.readAsText(f[i],"UTF-8");}e.stopPropagation()},false)})();