ここでは、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