最速インターフェース研究会

連載すんの？
リファクタリングとか嘘で実は実践ビルトインオブジェクトハックなんだけど。

例題
配列 a = [3,5,4,2,1] から一番小さな値と、一番大きな値を取り出すにはどうすればいいか。

多分昔はこんな風に書いてたと思うんですよ。

a = [3,5,4,2,1];
for(i=0;i<a.length;i++){
    if(i == 0){
        min = a[0];
        max = a[0];
    }
    if(min > a[i]){min = a[i]}
    if(max < a[i]){max = a[i]}
}

模範解答として、後先考えないやり方を提示しておく。

a = [3,5,4,2,1];
min = a.sort().shift();// 1
max = a.sort().pop();  // 5

短い。ただし、これをやるとaの内容は並べ替えられて最初と最後の要素が取り除かれる。

a // 2,3,4

内容を破壊してもかまわないなら、こういうやり方がある、ということを踏まえて次に進む。

配列の内容をコピーする

ありがちな間違いとして次のようなものがある。

a = [1,2,3,4,5];
b = a; // コピーしたつもり
b.shift() // 1
a // 2,3,4,5

aもbもメモリ上のどっかにある[1,2,3,4,5]という配列への参照でしかない。
b = a は別の名前でアクセスできるようにしただけであって、コピーではない。
だから、bの内容を破壊するとaの内容も破壊される。

aと同じ内容の、別の配列を作るには次のようにする。

// ごくふつうの、配列のコピー
a = [1,2,3,4,5];
b = [];
for(var i=0;i<a.length;i++){
    b[i] = a[i]
}

Arrayのメソッドとして定義してやると、次のようになる。

Array.prototype.clone = function(){
    var tmp = [];
    for(var i=0;i<this.length;i++){
        tmp[i] = this[i]
    }
    return tmp
}
a = [1,2,3,4,5];
b = a.clone();
b.shift() // 1
// bのみ破壊される
a // 1,2,3,4,5
b // 2,3,4,5

配列のクローンを作成するのには、実はもっとスマートで速い方法がある。
これに気付いたのは最近なんだけど。

Array.prototype.clone = function(){
    return Array.apply(null,this)
}

[1,2,3,4,5].clone() は Array(1,2,3,4,5) を呼び出す。

これを使って最初の例題を解くとこうなる。

Array.prototype.clone = function(){
    return Array.apply(null,this)
}
a = [3,5,4,2,1];
min = a.clone().sort().shift();// 1
max = a.clone().sort().pop();  // 5
a // 3,5,4,2,1

オリジナルの配列の内容は変更されない。

破壊しないソート

そもそも、sortが破壊的なのがおかしいんじゃないのか、とかいう疑問を感じる。
http://namazu.org/~satoru/blog/archives/000043.html

Rubyではsortが非破壊、sort!が破壊的、という区別がある。
Perlでも「@a = sort(@a)」と明示的に代入しなければ元の配列の内容は書き換えられない。

// JavaScriptのsortは破壊的である
a = [5,4,3,2,1];
a.sort();
// aの内容が置き換わる
a // 1,2,3,4,5

Array#sortの機能を置き換えて、オリジナルの配列が変更されないようにするには、次のようにする。

// オリジナルのsortメソッドを保存
Array.prototype.sortIt = Array.prototype.sort;
// コピーしてソートする
Array.prototype.sort = function(){
    var tmp = this.clone();
    return tmp.sortIt.apply(tmp,arguments)
}
a = [5,4,3,2,1];
b = a.sort();
a // 5,4,3,2,1
b // 1,2,3,4,5

これはかなり邪悪なハックだ。
sortが破壊的であることを期待しているコードは動かなくなる。もはや全然リファクタリングではない。

ソートが非破壊だと、cloneを省略して次のように書けるようになる。

a = [3,5,4,2,1];
min = a.sort().shift();// 1
max = a.sort().pop();  // 5
a // 3,5,4,2,1

firstとlastを定義

shiftとpopが少し気持ち悪いので最初の要素と最後の要素を参照するメソッドを定義してやる。

// Rubyのfirstとlastメソッド移植
Array.prototype.first = function(size){
    return (size == undefined) ? this[0] : this.slice(0,size)
}
Array.prototype.last = function(size){
    return (size == undefined) ? this[this.length-1] : this.slice(this.length-size)
}
a = [3,5,4,2,1];
min = a.sort().fisrt(); // 1
max = a.sort().last();  // 5

これで、minは並べ替えた最初、maxは並べ替えた最後、と、定義そのままのコードが完成する。
実際のところ配列が巨大になるとソートが非常に遅くなってしまうのだけど、まあ100や200の配列なら問題は無いだろう。

まとめ

Array.prototype.clone = function(){
    return Array.apply(null,this)
}
Array.prototype.sortIt = Array.prototype.sort;
Array.prototype.sort = function(){
    var tmp = this.clone();
    return tmp.sortIt.apply(tmp,arguments)
}
Array.prototype.first = function(size){
    return (size == undefined) ? this[0] : this.slice(0,size)
}
Array.prototype.last = function(size){
    return (size == undefined) ? this[this.length-1] : this.slice(this.length-size)
}
Array.prototype.min = function(){
    return this.sort().first()
}
Array.prototype.max = function(){
    return this.sort().last()
}
a = [3,5,4,2,1];
min = a.min(); // 1
max = a.max(); // 5

なんか、最初より長くなってるけどArray.prototypeは別のファイルに書いておけば後は使い回しが利くので、コードの記述量はどんどん減るようになる、というわけ。

あとはruby.jsのソースなんかを読むと良い。メソッドチェーンを使うことで殆どの機能は、より簡潔に書くことができる。
http://www.advogato.org/proj/Ruby.js/

番外編

中身を数値に限定するならばこう書ける。実はこれが一番高速だったりする。

Array.prototype.min = function(){
    return Math.min.apply(null,this)
}
Array.prototype.max = function(){
    return Math.max.apply(null,this)
}

ただこれは、配列が空だとInfinityを返してしまうとか、そういう問題はある。