2007年12月03日 04:00 [Edit]

アルゴリズム百選 - 配列を再発明する

アルゴリズムを理解するのに最適な方法は、すでに当たり前のように使われている仕組みを、もう一度時分の手で作ってみることです。ここでは、配列に関するアルゴリズムを再実装してみます。


ここでは、MyArrayというオブジェクトを作って、それに配列としての機能を持たせることにします。まずは基本的な操作ができるようにしておきます。

残念ながらRubyなどと異なり、JavaScriptでは[]を演算子として再定義することは出来ないので、ここではget()メソッドとset()メソッドをその代わりとして用意することにします。また、利便性を考えて、組み込みのArrayに変換するtoArray()メソッドも用意しておくことにしましょう。

function MyArray(){
  this.size = arguments.length;
  this.data   = {}; // [] でない点に注意!
  for (var i = 0, l = this.size; i < l; i++){
    this.data[i] = arguments[i];
  }
}

MyArray.prototype.set = function(index, value){
  if (index < 0) index += this.size;             // 添字がマイナスの場合
  if (index >= this.size) this.size = index + 1; // 必要に応じてサイズ変更
  this.data[index] = value;
  return this;
}

MyArray.prototype.get = function(index){
  if (index < 0) index += this.size;
  return this.data[index];
}

MyArray.prototype.toArray = function(){
  if (! this.size) return [];
  var result = [];
  for (var i = 0, l = this.size; i < l; i++){
    result[i] = this.get(i);
  }
  return result;
}

以上のような感じになるでしょうか。それでは以下、このMyArrayが期待どおりに動くかをチェックしてみることにしましょう。

プログラム:
出力:
エラー:

どうやら期待どおりに動いているようです。ただし、これだけでは、単に「数字を入れると、それに対応したデータが出てくる」オブジェクトでしかありません。配列として使うには、もう少しメソッドが必要になるでしょう。これらを実装していくことで、配列に関するアルゴリズムの特性をつかむこともできるようになります。

配列をスタックとして使う - popとpush

配列の利用法として最も使われているものの一つがスタック(stack)です。スタックとは何かというと、一番最初に入れたものが一番最後に出てくるLIFO(Last in, first out)というデータ構造です。スタックにデータを入れることをpush、データを取り出すことをpopといいます。JavaScriptのArrayでも、これらはそのままの名前で呼ばれています。

MyArray.prototype.push = function(value){
  this.set(this.size, value);
  return this;
}

MyArray.prototype.pop  = function(){
  if (!this.size) return;            // 空なら空のreturn
  var value = this.get(this.size-1); // 最後の要素
  this.size--;                       // 要素数を一つ減らす
  return value;
}
プログラム:
出力:
エラー:

見てのとおり、pushもpopも配列の大きさに関わらず手順数は一定、すなわちO(1)です。

配列をキューとして使う - shiftとunshift

スタックと同じぐらいよく使われているのが、キュー(queue)という仕組みです。こちらはスタックのLIFOとは逆に、一番最初に入れたものが一番最初に出てくるFIFO(first in, first out)です。

配列をキューとして使う場合、データを追加するのは先ほど紹介したpushのままですが、データを取り出す法はshiftといいます。そしてデータを配列の末尾ではなく先頭に追加する方はunshiftといいます。これらを実装してみましょう。

MyArray.prototype.shift  = function(){
  if (!this.size) return;
  var value = this.get(0);
  // 後でデータを一つ前に引っ越す
  for (var i = 0, l = this.size - 1; i < l; i++){
    this.set(i, this.get(i+1));
  }
  this.size--;
  return value;
}

MyArray.prototype.unshift = function(value){
  // 先にデータを一つ先に引っ越す
  for (var i = this.size - 1; i >= 0; i--){
    this.set(i+1, this.get(i));
  }
  this.set(0, value);
  return this;
}
プログラム:
出力:
エラー:

今度はpushとpopの場合と異なり、データを引っ越すという作業が必要になります。この引っ越し作業の手間は、配列の要素数に比例します。すなわちO(n)です。

