Three-way quicksortをJavaScriptで書いた。
普通Quick Sortっていうと、ピボットが1つなんだけど、ピボット2つで区間を3分割して考えるのが3-way quicksortです。
分割された区間は、ある値よりも小さいか、同じか、大きいか、で分けられているだけで、それ以外は普通のquicksortです。
例によってJavascriptで書きました。本当に誰得。
さらに例によってデモを作った。
整列の様子を視覚的に分かりやすくたデモを作りたかったのですが、タイムアップで単純にソート前とソート後しか表示されません。
これじゃあ中でバブルソートやっていてもわからない。何のためのデモか。
これだけではうまみがあまり無いのですが、ソートの対象が数字ではなく文字列や配列である場合、3-wayをうまく使ったmultikey quicksortという手法を使うと高速な整列が可能になります。そのあたりはまあ、そのうち。
追記
Multikey-Quicksortは割合ベーシックな話なのでオワコンだと思っていたのですが、昨年、IBIS 2010で東大の鹿島先生のところの学生さんと話した際、だいぶ違う問題に転用していて、認識を改めたのを思い出した。
JavascriptでTrieデータ構造のVisualizationをやってみた
TRIEに対するオペレーションを視覚的に表示する謎のスクリプトを書いた。視覚化、といっても、要するにツリーを作るコンポーネント使っただけ。視覚化しなくてもTRIEは分かりやすいので誰得もいいとこなんですが、それはそれ。
こちらで遊べます =>"Trieのデモ"
見た目は、
こんな感じ。
YUIを使ってみた。牛刀をもって鶏を裂く。
ついでにtrieのコードもはっておく
new function(){ // private var nnodes = 0; Node = function( value ){ this.count = 0; this.value = value; this.leaf = " this.children = []; this.isEmptyWord = function( word ){ return word === undefined || word === null || word === ""; } this.nnodes = 0; //except root node this._insert = function( word, data ){ if( this.isEmptyWord( word ) ){ if( this.leaf === null ){ this.count++; this.leaf = data; return true; } } else { var ch = word[0]; var child = this.children[ ch ]; if( child === undefined ){ this.children[ ch ] = new Node( ch ); child = this.children[ ch ]; ++nnodes; } if( child._insert( word.slice(1), data ) ){ this.count++; return true; } else { return false; } } }; this._remove = function( word ){ if( this.isEmptyWord( word ) ){ if( this.leaf === null ){ return false; } else { this.leaf = null; return true; } } else { var ch = word[0]; var child = this.children[ ch ]; if( child === undefined ){ return false; } if( child._remove( word.slice(1) ) ){ if( child.count == 1 ){ delete this.children[ch]; } child.count--; --nnodes; return true; } else { return false; } } }; this._find = function( word ){ if( this.isEmptyWord( word ) ){ if( this.leaf === null ){ return null; } else { return this.leaf; } } else { var child = this.children[ word[0] ]; if( child === undefined ){ return null; } else { return child._find( word.slice(1) ); } } }; return this; } // public Trie = function(){ this.root = new Node( "/" ); this.insert = function( word, data ){ this.root._insert( word, data ); }; this.remove = function( word ){ if( this.root._remove( word ) ){ this.root.count--; } }; this.find = function( word ){ return this.root._find( word ); }; }; }
↑これは、trieとして必要な部分を抜いただけのものなので、動作確認してませんのであしからず。学校の課題とかには使わないほうがいいと思う。。。
最近jsのエントリが続いているのは、GUIが脳みそ一切使わなくても作れて楽だからです。
JavaScriptでDancingLinksアルゴリズムによる数独ソルバを作った
昨今のJSエンジンはすごい。とにかく速い。3Dとかもやれちゃう。
なんだかもう、前処理はクライアント側でやらせて、サーバはサボっててもいいんじゃないか。
どんなやつでもかかってこいという感じですか。まあ、一部ブラウザは除きますが・・・
そんなわけで、JavaScriptで何か重めの処理走らせてみよう。きっと超絶スピードでサクサクやってくれるはずだ!
というモチベーションの元、数独ソルバをjsで作ってみた。
数独をとかないと世界が破滅するようなシチュエーションで使ってみてください。
↓ここにあります。
http://kogecoo.sakura.ne.jp/scripts/dancing_sudoku.html
恐ろしいことにChromeでしか動作確認をしておりません。
以下駄文
書きなぐってポイ、という感じなので色々と不備があるかもしれません。
検算とか手でやったわけじゃないので、ちゃんと解けているかどうかは保障しません。。。
jQuery使っているのでリッチなブラウザ使ってください。コア部分は多分ECMA 3rdでも通じるくらい何もしていないので、誰か携帯用とか書きたければ書いてください。
数独の解を探すアルゴリズムは、Knuth先生が広告塔をやったDancing Linksというアルゴリズムを使いました。学生のときにJavaで書かされたものを書き直す形で最初はじめたのですが、最終的には原型をとどめていません。
Dancing Linksは、縦方向と横方向に双方向リンクをもつノードを2次元平面状に並べた構造で実現されていて、Exact Coverな問題に対するバックトラッキングの高速化をするアルゴリズムと知られていると僕は記憶しています。細かい話は元論文が非常に分かりやすいので、興味があればぜひ。
また、数独のExact Coverとしての解釈はWikipediaが、これまためちゃくちゃ分かりやすいので、こちらも興味があればぜひ。
ちなみにDancing Linksをwebを探すと実装がかなりたくさんあります。ちょっと前は全然無かったんだぜ…
java, c, c++, python, haskell...適用先として面白いんでしょうね。。。
追記
ipod touchの第4世代で動いた!けど画面が足りてない!
Aptana Studio 3とPydevのハイライティング
IDEマンセー言っている割に、最近コード書くときはもっぱらvimかサクラエディタです。こんばんわ。
そんな僕も時代の流れに乗ってAptana Studio 3を触ってみました。まあ、eclipseもaptana 2も触ってはいたわけですが。
3になって、デフォルトのカラーテーマが黒背景・白文字でとてもよろしいのですが、Pydevと共存させたときに、背景黄色、文字白。見えないよ。
この設定探すのにすごい時間がかかった。apntanaが悪いわけじゃないんだけど、配色関係の設定は、Preferenceのあちこちに分散しているので探しにくかった。
のでメモ。
Preference -> General -> Editors -> Text Editors -> Annotations -> Occurrence (Pydev )
1時間も探したよ。
HTML5にフル対応させ(たようにみせかけ)る
HTML5が待ち遠しくて待ち遠しくて、各種ブラウザも徐々に対応はしてきているのだけど、もう待ちきれないよ!とお悩みの紳士淑女の皆様。
そんなHTML5フリークな皆様は、ブラウザのアップデートのたびに、HTML5testでスコアを確かめ、一喜一憂していることでしょう。
そんなあなたに朗報。HTML5にフル対応させるスクリプト書きました。
すいません嘘ですHTML5にフル対応した気分になれるスクリプトです。
Firefoxさんが、
Operaさんも、
時代の先を行っちゃったぜ。
再現手順
1.Operaまたはgreasemonkeyの入っているFirefoxを用意
2.以下のリンクからダウンロード/インストール
3.HTML5testでHTML5フル対応したことを確認する
3.HTML5testでHTML5フル対応したように見せかけられてしまったことを確認する
4.にやりとする
●Zipが嫌ならこの辺
userscripts.org
まあ、つまりはユーザースクリプトです。
本当にすみませんでした。今は反省しています。
怒られるか、飽きたら消します。
greasemonkeyでグローバルスコープの汚染をしたい
表題がおかしい。
greasemonkeyのスクリプトはブラウザで表示しているwindowのスコープとは別なスコープで動きます。
これは、greasemonkeyスクリプトで使用している名前と、サイト側で使っているjavascriptの名前が衝突しないようにするための工夫ですね。
逆に、サイト側の名前空間を汚染したいよう、というときはどうすればいいんだろう。
with( unsafeWindow ){}
これでscriptを囲むだけ。unsafeWindowって名前すごいね。
documentオブジェクトの挙動を変える
あー、getElementByIdの動作変えたいなーとか、createElementの動作変えたいなー、という要求は多いかと思います。あ、javascriptの話ですよ。
そんな変テコなことを考えるあなたにはこれ。インスタントdocument wrapping、もしくはdocumentのプロパティの上書き。そのまんま。
どうするかっていうと、documentのオリジナルのプロパティをそのまま上書きするだけ。ただ、既存の動作も残したい場合はちょっと面倒。
所望のプロパティのオリジナルを一時的に保存し、上書きする。意図としてはthisがdocumentなので、callでdocumentを指定。
こうすることで、わりと直感的なdocumentのオーバーライドモドキができます。
以下はdocument.createElementでdivを作ろうとするとspanができて、spanを作ろうとするとdivができるという、ヘンチクリンなコード。オーバーライドでやっちゃいけないことの代表例w
var temp = {} temp.createElement = document.createElement; document.createElement = function( arg ){ switch( arg ){ case 'div': return temp.createElement.call( document, 'span' ); break; case 'span': return temp.createElement.call( document, 'div' ); break; } return temp.createElement.call( document, arg ); } </html>
window.documentでも同様なことができる(はず)
HTMLのサンプルはこちら。
<html> <head> </head> <body> <div id="foo"></div> <script type="text/javascript"> var temp = {} temp.createElement = document.createElement; document.createElement = function( arg ){ switch( arg ){ case 'div': return temp.createElement.call( document, 'span' ); break; case 'span': return temp.createElement.call( document, 'div' ); break; } return temp.createElement.call( document, arg ); } document.getElementById( 'foo' ).appendChild( document.createElement( 'div' ) ); </script> </body> </html>
見た目には変化ないですが、先述した動作をしとります。domインスペクタで見ると良いかと。
使い道は全く不明ですが。
こんなヘンテコな遊びに付き合ってくれた友人に感謝。
スマートフォンへの懸念
特に日本では、だと思うのだけど、これまでの携帯電話のブラウザと同じような感覚で
みんなiPhoneとかAndroidでフルブラウザ使っている(あたりまえだ)。
これにちょっと警鐘を。今更僕が言うまでもないのですが。
わりと最近認識されてきたっぽいですが、セキュリティ面でかなり懸念があります。
正確には、バージョンの古さが問題なのです。まあ当たり前ですが。
そりゃあ当たり前で、バージョンアップにはバグフィックスも含まれている、
逆に言うと新しいバージョンがリリースされたときには、古いバージョンにあった、
問題が認知されてしまっているわけです。セキュリティ面も含めた、です。
組み込み機器はアップデートのしにくい世界、これはかなり致命的になるわけです。
Androidで言えば、メーカーのアップデートの頻度等をみるとわかるかと思います。
コストすごいしね。
そんなわけで、脆弱性を抱えた端末は、巷にゴロゴロ転がっていて、
たとえばWebKitで過去に認知された問題等を突けば攻撃できる、
というような状況に既になっているような気がします。
それについては、iPhoneにしても状況は全く一緒だと思います。
たとえばAndroid ver.x向け攻撃コード、なんてのがこういうのが認知された瞬間作られてしまうわけですよね。
ここまで言えば、「あー、今あれが狙い目だなー」とかみんな考えるんじゃないでしょうか?
これまでのガラケーは、わりとクローズドなコンテンツの世界だったり、
jsがまともに動かなかったりで、逆に助かって(?)いたのだけど、時代はフルブラウザ。
スマートフォンブームに乗ろうと日本のキャリアも熱心ですが、そのあたりは握りつぶしているんでしょうか。
結局ユーザーが気をつけるしかないっすかね。
実はセキュリティパッチだけは頻繁に自動であてていたり?なんていう期待をしちゃあいけないような気がします。
スマートフォンもってないんですけどね、僕。
ブラウザでグリッドコンピューティングとかやったらどうか
最近はコンピュータの性能上がっているし、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に移っただけだしね。