私はSkienaの『Algorithm Design Manual』 (訳注：『アルゴリズム設計マニュアル』 上巻 ・ 下巻 ) を読んでいました。ところでこの本は素晴らしい本で、連結リストと配列についてこんな比較をしていました(chapter 3.1.3)。 連結リストが静的配列に勝る相対的な長所には以下のものがあります。： • メモリが本当にいっぱいにならない限り、連結構造にオーバーフローが生じない。 • 連続的な(配列)リストに比べて、挿入と削除が単純である。 • 大きなレコードを扱う場合、要素自体を動かすよりもポインタを動かすほうが容易かつ高速である。 一方で、配列の相対的な長所には以下のものがあります。 • 連結構造には、ポインタのフィールドを格納するための余計な領域が必要となる。 • 連結リストでは、要素に対する効率的なランダムアクセスができない。 • 配列は、ランダムなポイン

JavaScript を使って小数を整数に変換する（小数部分のカット）いろいろな方法の紹介です。Math.random() を利用するときによく使うでしょうか。最も一般的な方法は Math.floor() を使うものだと思うのですが、他の方法でも出来るので紹介してみます。 ついでに実行速度まで計測してみました。 「切り捨て」のみに着目しています。「切り上げ」や「四捨五入」はまた別の方法になりますのでご注意ください。 Math.floor(number)Math.floor(5.368) //→ 5一番使われる有名な方法です。 ただしこの方法は、「プラス値」であれば「小数部分のカット」になるのですが、数値が「マイナス値」だった場合は挙動が違いますので注意してください。 Math.floor(-5.368) //→ -6つまり、Math.floor() は「値を切り下げる」ということです。その

先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in

ここHumanGeo社ではPythonを使うことが多く、それは極上の楽しみでもあります。美しく機能的なコードを短時間で記述するのにPythonはうってつけで、私個人にとっても一押しの言語です。仕事に限らずプライベートでも使っています。そんな素晴らしいPythonですが、欠点がないわけではありません。それはあまりにも遅いことです。幸いPythonには、コードをプロファイリングするための優れたツールがいくつかあるので、コードの美しさと速さを共存させることができます。 HumanGeoで働き出した頃、実行に長時間を要すプログラムのボトルネックを探り、何とかしてそれを速くさせるという仕事を担当しました。その内容は、 cProfile や PyCallGraph （ ソース ）、はたまたPyPy（高速なPython用代替インタプリタ）などの各種ツールを使って、プログラムを最適化するためのベストな方法

qiitaでこんな記事がありました。 innerText(textContent)/innerHTMLを使わずJavaScriptでHTMLエスケープ - Qiita で、思い出したのですが「文字クラスでreplaceを一度で済ますより、単純なマッチを直列で繰り返したほうが速い」って話しをどこかで聞いた覚えがあるので、どのぐらい差があるのか、ちょっと試してみました。 念のため、元記事の関数でテーブル参照をしないバージョン（escapeCharClassEx）も用意。 3パターンのescape関数 // 元記事の関数 var escapeCharClass = function(content) { var TABLE_FOR_ESCAPE_HTML = { "&": "&amp;", "\"": "&quot;", "<": "&lt;", ">": "&gt;" }; return co

Perl Advent Calendar 2014の枠が空いていたので、ただのメモですが10日目の記事として晒すことに。 今さらかなり基本的なことだけど、Perlでのベンチマークの実行方法を調べて、適当にいろいろ試してみたメモ。 Benchmarkモジュール 基本的にはperldocを見れば良い。 ゆとりなのでPerldoc.jpにて。 いろいろ関数があるけども、よく使いそうな雰囲気なのは次の2つな気がした。 timethis : 特定のコードの実行速度を測る cmpthese : 複数のコードの実行速度を測りつつ比較する timethis DateTimeは遅いって言われているけど、実際にどれくらい遅いのか試しに測ってみる。 現在の時間を取得して1日足すという処理を例に。 timethisの1つ目の引数は、2つ目の引数の処理を実行する回数を示している。 第2引数には、CodeRefかev

ポエムばかり書いてるわけにもいかんので、新しい卒論の現実逃避をする。 「CoffeeScriptの関数は明示的にreturnしてはいけない理由」を探す暇あったら他にやるべきことあるのでは？ - mizchi's blog http://mizchi.hatenablog.com/entry/2013/12/16/184306 みたいな記事を書いてしまった以上、ダグラスクロックフォード卿の「JavaScriptのwithは遅いので使うべきではない」という神話を検証してみなければと思っていた。2014年においてはどうなんだろうか。 自分自身、たまにメタプロしたくなってwithを使いたい気分になることがある。John Resigとかはwith肯定派だと噂に聞いている。 実測 というわけで適当なスクリプトをでっちあげてベンチしてみる。環境は node v0.10.22 一番最初にでっち上げたコード

Pythonスクリプトの速度を計測し、そのボトルネックを探る。さらに、メモリ使用量、メモリリークの原因特定までの調査方法を解説する。 あなたが書いたすべてのPythonプログラムで厳密なパフォーマンス計測が必要になるというわけではないにせよ、その時が来たら、役に立ってくれる様々な種類のツールがPythonのエコシステムにはあるのだということを知っておけば安心できるだろう。 プログラムのパフォーマンスを計測することは、すなわち以下の4つの基本的な質問に答えることだと要約できる。 どのくらい高速に実行できるか？ スピードのボトルネックはどこか？ どのくらいのメモリを使うか？ メモリリークしているのはどこか？ これから、いくつかの素晴らしいツールを使ってこれらの質問に答えていくための詳細を見ていこう。 大ざっぱな実行時間 素早くざっくりとコードの実行時間を計るのに、古き良きUNIXのユーティリテ