これはキューの実装手段としては必ずしも最適ではありません。が、配列の利用そのものが手軽なので、実地では結構そのまま使われていたりします。ただし、最適ではないので、効率が問題となる場面では、キューの実装はO(1)アルゴリズムであるリスト(後述予定)ないしリングバッファー(後述予定)が用いられます。

配列操作の一般化 - splice

JavaScriptに限らず、perl、ruby、pythonなど配列を組み込みで持つ言語のほとんどには、spliceという関数/メソッドが用意されています。これは何をするものかというと、「配列の一部を抜き出し、場合によってはそこにさらに要素を押し込む」という操作を一度に行うものです。英語でspliceというのは「切り貼りする」という意味ですが、配列を切り貼りするのがspliceです。

これを使うと、配列を変更する操作を全てspliceで言い換えることが出来ます。

array.push(x);    // array.splice(array.length, 0, x);
array.pop();      // (array.splice(-1, 1))[0];
array.shift();    // (array.splice(0, 1))[0];
array.unshift(x)  // array.splice(0,0,x);
array[i] = x      // array.splice(i,1,x);

なんだか大変そうですが、がんばって実装してみましょう。

MyArray.prototype.splice = function(where, len){ 
  if (where < 0) where = this.size + where; // 位置が負数の場合
  var result = new MyArray; // 結果もMyArrayで
  // まずはwhereからlen個の要素をコピー
  for (var i = 0; i < len; i++){
    result.set(i, this.get(where + i));
  }
  // len個だけ前につめる
  for (var i = where+len, l = this.size; i < l; i++){
    this.set(i-len, this.get(i));
  }
  this.size -= len;
  // 追加要素がある場合
  if (arguments.length > 2){
     var stretch = arguments.length - 2;
     // 隙間を開ける
     for (var i = this.size - 1; i >= where; i--){
       this.set(i + stretch, this.get(i));
     }
     // 隙間に追加要素をコピー
     for (var i = 0, l = stretch; i < l; i++){
       this.set(where + i, arguments[i+2]);
     }
  }
  return result;
}
プログラム:
出力:
エラー:

JavaScriptのArrayには、その他にもreverse、concatなど多くのメソッドが存在しますが、これらの再発明は読者の課題とします。ただし、sortは後ほど登場する予定です。

Dan the Algorithmic Blogger


この記事へのトラックバックURL

この記事へのトラックバック
(実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。
アルゴリズム百選 - ハッシュを再発明する【404 Blog Not Found】at 2007年12月03日 11:25
この記事へのコメント
ECMA-262さん、
さすがにそこまでPedanticにやるのも何なので。
あと、ma.length は rather confusing なので ma.size としました。
Dan the Reviewed
Posted by at 2007年12月03日 15:40
忘れがちですが、JavaScript(ECMAScript)組み込みのArrayは
コンストラクタを引数1つだけで呼び出した場合、
それを this.length としますよ。
Posted by ECMA-262 at 2007年12月03日 14:57
ココサブさん、
さいです。ついでなので

if (index < 0) index += this.length;

としました。
Dan the Debugged
Posted by at 2007年12月03日 14:11
if (index < 0) index = this.length - index; // 添字がマイナスの場合



if (index < 0) index = this.length + index; // 添字がマイナスの場合

じゃないでしょうか。
Posted by ココサブ at 2007年12月03日 14:03
×)もう一度時分の手で
○)もう一度自分の手で
と思われます。
Posted by typo watcher at 2007年12月03日 10:22
_さん、
その通りです。"foo"+0は"foo0"ですから....
と言おうとして、念のために-=0をやっても0でなくて"NaN"、*=1でも"Nan"
なので、強制数値化はヤメにしました。
Dan the JavaScripting Perl Monger
Posted by at 2007年12月03日 05:19
数値化なら+=0ではなく-=0ですね
Posted by _ at 2007年12月03日 05:01