ブラウザでグリッドコンピューティングとかやったらどうか
最近はコンピュータの性能上がっているし、JITだしで、
ブラウザ上で重い処理をやっちまっても結構何とかなっちゃいます。3Dとか扱えちゃうしね。
おまけに、Web Workersなんか使っちゃえば、javascriptでマルチスレッドまでできちゃう。
それじゃあ、こんなのはどうか。
というわけでjavascriptで、グリッドコンピューティング。
計算させたいコードをクライアントがアクセスするページに埋め込んどけば、
BOINCみたいなことができるんじゃないか、というかできる。きっと。
onloadしてから別スレッドでまわせばストレスも（たぶんそんなに）ない（かもしれない）。
そのうちそういう世界になるんじゃね？という気がしています。
可能性としてありえるのは、アクセス数の多い検索サイトとか、
滞在時間の長いゲームのサイト側が勝手にその手の仕組みを埋め込んで、
ユーザのCPU時間を勝手に搾取するという、「勝手グリッド」みたいなこと。
でもそれはそれで楽しい。
HTML5の仕様書を見て歳を感じる
HTML3.2の頃を知る身としては、隔世の感があると本当に思う次第です。
世間はcanvasだvideoだと賑やかですが、個人的には廃止になった機能に目がいきます。
HTML5のobsolete項を見ると、レイアウト系のattributeが結構削られています。
特に、table系要素のalign/valign等が削られているのを見ると、意地でもテーブルレイアウトの時代を終わらせるぜ、CSS万歳！という気概が感じ取れます。
また、レイアウトとは違うけど、bodyのbgcolorやbody/tableのbackgroundが削られていたりします。
レガシーな人間としては、「うお、マジッスか！」と嫌でも思う。
CSSがあるのに必要かと言われると、全然、ですが。
で、今回の（廃止の)ハイライトは、frame/frameset, marqueeタグでしょう。
かつてHTML覚えたての人の作ったダサダサなページの見本といえば、
無意味なframe、謎のmarquee、どこかで拾ってきた鬱陶しいjavascriptというのが相場でした（勝手にそう思っている）。
javascriptは世界を席巻しましたが、われらがframeとmarqueeはあえなく時代遅れとなりました。合掌。
蛇足ですが…
そんな風に名指しで「使うなよ！」といわれちゃってるmarqueeタグなんですけど、地味にHTML401の仕様ではないんですね。
IEの独自実装を他ブラウザがパクったもの、だったはず。
それなのにもかかわらず、わざわざ新しい仕様が「marquee廃止ね」って言うのは、何なのお前。何様よ？といいたくなりますね。なりませんか。そうですか。
ま、使いたきゃ使えるんですけどね、frameもiframeで何とかできるし、
marqueeはCSS3に移っただけだしね。
IEEE754の分布について
積年の謎が氷解した日。
IEEE754で表現される浮動小数の数値の分布はどうなっているのか。
表現可能な数値間の距離はそもそも一定なのか？一定じゃないのか？
感覚としては0を中心として数直線の両側にいくにつれてスカスカになりそうだけど…
一定じゃないなら、どんな感じになってるんだろうか？
結論を言うと、全く一定じゃなく、感覚が正解。
大学の授業でIEEE754は扱ったのだけど、その辺まで詳しい話は出てこなかった。
どうも大学で情報系を専攻している人たちはその辺まで突っ込んできちんと授業を受けているみたいですね。
というのも、「プログラマが知るべき97のこと」というオライリー本で計算誤差の説明のついで？に、
隣接する数値間の距離について言及されていました。
で、さらに色々とググったら、こんなのとか、こんなのとか出てきた。素晴らしい。分かりやすい。
特に前者は数直線での数値の密度の模式図まである。
そうなると次に気になるのは、そんなんで不都合ないのかということ。
もちろん丸めの誤差が、累乗の数字が大きくなるにつれてどんどん大きくなっていくというのは既に分かりやすい問題だけど。
ううん、この辺の話は楽しいなぁ。なんだかわくわくする。情報科学科の方々は幸せだ。
JavascriptのMath.random()でユーザートラッキングができるという話
表題の件について。
地味な話ですが、javascript（というかECMAの仕様）にあるMath.random()には、乱数のシードを与える方法が無いようです。
そんなわけで、われわれ一般市民は各ブラウザが独自に実装している、謎のシードで初期化された謎のアルゴリズムで作られた乱数を通常使うわけですが。
曰く、Math.random()のシードによる初期化は、ブラウジングセッションごとに1度しか行われないと。
で、シードはまあ、かぶる率そんなに高くなさそうなので、そのシードをUSERの（擬似的な）ID代わりにしてしまえば、ユーザーのトラッキングができるよーん、とのこと。
はじめ読んだとき、「おおー、かっけー！」と思ったんですが、ちょっと待て。
シードって外から取れんのか。
というわけで、色々調べたところ、各ブラウザは（多分IEも）線形合同法による擬似乱数を使っていると。
線形合同法ってのは、あれです。cmath.hのrandって言えば大体分かりますか。普通の早くて安い乱数です。
で、こいつはジェネレータが何ステップ目の状態かをリバース簡単に出来る→乱数シードをリバースさせることができるよん、とのこと。
これは驚き。言われてみればそりゃそうなんだけど、そうか、シードをリバースエンジニアリングするなんてこと、考えたことも無かった。
ちなみに、後半のソースはこれ。
Firefoxだけじゃなくて、他のブラウザにも言及して、ソースコードまである。すげえ。
ちなみに、すでにIE9についても同型の問題を確認しているようです。
某visit historyみたいなことにならないといいですねえ…。
Firefoxは、少なくとも冒頭のものについてはパッチが当たっているみたいですが、他はどうなんでしょ。
Jaro-Winkler距離
以前、スペルミスや「もしかして」系の機能の裏で動く技術としてわりと知られているLevenshtein距離についてちょっと書いてみました。
今回はそれと同様な用途に用いられがちなJaro-Winkler距離。
Jaro-Winkler距離というのは、Levenshtein距離同様に文字列同士の近さを数値化するアルゴリズムです。
距離って言っても、数値が小さいほうが遠いので気をつけましょう。cos距離みたいなかんじです。
こいつは、Jaro距離という、これまた謎の文字列類似度計測指標にすこしだけ改良を加えたもので、肝はJaro距離です。
その少しだけの改良というのは、（式を見る限り）プレフィックスのexact matchは重視しようか、という程度のもの。
で、パパっと作れると思ったら、意外とてこずった。
Jaro距離では文字同士の一致を取るのですが、マッチとする文字の文字位置に一定の範囲をもうけ、そのウインドウ内での一致を取ります。
また、文字位置の交換によるマッチが可能であるかどうか？という転置の考えも取り入れています。
この転置が曲者で、しばらくうんうんうなってました。
というわけでコード
// valid_distance = -1 : not consider distance between characters unsigned int getNumRangeMatchChar( const std::string &s1, const std::string &s2, const int distance = -1 ){ unsigned int l1 = s1.size(); unsigned int l2 = s2.size(); bool ignore_distance = false; if( distance < 0 ){ ignore_distance = true; } unsigned int counter = 0; for( unsigned int i = 0; i < l1; ++i ){ // setting search range unsigned int from = i; unsigned int under = l2; if(! ignore_distance ){ from = ( i < (unsigned int)distance ) ? 0 : i - (unsigned int)distance; under = ( i +(unsigned int)distance >= l2 ) ? l2 : i + (unsigned int)distance; } for( unsigned int j = from; j < under; ++j ){ if( s1[i] == s2[j] ){ ++counter; } // NOTICE : this code consider the case i == j ( both place and character match ) } } return counter; } std::string getRangeMatchChar( const std::string &s1, const std::string &s2, const int distance = -1 ){ unsigned int l1 = s1.size(), l2 = s2.size(); bool ignore_distance = false; if( distance < 0 ){ ignore_distance = true; } std::string ret = ""; for( unsigned int i = 0; i < l1; ++i ){ // setting search range unsigned int from = i; unsigned int under = l2; if(! ignore_distance ){ from = ( i < distance ) ? 0 : i - distance; under = ( i + distance >= l2 ) ? l2 : i + distance; } for( unsigned int j = from; j < under; ++j ){ if( s1[i] == s2[j] ){ ret += s1[i]; } // NOTICE : this code consider the case i == j ( both place and character match ) } } return ret; } unsigned int getNumTransposition( const std::string &s1, const std::string &s2 ){ unsigned int c = 0; for( unsigned int i = 0; i < s1.size() && i < s2.size(); ++i ){ if( s1[i] != s2[i] ){ ++c; } } return c; } // Error the case s1 & s2 are empty double getJaroDistance( const std::string &s1, const std::string &s2 ){ int distance = ( s1.size() > s2.size() ) ? s1.size() : s2.size(); if( distance < 0 ){ return -1; } distance = distance / 2 - 1; if( distance < 0 ){ return -1; } int match = getNumRangeMatchChar( s1, s2, distance ); int trans = getNumTransposition( getRangeMatchChar( s1, s2, distance ), getRangeMatchChar( s2, s1, distance ) ); double m = (double)match; double t = ( (double)trans ) / 2.; return ( m / (double)s1.size() + m / (double)s2.size() + ( m - t ) / match ) / 3.; } unsigned int getLengthOfCommonPrefix( const std::string &s1, const std::string &s2 ){ unsigned int c = 0; for( unsigned int i = 0; i < s1.size() && i < s2.size(); ++i ){ if( s1[i] == s2[i] ){ ++c; } else { return c; } } return c; } double getJaroWinklerDistance( const std::string &s1, const std::string &s2, const double scaling = 0.1 ){ if( scaling < 0 ){ return -1; } double j = getJaroDistance( s1, s2 ); return j + getLengthOfCommonPrefix( s1, s2 ) * scaling * ( 1 - j ); }
ミソは、マッチを取るときに軸足をstring1とstring2どちらにおいても同じ数字が得られるのだけど、
マッチした文字をマッチした順に並べると、軸足の置き方によって順番が変わるよね、という話。
Levenshtein距離より精度がいいぜ、という発言をたまに聞きますが、意味が分からないのでそういう考え方はしないほうがいいと思います。
ものの尺度なので。
バグのデータベースとか
バグトラッキングシステムをお使いの皆様方こんばんわ。
唐突ですが、失敗知識データベースってご存知でしょうか。
たしか、科学技術関連の雑多な「失敗」をデータベースとして管理公開して、
みんなで教訓を共有しようぜ！というプロジェクトだったと思います（うろ覚え）
どうもこのサービスは終了が決定しまったようですが。
最初は面白くて色々とみて、へーへー言っていたのですが、だんだん飽きてきてすぐに見なくなった覚えがあります。
こういうのが、「バグ」に対してあってもいい。いやむしろあるべきだと思います。
前述のDBにはコンピュータで起こった過去の失敗事例というものが入っていますが、
かなり具体的な、個別のインスタンスの事例と実際の対策であって、もちろん有用と思いますが、もう一歩踏み込みたいところです。
すなわち、問題をより抽象化し、デザインパターンならぬバグパターンのようなものを考えて、みてはどうだろうか。
デザインパターンというと数はそんなに無いけど、バグパターンだったらわりと数ありそうなのでDBとして蓄積し、それを共有財産にしてはどうだろうかという感じです。
もちろん、数が少ないなら、4人集まって本を出せばいいと思います。
とずっと思っていたんですが、本日その道では有名な人の講演を受けたら、
似たようなことを考えていて、それなりにきちんと作っているそうな。
僕のぼんやり思っていたものに比べ、断然かっちりしていて、差異はあれど、それはそれで。
すごい人っているのね。
と、ここまで書いて、たった今ググったら、バグ・パターンという言葉自体がすでに言っている人いるし。
これ。
アンチ・パターンまでは知っていたけれど、これは。
記事で扱っているターゲットの粒度は僕の考えているものと少し違うけど、これはこれで。
こういうことがあると、自分の考えは正しいという気になれる一方で、
自分ごときが思いつくことはもう誰かが思いついているのだと、ちょっと寂しくなる。
json hijack、ブラウザセキュリティ、サイト側のセキュリティリテラシーとかなんとか
JSONハイジャックでよく攻撃の例として挙げられるパターンとして、
サイトAの認証Cookieを持ったマシンBが、攻撃者Cのサイトにアクセスした際、
BにAからデータをリクエストさせるという例が良くあります。
形式的にはまあ、昔々からあるお話で、通路がJSON、というかjsというだけですね。
こういったCookieの情報を利用してリクエストを投げさせるっていうのはわりとしょっちゅうで、
クロスサイトリクエストフォージェリもおんなじ様なことをしてます。
JSONだとArrayコンストラクタとかを改造して、うまいことデータを抜くのが主な用途？ですが、
CSRFの場合は、リクエストそのものに意味？がある感じでしょうか。
最近だと、この手の脆弱性に対して、ブラウザ側でも対策を入れるようになってきているようです。
ですが何が切ないって、この辺の脆弱性といわれるものって、個人的には、ですが、わりとサイト側のつくりが悪いに尽きると思っているからです。
ブラウザ屋さんはSafety Browsing!とかなんとか言いたからやっているのかもしれませんが…
むしろその辺に頼らせるようになった場合、UAとかで判断して、いつもは正常なサイトなんだけど、
古いブラウザやマシン、アップデートの難しい組み込みブラウザなんかを使っている人たちが来たら攻撃、
みたいな感じで狙い撃ちするような攻撃者が増えるだけなのでは。そのほうが露見が遅そうだし。
根本的な問題は、やっぱりサイト側にある（あくまで個人的な考えですが）以上、その辺を何とかするべきなんじゃ…
まあ、多分やらないわけにはいかないんでしょうけどね。
なんというか、Cookieもjsも、本当に出たてのころ（Netscapeとか、あのあたり）は、
危ない危ない言われていましたが、結局やっぱり色々と攻撃手法が出てくるもんです。
最近だとFileAPIとか、JSONPですか？
今のうちにあら探しをしてみると、意外な落とし穴があるのかもしれません。
WebSQLは、どうせXHRみたく各ブラウザが微妙な互換の別実装をするでしょうから構えておいていい気がします。
もうすでにあらかた食い尽くされた後なのかもしれませんが、少なくとも僕は知りません。
見つけてもお願いですから悪用はしないで欲しいですが。
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/"
