URIの長さの上限とブラウザいじめ
URI(もしくはURL)の長さの上限ってどれくらいだろう？
GETを多用する人やブックマークレットでありとあらゆることをやりたい人は一度は興味を持ったことかと存じます。
僕の知る限り、RFCではURL（の長さ）を規定はしていないはず。
俺責任取れないから、長さとかグレーにしとくわ、見たいな事が書かれていたような気がします。完全に気のせいかも。
でも世の中には、死ぬほど長いJSとかをロケーションバーに突っ込むクレイジーさんだっているでしょう。途中で切ったりしてないのかな？
よし、ちょっといじめてみよう。
というのが今回のモチベーション。
98000000 = 9.8 * 10^7文字長まで試した。
●環境
Windows7/i7-920/3Gbyte
●結果（文字数）
IE 8.0.7600.16385 .... 2048 Opera 10.53 .... 65531 Safari 5.0.3 .... 50881 Firefox 3.6.3 .... inf (?) Chrome 8.0.552.237 .... inf (?)
●やり方
１． テキストエディタでとてもながい文字列を入力
２． ロケーションバーにコピペ
３． ロケーションバー上の文字列を全選択してコピペ
４． txtに貼り付けてwc
●考察
IEが残念すぎる。さすがにこの長さだと、GETのクエリとかやばいんじゃないの。
ちなみに、MSのページには2083文字と書いてあったので、多分この結果が当てにならないんでしょう。
Firefox, Safariは多分制限を設けていないっぽい。
長い文字列をロケーションバーに食わせたときのFF,CHの挙動は以下のとおり。
○Firefox：
ある一定以上長い文字列をペーストすると、ペーストはされているんだけど、
文字が表示されないという問題が。さらにそれをオーバーするとクラッシュする。
最新の3.6.13でも再現したけど再現率低い。というか、再現する前にクラッシュすること多数。
セーフモードではやってない。
○Chrome
捌けるんだけど、長い（僕の環境だと3 * 10^7くらい）文字列は捌くのに5分くらいかかる。それをオーバーすると、わりと早々にあきらめてクラッシュする。
今回気になったのは、右クリックでロケーションバーに貼り付けしようとしたときに、
クリップボードを先読みしているのか分からないんだけど、右クリックだけでクラッシュしたりしていた。ちょっとっ。
で、この結果は、あくまでブラウザのアプリに対するロードテストで、
コアがどうURL捌いているかに直接関係無い可能性大きいのであしからず。
●今後の展望
バリエーションとしては、リンクやdocument.location.hrefやらなんやら、その辺で以上に長いURL指定したらどうなるのかなぁ、ということを調べても良いかもしれないですね。
僕はもう飽きたのでやりません。
後々知り合いに教えてもらったんですが、今回の件と同じことを考えて実践してみた人もいるみたいです。
5年前のことなので、比較してみるのも面白いかと思います。
SPACE ALC用のブックマークレット
なんてやる気のない表題なんだ。
情強の方々はSPACE ALCなんぞ使わなくても脳みそのMySQLで間に合っているのでしょうが、
僕はその辺が足りないようなのでいつもお世話になっております。
きっとALCとLSDがあれば英語についてはもういい気がします。
そんなときはブックマークレット。
新規ブックマークを追加 → アドレス欄に以下のスクリプトを突っ込むことで、
トップページをすっ飛ばして検索結果にダイレクトにいけます。2011/01現在。
いい加減、新しいタブ開く→トップページを待つ→入力という
一連の流れに耐え切れなくなって、たった今書いたのを貼り付けただけです。
実は結構使えるのでだまされたと思って使ってみてはいかが。
別ウインドウで開く
javascript:window.open("http://eow.alc.co.jp/"+prompt("look up word in SPACE ALC")+"/UTF-8/")
現在のウインドウで開く（使い勝手は良くない）
javascript:document.location.href = "http://eow.alc.co.jp/"+prompt("look up word in SPACE ALC")+"/UTF-8/"
Levenshtein距離とか。
某所のパズルでまさにこれを使う問題が出たので2年ぶりくらいに実装してみる。
●レーベンシュタイン距離
２つの文字列があるとき、片方からもう片方に変換したい。
文字の置換・挿入、削除の３つの操作が可能なとき、一連の操作の最も少ない回数のこと。
Googleの"もしかして"のような機能や、判別系モデルの特徴量なんかに使われていて、自然言語処理屋さんなら必ず知っている気がします。気のせいかもしれません。
※ちなみにこのとき、置換操作のみを許可したものがハミング距離というやつです。
昨今（といってももうだいぶ前から）ではバイオインフォでも使われます。
面倒な話は省きますが、謎の要請により、DNA配列同士を比較したいのだけど、
DNAには塩基の置換や挿入、欠失が起こるから困ったもんだ、という、
まことにレーベンシュタイン距離の扱う問題そのものがあったりします。
しかし昨今はインターネットでこの辺の説明もコードも簡単に手に入るなぁ。
上で書いた内容なんてほとんど、むしろ断然詳しくネットに乗っているので僕が偉そうに書く必要もないのですが。
そんな感じで虚無感に苛まれていてもあれなので、その辺に出回っているものとはほんのちょっと、wikiでは扱っていない部分を付け足したスニペットをはっときます。
何が違うかって言うと、たとえば、置換はわりとよくあるんだけど、
挿入はほとんどないし、削除にいたっては絶望的にないよね、
という事前情報を状況に対応できるよう、コストを突っ込めるようにしただけ。
※挿入と削除は見る方向が違うだけで、同じ処理なので、ここを変える要請があるかは不明
template< typename CostType > int getLevenshteinDistance( const char* str1, const char* str2, CostType cost_ins, CostType cost_del, CostType cost_mut ){ unsigned int len1 = std::strlen( str1 ); unsigned int len2 = std::strlen( str2 ); // alloc CostType **matrix = new CostType*[len1+1]; for( unsigned int i=0; i <= len1; ++i ){ matrix[i] = new CostType[len2+1]; } // init dp matrix for( unsigned int i = 0; i <= len1; ++i ){ matrix[i][0] = i * cost_ins; } for( unsigned int i = 0; i <= len2; ++i ){ matrix[0][i] = i * cost_del; } for( unsigned int i = 1; i <= len1; ++i ){ for( unsigned int j = 1; j <= len2; ++j ){ CostType min = matrix[i-1][j-1] + ( ( str1[i-1] == str2[j-1] ) ? 0 : cost_mut ); // mutation if( min > ( matrix[i-1][j] + cost_ins ) ){ min = matrix[i-1][j] + cost_ins; } // insertion if( min > ( matrix[i][j-1] + cost_del ) ){ min = matrix[i][j-1] + cost_del; } // deletion matrix[i][j] = min; } } for( unsigned int i = 0; i <= len1; ++i ){ for( unsigned int j = 0; j <= len2; ++j ){ std::cout << matrix[i][j] << " "; } std::cout << std::endl; } CostType result = matrix[len1][len2]; for( unsigned int i=0; i < len1; ++i ){ delete[] matrix[i]; } delete[] matrix; return result; }
また無駄にテンプレート。コストはintとは限らないからね！
テストしてないのでちゃんと動くのかは知りません…
●蛇足
この辺の、文字比較の何とか距離というものは有用だからか、わりと色々な種類があって、
今回のレーベンシュタイン距離のほかにも、Jaro距離とか、Jaro-Winkler距離とか、
なんだかもう色々とわけが分からない感じになっています。
その辺の話も、一応できるのですがまた今度。
PythonでMethod Missing
聞くところによると、RubyにはMethod Missingなる機能があるとか。
いわく、オブジェクトにメソッドがない場合に、どういう処理をするかを記述するとか。
こいつぁ、われらがPythonにも欲しい機能です。
上記の文面をまともに受け取る使い方でも良いのですが、たとえば、あるオブジェクトのメソッド全てについて、
同様な処理を付加するといったラッパーが簡単に書けちゃうわけです。
というわけで調べてみた。
そのものずばりは出てこなかったけれど、おおむねこんなかんじ。
Method missing（のようなもの）を使った簡易ラッパー。
import threading import time class Wrappee: def __init__( self, count ): self.count = count def print_something( self, text ): for i in range( self.count ): print( i, " something : ", text ) time.sleep( 0.5 ) class Wrapper: def __init__( self, wrapper ): self.wrappee= wrapper # Emulate ruby like " missing method ". def __getattr__( self, name ): def _method_missing( *args ): return args print( "--", name, " is called --") ret = getattr( self.wrappee, name, _method_missing) return ret wrappee = Wrappee( 10 ) wrapper = Wrapper( wrappee ) wrapper.print_something( " foo " )
ううん、これは便利だ。
ただ、ラップされるオブジェクトに指定の関数名がない場合にエラーが出ないのが玉に傷。
どこかのサイトで関数名一覧をディクショナリでもっておいて検査するという手法も見られたけど、もっと楽にいけないものだろうか。
MacPortsでHugs突っ込むときにコケる件。
トラッカーによるとleopardでは起こらないけどsnow leopardでは起こる。
https://trac.macports.org/ticket/20950
以下を参考にすれば最短距離。
パッチ2つ当てるのみ。
http://antsomerset.co.uk/2010/10/04/installing-hugs98-haskell-on-mac-10-6-snow-leopard/
すごいのみつけた
以前から、Haskellの遅延評価の枠組みは確率分布のサンプリングとかやるのによさそうだなぁとか思っていたのですよ。
再帰を使うってだけなら、C++とかでも上記の式と同様になるかと思いますが、
いざサンプリングするぞって時に面倒なのが、SBPのtailの方。
僕の場合だと、必要な分だけ確率列を用意して、サンプリング中に必要になる、
そのつど確率変数に値を振っていくという形式のコードです。面倒。
んが、Haskellだと（多分）そのへん自動でやってくれる！すごい！
んじゃないのかな。実際動かしたわけじゃないのでわからないのですが。
そんなこんなで、Haskellでノンパラベイズ周辺のライブラリを書こうと意気込んだその矢先、
しかもコードは、かのHal Daume III御大。
とりあえずオープンソースにして。コミットするから。
O'REILLYどうした
もともと翻訳どうよ、と思うものが多い出版社でしたが、
久々の出物、しかも大物、しかも２つ。
あまりに酷いので、ここで血祭りにあげようと思います。
プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)
- 作者: David Wells,伊知地宏(監訳),さかいなおみ
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/10/25
- メディア: 単行本
- クリック: 15回
- この商品を含むブログ (33件) を見る
数学を生み出す魔法のるつぼ ―実験数学への招待 (O’Reilly math series)
- 作者: Jonathan Borwein,Keith Devlin,伊知地宏
- 出版社/メーカー: オライリージャパン
- 発売日: 2009/12/28
- メディア: 単行本（ソフトカバー）
- クリック: 20回
- この商品を含むブログ (11件) を見る
これはひどすぎる。読めたものではないとはまさにこれか。
分かりにくい日本語とか、そういうレベルではなく、
もはや日本語の体をなしていない文章だらけ。
誤植等も非常に多い。
久々に焚書目録に登録しました。
なお、非常に残念ですが、内容については触れることはできません。
５０ページくらいで読むのをやめてしまったので。
そのうち原書のほうを買います。
原著をなぶって遊ぶのはやめたらどうかと声を大にして言いたい。
....追記
プライムナンバーズを無理やり読んでみた。
普通に原書がほしい。
Project Euler Problem 84
モノポリーで、どの升目に止まりやすいかという問題。
まじめに計算できそうな感じだけど、せっかくなのでサンプリングしてみる。
ただひたすら面倒なだけ。
import random # monopoly simulator cells = [ 'GO', 'A', 'CC', 'A', 'T', 'R', 'B', 'CH', 'B', 'B', 'JAIL', 'C', 'U', 'C', 'C', 'R', 'D', 'CC', 'D', 'D', 'FP', 'E', 'CH', 'E', 'E', 'R', 'F', 'F', 'U', 'F', 'G2J', 'G', 'G', 'CC', 'G', 'R', 'CH', 'H', 'T', 'H' ] cccards = ['DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', '0', '10'] ccards = ['DC', 'DC', 'DC', 'DC', 'DC', 'DC', '0', '10', '11', '24', '39', '5', 'G2NR', 'G2NR', 'G2NU', 'GB3'] def pe84(): ntrial = 500000 shuffle_cards() visited = sampling( ntrial ) print visited print get_solution( visited ) def get_solution( visited ): first = get_max_index( visited ) visited[first] = 0 second = get_max_index( visited ) visited[second] = 0 third = get_max_index( visited ) return "".join( [encode_squareface( first ), encode_squareface( second ), encode_squareface( third ) ] ) def get_max_index( lis ): idx = 0 max = 0 for i in range( 0, len( lis ) ): if lis[i] >= max: idx = i max = lis[i] return idx def sampling( ntrial ): visited = [ 0 for i in range(0, len(cells))] pos = 0 tried = 0 # should I count first GO as visited ? while tried < ntrial: nextpos = nextcell( pos) #print len( visited ), " ", nextpos visited[nextpos]+= 1 pos = nextpos tried +=1 return visited def nextcell( current_position): global prev_doubles score1 = random.randint( 1, 4 ) score2 = random.randint( 1, 4 ) if score1 == score2: if prev_doubles == 2: prev_doubles = 0 return 10 else: prev_doubles += 1 else: prev_doubles = 0 next_position = advance( score1+score2, current_position ) #print score, next_position if cells[next_position] == 'CC': return ccjump( next_position ) elif cells[next_position] == 'CH': return cjump( next_position ) elif cells[next_position] == 'G2J': return 10 else: return next_position def ccjump( current_position ): card = drawcc() if card == 'DC': return current_position else: return int( card ) def cjump( current_position ): card = drawc() if card == 'DC': return current_position elif card == 'G2NR': return g2nr( current_position ) elif card == 'G2NU': return g2nu( current_position ) elif card == 'GB3': return back( 3, current_position ) else: return int( card ) def g2nr( current_position ): while( True ): current_position = advance( 1, current_position) if cells[current_position] == 'R': return current_position def g2nu( current_position ): while( True ): current_position = advance( 1, current_position ) if cells[current_position] == 'U': return current_position def advance( nsteps, current_position ): while nsteps > 0: current_position+=1 if current_position > len( cells ) - 1: current_position = 0 nsteps-=1 return current_position def back( nsteps, current_position ): while nsteps > 0: current_position -= 1 if current_position < 0: current_position = len( cells ) - 1 nsteps -=1 return current_position def shuffle_cards(): global ccards global cccards random.shuffle( ccards ) random.shuffle( cccards ) def drawc(): global ccards drawed = ccards.pop( 0 ) ccards.append( drawed ) return drawed def drawcc(): global cccards drawed = cccards.pop( 0 ) cccards.append( drawed ) return drawed def encode_squareface( num ): print "n : ", num if num < 10: return '0'+str(num ) else: return str( num ) prev_doubles = 0 pe84()
なんだかとてもまじめに書いた。
