2007-10-13 - 技術日記＠kiwanami JavaScriptで b-tree
導入 ある日突然、JavaScript上で高速に追加・削除が行えて爆速で最小値を検索できる入れ物が欲しくなった。 普通(JavaとかFORTRANとか)ならここで素直に b-tree の実装に入るのだけども、JavaScriptは例によって変態言語なので、実は面倒なことせずにArrayに普通に入れて、素直にソートとか線形探索したほうが速いのかもしれないという疑問を持った。 しかも「最近全然技術日記してない」という突込みが入り、ついカッとなってベンチマークをとってみた。*1 調べ方 以下の3つの入れ物を実装。適当な実装を探してみたが、あまりいいものが無かったので車輪の再実装。 BTree 素直にb-treeを実装。速度よりは読み書きしやすさ優先。スペック通りなら、追加・削除、値の探索が高速。 SortedList 配列を常にソートしておいてb-searchで値探索、spliceで追加・削除。
escapeHTML の実装 3 パターン (ベンチマーク付き) - (new Hatena).blog()
ウェブを扱うライブラリやプログラムで必ずと言って良いほど見かけるものに、escapeHTML という関数があります。 "&" 等、特別な意味を持つ文字を、表示等のために実体参照 (&) に変換するお決まりの関数なんですが、実装には色々とバリエーションがあるものです。 1. String#replace メソッドを繰り返す (MochiKit 等) function escapeHTML(str) { return str.replace(/&/g, "&").replace(/"/g, """).replace(/</g, "<").replace(/>/g, ">"); }このパターンが最も多く見受けられます。Ruby でも同様に gsub を繰り返す方式を見かけることがあります (例: RSS::Utils.html_escape)。 2. Str
"abc".x(2) -> "abcabc" - (new Hatena).blog()
配列に続いて、文字列の乗算メソッドも実装してみましょう。ただし、全然違うアルゴリズムを用います。 String.prototype.x = function (x) { var base = this, result = ''; while (x) { if (x % 2) result += base; x = Math.floor(x / 2); base += base; } return result; };KaoriYa.net さんの BBS ブラウザ "Chalice" の文字列乗算関数 (AL_string_multiplication in alice.vim) からほぼそのまま拝借しています。 どういう理屈か説明しますと、要はビット演算なんですね。1 回のループで要素を倍のサイズに、なおかつループカウンタを 2 で割っています。このことが言わば左ビットシフトとして機能す
GreasemonkeyスクリプトのGM_xmlhttpRequestとかで取得したhtmlとかxmlをいじる場合はxpathだと遅いことが多いかも - gotin blog
GM_xmlhttpRequestはresponseXMLを返してくれない。 DOMを作ってくれない、ということ（作ってくれなくていいんだけど）。 xpathするにはDOMを作る処理が必要になる。 DOMParser使うとか、適当なelementのinnerHTMLに突っ込んだりする。 そのときの処理時間がそれなりにかかるので、正規表現とかでひょいひょいパースするほうが早く終わるケースが多いような気がする。 だけど正規表現だと読みにくくてつかれてしまうので、例えばこんな感じの関数でも定義しておけばそれなりに読みやすくなりそうだしそれなりに速いし、ってことになるかなぁ、どうだろう。 function getTags(html, tagName, className){ var cls = ""; if(className){ cls = "[^>]*?class=\"" + classNam
length プロパティのパフォーマンス: Days on the Moon
「for 文 2.0」(IT戦記) では length プロパティの評価をループの外に出すことにより高速化を図っています。DOM の NodeList オブジェクト (document.getElementsByTagName() などで取得) や HTMLCollection オブジェクト (document.forms などで取得) の length プロパティは「生きている」(オブジェクト取得後の操作が反映される) 、すなわち誤解を恐れずいえば評価のたびに数えなおす必要があるので遅いというのも納得ですが、JavaScript のネイティブオブジェクトである配列の length プロパティはどうなのでしょうか。実際に調べてみました。 以下は 10000 個の span 要素に対する NodeList オブジェクトと配列の length プロパティのパフォーマンスを調べた結果です。数値は
DOM API と innerHTML のパフォーマンス比較 - とっくりばー
404 Blog Not Found:javascript - element.innerHTML はなぜ速く見えるかにて InnerHTMLは速くない。速く見えるだけだ。とあった。Danさんの予測は、DOM APIが遅く見えるのは、DOM Treeを更新していくたびに再描画が走るからではないかというもの。 そうなのかなと思って実験を作ってみました。 複雑なHTMLを文字列として作ってからinnerHTMLに代入するのと、 再描画が一度も走らないよう、あらかじめ複雑なElementを作ってから最後にdocumentにくっつけるようにするの Elementを作ったそばからどんどんdocumentにくっつけていくの で比較しました。↓以下実験。 HTMLタグを生成してinnerHTML DOM APIでElementを生成（最後にbodyに接続） DOM APIでElementを生成（最初にb
DocumentFragmentの考察 - Personnel
DOMユーザーの方は、このようなことが出来たら良いと思ったことはありませんか? NodeListのクローンを作成する NodeListをそのままappendChildのパラメータにする もちろんこのようなことは出来ません。NodeListのitem一つ一つのクローンを作成し、一つ一つをappendChildしなければならないのです。しかし、DocumentFragmentを利用することによって、このような感覚の操作をすることが可能になります。 Foot note この記事のURI参照 http://members.jcom.home.ne.jp/jintrick/Personal/documentFragment.html#seeds ここに、文書A、文書B、文書C があったとします。 文書A <rootA> <item /> <item /> <item /> <
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.habtm.com/articles/2006/06/08/optimizing-prototype-js
?D of K
IT戦記 - Shibuya.js Technical Talk #1 を終えて。