今年は本をよく読んだ気がする
SICPからHOPへのコンボがperlを扱う上でとても役立った。
計算機プログラムの構造と解釈特にHOPは値段以上の価値があったと思ってる。満足。
Higher-order Perl: A Guide To Program TransformationMark Jason Dominus
Morgan Kaufmann Pub / ￥ 8,658 (2005-05-30)
通常24時間以内に発送
そしてMAWP
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
来年もこの調子で。あと、もっとコードを書く。
MAWP14章はProbability
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
こういうのはRに任す。確率分布とか充実してる。
15章も統計なのでRで。
16章は微分とかsmoothingとかSICPな感じなので流し読みして終了。
ってことで、MAWPも終了。ソート、マトリックス、グラフ、文字列マッチング、暗号あたりが面白かった。
ElGamal暗号
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
位数が大きな群の離散対数問題が困難であることを安全性の根拠にした暗号化方式
巡回群を利用しているらしい。そういや、ガウス平面上の回転って数学ガールの3章で読んだなと。
数学ガールmodも回転か何かで考えることが出来るのかね。
MAWP 13章はCryptography
アンゴウよりアンコウ+日本酒のほうが好きなんだけど。
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
というより、数式を避けてただけだった。ちゃんと読んでみると暗号も面白いかも。 法とか合同をほうとかいいながら読んでた。MAWPの説明だけだと分かりにくかったのでRSA暗号を参考にした。
MAWPにあったSSLeayっていうモジュールがなかったのでCrypt::RSAで遊んだ。
use Crypt::RSA;
use Data::Dumper;
my $rsa = new Crypt::RSA;
my ($public, $private) =
$rsa->keygen (
Identity => 'Kzfm Ohkw <xxxx@gmail.com>',
Size => 1024,
Password => 'drumnbass',
Verbosity => 1,
) or die $rsa->errstr();
print Dumper($public);
公開鍵
$VAR1 = bless( {
'e' => 65537,
'n' => '12390802849571403672579795755491999585878694
2679376999148135793744998012786068647404317033
4506694188629007869741465370712440443624446804
8813574622838502197241514075336790104367156693
3189856420057871502127203513391621825674392638
5941923712730877023358276499112454722795081438
05979844138326376749179360228658183',
'Version' => '1.91',
'Identity' => 'Kzfm Ohkw <xxxx@gmail.com>'
}, 'Crypt::RSA::Key::Public' );
おー65537乗してnでmodるのか。
MAWP 12章はNumber Theory
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
Modularとか。Chinese Remainder Theoremってなにがおもろいんだろうとか思ったが、RSA暗号がらみ？そのうちちゃんと読んでみる。
あとMiller-Rabinとかコラッツ予想とかそんな感じ。
MAWP 11章はNumber System
perlで複素数とか極座標とか扱うって話 あまり興味がなかったので流した。
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
最後の例のリーマンゼータ関数は面白かった。
まだ2章くらいしか読んでない数学ガールにも出てくるらしい
これも早く読みたいなぁ。
MAWP 10章はGeometric Algorithm
さわりだけなので、さらっとしている。
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
ちゃんと学びたければC++とかの本を探したほうがよいのかな？pymolとかAvogadroのソースを読むのがいいのかもしれんなぁ。
ドッキングシミュレーションとか色々気に入らない部分があるので、手を加えたい部分があったりとか、Caverみたいなの自分で書いてみたかったりするんだけどそういう書籍はないもんかな。
MAWP 9章終了
後半はparserとか
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
HOPも読んだし、再帰下降パーサもいじったことあるのでさらさらと。あとハフマン符号化とか。
結局1週間近くかけて読んだが文字列検索アルゴリズムがなかなか面白かった。
PythonでWu-Manber
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,036 (1999-07)
通常8～11日以内に発送
ビット演算を利用したアルゴリズム。Shift-ADDと違いdifference,insertion,deletionを考慮する。
可能性を論理和として積み上げていってShift-ORみたいなアプローチで評価するとこだと思う。いまいちちゃんと理解できてないが。
for j in range(1,k+1):
s[j] = (r[j] << 1) & Tc
s[j] |= (r[j-1] | s[j-1]) << 1
s[j] |= r[j-1]
s[j] |= 1
あと、perlで@a = @bとやれるところがpythonではa=bとできず、 b = copy.copy(a)なのね。
#!/usr/bin/env python
import copy
def amatch (T,P,k=-1):
text_length = len(T)
pattern_length = len(P)
po2 = map(lambda(x): 1 << x,range(31))
if k == -1: k = int(pattern_length/10) + 1
Table = [0] * 256
for i in range(pattern_length):
Table[ord(P[i])] |= po2[i]
r = [0] * (k+1)
for i in range(1,k+1):
r[i] = r[i-1] | po2[i-1]
mb = po2[pattern_length-1]
s = [0] * (k+1)
for i in range(text_length):
s[0] <<= 1
s[0] |= 1
Tc = Table[ord(T[i])]
s[0] &= Tc
for j in range(1,k+1):
s[j] = (r[j] << 1) & Tc
s[j] |= (r[j-1] | s[j-1]) << 1
s[j] |= r[j-1]
s[j] |= 1
if s[k] & mb:
return i - pattern_length + 1 if i > pattern_length else 0
r = copy.copy(s)
return -1
if __name__ == '__main__':
print "match: ", amatch("pearl","perl",1)
PythonでShift-ADD
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,036 (1999-07)
通常8～11日以内に発送
これもビット演算を利用したアルゴリズム。differenceを許容するけどinsertion,deletionは駄目。
#!/usr/bin/env python
from math import *
def shift_ADD (T, P, k=-1):
text_length = len(T)
pattern_length = len(P)
if k == -1: k = int(log(text_length)+1)
if k == 0: return T.find(P)
if pattern_length == 1: return T.find(P)
if pattern_length > text_length: return -1
if pattern_length == text_length and P == T: return 0
bits = int(log(k+1,2)) + 1 # ????
mask = 1 << ( bits - 1 )
ovmask = 0
for i in range(pattern_length):
ovmask |= mask
mask <<= bits
table = [ovmask >> (bits-1)] * 256
nmask = 1
for i in range(pattern_length):
table[ord(P[i])] &= ~nmask
nmask <<= bits
mask = ( 1 << ( pattern_length * bits )) -1
state = mask & ~ovmask
ov = ovmask
watch = ( k + 1 ) << ( bits * ( pattern_length - 1 ) )
for i in range(text_length):
state = ((state << bits) + table[ord(T[i])]) & mask
ov = ((ov << bits) | (state & ovmask)) & mask
state &= ~ovmask
if (state | ov) < watch:
return i - pattern_length + 1
return -1
if __name__ == '__main__':
print shift_ADD("perlpethonxx","python",2)