「Ｊａｖａの高速化の方法」というページに、次のような高速化手法が書かれていました。 文字列がNULLかどうかの判断は IF文を使用せずに 例外処理NullPointerException で置き換える if文の場合です。 if(obj == null) { /* process */ } try/catchの場合です。 try { /* process */ } catch (NullPointerException e) {} たまにこういう謎の高速化手法を教えてもらうのですが、どうしてもすぐには信じられないので少し調べました。 ifとtry/catchのオーバーヘッドは？ Stack Overflowに、ドンピシャな質問がありました。 Java if vs. try/catch overhead 読んでみると、「例外処理は例外的な処理に使うものだから、通常のフローでnullになるような

普段、Pythonのコードは何となく速かろうという、言ってみれば勘で書いているのだけど、その勘とやらは往々にしてウンコードを生むものである。そこで、プロファイラを使っていきたいと思う。 使えそうなツール そういうわけで、いくつか使えそうなツールをリストアップした。 経過時間のプロファイラ ツール名 メモ profile ビルトイン, ピュアPythonの決定論的プロファイラ cProfile ビルトイン, C拡張の決定論的プロファイラ line_profiler 行単位の決定論的プロファイラ Plop 統計的プロファイラ, Dropboxの人が作ってる statprof 統計的プロファイラ, 開発停止？ yep 拡張モジュール用の統計的プロファイラ, バックエンドにgoogle-perftools メモリのプロファイラ ツール名 メモ memory_profiler 行単位でメモリ消費量の

自分は普段からJavascriptを書く機会が多いのですが、Webサイト構築ではDOMを扱うことがほとんどです。 最近はjQueryなどのライブラリを利用する方が多いのではないでしょうか。 今回はDOMを取得する際のパフォーマンスに着眼して、今一度整理してみたいと思います。 とりあえずテストしてみた JSPerfで要素を取得するメソッドをそれぞれ追加しました。 basic DOM selector test | JSPerf そして、自分の所持している PC , SP の各ブラウザからRUNボタンをポチポチ押します。 テスト項目 テスト項目は以下の通りです。 ピュアなJSでの取得とjQueryでの取得を選択しています。 getElementById getElementsByTagName getElementsByClassName querySelector querySelector

最近、自作の プログラミング言語 を作っていて、ベンチマークを取るためにいくつかの言語で 竹内関数 を書いてみました。 そこで調べている中で、結果をメモ化したり遅延評価したりすることで高速化させることができると知ったのでJavaScriptで書いてみた次第です。 まずは下ごしらえ 環境は以下の通りです。 Intel Core i3 1.8GHz node.js v0.10.5 64bit で、次の様なユーティリティーを書いてみました。 /** * ベンチマーク用関数 * @param {Number} n 実行する回数 * @param {Function} fun 測定する関数 * @return {Object} averageに平均が、resultsに各結果が入ったオブジェクト **/ function bench(n, fun) { var i, start, finish, av

ブロックスコープを作る構文をちゃんと性能比較してみました。 ブロック構文の性能比較 前回の記事で書いたcreateScope関数もセットにしました。 function createScope(prev) { var newScope, Scope=createScope.Scope; if (prev instanceof Object) { Scope.prototype = prev; newScope = new Scope; newScope.__outer__ = prev; return newScope; } else { Scope.prototype = null; return new Scope; } } createScope.Scope = function(){ this.my = this }; ひとまずFirefoxでの測定結果をのせます。 ブロック自体の生

python専用のプロファイラー，cProfileを使ってみました。 プロファイラーって？ 実行されているプログラムの処理のいろんなものを測定してくれる開発ツールの事をさします。 多くの開発者はプロファイラーを使って関数単位で処理時間を測定してプログラムのボトルネックを探します。 C言語でLinux環境な人なんかはプロファイラーとしてvalgrindにcallgrindをのっけて測定とかよくやってますね。 とはいえ開発しているターゲットや開発環境によってはプロファイラーが無い，あっても使えない場合もありますが… cProfileとは？ python用のプロファイラーです。 MacOSX等はXCodeを入れればこれらもインストールされるでしょう（多分，気づいたら入ってました！）。 Ubuntu10.04だと素の状態では入っていないので sudo apt-get install python-

3つとか5つとかそれくらいのデータをまとめて扱いたい時は割とすぐ defstruct してて、他にも list とか vector とか hash-table とか色々やり方はあるんで、それぞれ速度的にどーなのよ？と。xyzzy だとそこまで速度を気にすることはあんまりない（compile しないで使ってたりするくらいだし、ヘビーな計算とかするなら SBCL とか使うだろうし）のだけど、気になったので調べてみた。 速い方からざっくり。データ型で言うと (simple-)vector, list plist, alist, hash-table structure アクセスする関数で言うと 速い組み込み関数*1 second, cadr, svref, elt first とか car とかでもほぼ変わらない 遅い組み込み関数 si:*slot-value, si:*index-slot-v

バッチ処理スクリプト書いてて思った。perlは変数生成のコストが意外に高いって以前聞いたのだけど、どんくらいなのかなと。 use strict; use warnings; use Benchmark qw/:all/; sub gen_once { my ($ho,$ge,$fo); my $re; for (1..1000) { $ho = 1; $ge = 2; $fo = 3; $re = $ho + $ge + $fo; } return $re; } sub gen_each { my $re; for (1..1000) { my ($ho,$ge,$fo); $ho = 1; $ge = 2; $fo = 3; $re = $ho + $ge + $fo; } return $re; } cmpthese(5000, { gen_once => sub { gen_once