全てがReduceになる(5)

前回に続き、Array のメソッドを reduce で再実装する。

今回は Node における Array#sort のアルゴリズムの解明で非常に長い内容になってしまった。なので sort のみです。

  • sort

実装及びテストのリポジトリ(practice-all-becomes-reduce)

ルール

引き続き以下のルールでやっていく。

  • for 文禁止
  • Array#reduce を必ず使用する
  • Array のインスタンスメソッドは reduce 以外使用不可
  • Array のプロパティ、クラスメソッドは使用可能
  • スプレッド構文は使用不可（reduce すら不要になる場合があるから）

sort

Array.prototype.sort() - JavaScript | MDN

sort なので当然配列の並び替えを行う。ただしこの sort メソッドは非常にクセがある。（後述）

構文

arr.sort([compareFunction])

sort はソートされた配列を戻り値として返すが、レシーバとなる配列を破壊的にソートする。

compareFunction を指定した場合、その関数の結果に基づいたソートを行い、省略した場合は各要素を文字列比較した結果に基づき、辞書順次ソートする。

再実装

const concat = (...args) =>
  args.reduce((acc, array) => {
    Array.from(array).reduce((_, cur, index) => {
      if (index in array) {
        acc[acc.length] = array[index]
      } else {
        acc.length += 1
      }
    }, null)
    return acc
  }, [])

const push = (from, to, index) => {
  if (index in from) {
    to[to.length] = from[index]
  } else {
    to.length += 1
  }
}

const quickSort = (array, compare) => {
  if (array.length < 1) return array
  // 後でconcatする為配列で保持
  const pivot = 0 in array ? [array[0]] : [,]
  const [left, right] = Array.from(array).reduce(
    (acc, cur, index) => {
      if (index !== 0) {
        // プロパティ有 & compareが0以下ならright
        const idx =
          0 in pivot && compare.call(undefined, pivot[0], array[index]) <= 0
        push(array, acc[Number(idx)], index)
      }
      return acc
    },
    [[], []] // [[left], [right]] を返す
  )
  return concat(quickSort(left, compare), pivot, quickSort(right, compare))
}

Array.prototype.sort = function(compare) {
  const sorted = quickSort(this, (x, y) => {
    if (x === undefined || y === undefined) {
      return (x === undefined ? 1 : 0) + (y === undefined ? -1 : 0)
    }
    if (compare) {
      const v = Number(compare.call(undefined, x, y))
      return Number.isNaN(v) ? 0 : v
    }
    return (String(x) > String(y) ? 1 : 0) + (String(x) < String(y) ? -1 : 0)
  })

  this.length = 0

  return Array.from(sorted).reduce((acc, cur, index) => {
    push(sorted, acc, index)
    return acc
  }, this)
}

まずいきなりだが、配列をソートする。

const sorted = quickSort(this, (x, y) => {
  if (x === undefined || y === undefined) {
    return (x === undefined ? 1 : 0) + (y === undefined ? -1 : 0)
  }
  if (compare) {
    const v = Number(compare.call(undefined, x, y))
    return Number.isNaN(v) ? 0 : v
  }
  return (String(x) > String(y) ? 1 : 0) + (String(x) < String(y) ? -1 : 0)
})

ソートにはクイックソートを使う。
quickSort 関数は名前の通りクイックソートを行う関数で、第一引数にソート対象の配列、第二引数には callback を渡す。この時 quickSort に渡す callback は比較関数である compareFunction を渡すのだが、 sort メソッドの引数である compareFunction をそのまま渡すのではなく、 undefined の場合や compareFunction が未定義の場合の比較処理を追加した関数でラップしている。（仕様にある”文字列で比較し辞書順にソート”の部分である）

これは ECMAScript 仕様書のRuntime Semantics: SortCompare(x,y)にある手順をそのまま実装している。

クイックソート部分はクイックソート : アルゴリズムを参考にさせて頂いて、以下のようになっている。

const quickSort = (array, compare) => {
  if (array.length < 1) return array
  // 後でconcatする為配列で保持
  const pivot = 0 in array ? [array[0]] : [,]
  const [left, right] = Array.from(array).reduce(
    (acc, cur, index) => {
      if (index !== 0) {
        // プロパティ有 & compareが0以下ならright
        const idx =
          0 in pivot && compare.call(undefined, pivot[0], array[index]) <= 0
        push(array, acc[Number(idx)], index)
      }
      return acc
    },
    [[], []] // [[left], [right]] を返す
  )
  return concat(quickSort(left, compare), pivot, quickSort(right, compare))
}

配列の先頭要素を pivot として取り出し、他の要素と compare 関数で比較し、left と right に割り振っていく。その後 left と right 配列は再帰的にクイックソートを繰り返し、最終的に left+pivot+right で配列を結合する形になる。

concat は単純に配列を結合する関数、push は配列に要素を追加する関数だ。concat は配列同士しか結合できないようになっているので、pivot は配列で保持している。

また、疎な配列であってもソートできるようにしていて、pivot がプロパティの無い要素（疎要素）ならば、他の要素は無条件で left（先頭側）にソートするようになっている。これによりプロパティの無い要素（疎要素）は compare の結果にかかわらず全て配列の末尾側にまとめられる。

この仕様もRuntime Semantics: SortCompare(x,y)の NOTE1 に記載がある。

Because non-existent property values always compare greater than undefined property values, and undefined always compares greater than any other value, undefined property values always sort to the end of the result, followed by non-existent property values.

ネイティブの sort と結果が異なる問題

大問題なわけで、僕のソート実装が間違ってるに等しいわけで

具体的には以下の配列をに比較関数有りでソートした時に結果が異なる。（※以降、node組み込みのsortをネイティブ、自作のsortをリメイクと呼ぶ）

const array = [1, undefined, 'z', 2, 'a', 0, null]

比較関数無しの場合はネイティブもリメイクも同じ結果を返す。

> array = [1, undefined, 'z', 2, 'a', 0, null];
> array.sort();
[0, 1, 2, 'a', null, 'z', undefined]

しかし (x, y) => x - y という比較関数を与えると異なる結果を返してしまう。

// ネイティブ
> array = [1, undefined, 'z', 2, 'a', 0, null];
> array.sort((x, y) => x - y);
[null, 1, 'z', 2, 'a', 0, undefined]

// リメイク
> array = [1, undefined, 'z', 2, 'a', 0, null];
> array.sort((x, y) => x - y);
[0, null, 1, 'z', 2, 'a', undefined]

上記の通り、0 の位置が異なる。

Node.js(v8) のソースを見てみる。

v8/array.js at master · v8/v8

Node.js は v8 を使用しているので、sort のコードを確認してみる。（場所は上記の箇所で良いハズ…）

いきなり大事なことが書いてある。ソートアルゴリズムはクイックソートを使用しているが、配列長が 10 以下の場合は挿入ソートを使用しているらしい。

// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.

その挿入ソートに対応するコードは以下のものだ

function InsertionSort(a, from, to) {
  for (var i = from + 1; i < to; i++) {
    var element = a[i]
    for (var j = i - 1; j >= from; j--) {
      var tmp = a[j]
      var order = comparefn(tmp, element)
      if (order > 0) {
        a[j + 1] = tmp
      } else {
        break
      }
    }
    a[j + 1] = element
  }
}

このコード使って疑似的なネイティブのソートを再現し、どのような結果を返すか確認してみる。

const compare = (x, y) => x - y

function comparefn(x, y) {
  if (x === undefined || y === undefined) {
    return (x === undefined ? 1 : 0) + (y === undefined ? -1 : 0)
  }
  if (compare) {
    const v = Number(compare.call(undefined, x, y))
    return Number.isNaN(v) ? 0 : v
  }
  return (String(x) > String(y) ? 1 : 0) + (String(x) < String(y) ? -1 : 0)
}

function InsertionSort(a, from, to) {
  for (var i = from + 1; i < to; i++) {
    var element = a[i]
    for (var j = i - 1; j >= from; j--) {
      var tmp = a[j]
      var order = comparefn(tmp, element)
      if (order > 0) {
        a[j + 1] = tmp
      } else {
        break
      }
    }
    a[j + 1] = element
  }
}

array = [1, undefined, 'z', 2, 'a', 0, null]
InsertionSort(array, 0, array.length)
console.log(array)

結果、ネイティブと違うソート結果になってしまった。。。

// 元配列
> [1, undefined, 'z', 2, 'a', 0, null]

// ネイティブ
> [null, 1, 'z', 2, 'a', 0, undefined]
// リメイク
> [0, null, 1, 'z', 2, 'a', undefined]
// 疑似ネイティブ
> [1, 'z', 2, 'a', 0, null, undefined]

// 全部ちがう。。。

更に詳細な動作を確認するため、InsertionSort の a[j + 1] = element 箇所で console.log を仕込み、配列の途中経過を出力するようにしてみた。

[ 1, undefined, 'z', 2, 'a', 0, null ]
[ 1, 'z', undefined, 2, 'a', 0, null ]
[ 1, 'z', 2, undefined, 'a', 0, null ]
[ 1, 'z', 2, 'a', undefined, 0, null ]
[ 1, 'z', 2, 'a', 0, undefined, null ]
[ 1, 'z', 2, 'a', 0, null, undefined ]
[ 1, 'z', 2, 'a', 0, null, undefined ]

すると undefined がただ後ろに移動していくだけの動きをしていることが分かった。

しかし挿入ソートのアルゴリズムを改めて確認すると、1, z, 2, a, 0 の並びは 数値と文字を比較すると結果が全て 0 になるため、隣同士の比較だと動くことができなくて、さらに 0 と null の比較も結果は 0 になる（null は計算上 0 扱いの為）ので、0 と null の比較も動かない。結局 undefined だけが 0 以外の結果を返し、移動していく形になっている。つまり動作としては何ら問題がないことになる。

ネイティブのようにnullを先頭にやらないといけないのだが、これどうやっても null は先頭にいかないよな…？

改めて v8 のコードを読む

改めて v8 のコードを読んでいると、大事なコメントを見逃していた。

We also move all non-undefined elements to the front of the array and move the undefineds after that. Holes are removed.

（意訳）non-undefined な要素を配列の先頭に移動し、その後ろに undefined な要素を移動する。そうすると穴が消える

この処理は %PrepareElementsForSort(array, length); というC++の関数で行われているようだ。ここから処理を辿っていき、動作を詳しく見てみる。

すると配列の操作をしていると思われる場所が…あった

    unsigned int undefs = limit;
    unsigned int holes = limit;
    // Assume most arrays contain no holes and undefined values, so minimize the
    // number of stores of non-undefined, non-the-hole values.
    for (unsigned int i = 0; i < undefs; i++) {
      Object* current = elements->get(i);
      if (current->IsTheHole(isolate)) {
        holes--;
        undefs--;
      } else if (current->IsUndefined(isolate)) {
        undefs--;
      } else {
        continue;
      }
      // Position i needs to be filled.
      while (undefs > i) {
        current = elements->get(undefs);
        if (current->IsTheHole(isolate)) {
          holes--;
          undefs--;
        } else if (current->IsUndefined(isolate)) {
          undefs--;
        } else {
          elements->set(i, current, write_barrier);
          break;
        }
      }
}

前述のコメント通り、undefined と hole(疎要素)を配列の後方へ移動させる処理だ。その内容はざっくりと言うと、配列中に undefined か hole(疎要素)が見つかったら、最後尾の要素とスワップするというものだ。

なので %PrepareElementsForSort(array, length); が実行された結果、array は以下の並びになっている（はずだ）。

;[1, null, 'z', 2, 'a', 0, undefined]

改めてこの配列で擬似ネイティブのソートを実行すると、こんどはネイティブの結果と同等になった。

array = [1, null, 'z', 2, 'a', 0, undefined]
InsertionSort(array, 0, array.length)
console.log(array)
// > [null, 1, 'z', 2, 'a', 0, undefined ]

つまりリメイクの sort メソッドは以下の点を改良するとネイティブと同じ結果を返すようになる。

  • undefined と hole（疎要素）の移動はソート処理前に行い、最後尾の要素とのスワップで行う。
  • 配列長が 10 以下の場合、クイックソートではなく挿入ソートで実行する。

で、直すの？

じつはリメイクのコードでも undefined と hole（疎要素）の移動は実現できている。ただ移動のアルゴリズムでスワップを行っていないだけだ。そしてこの移動アルゴリズムとソートアルゴリズムは ECMAScript の仕様書では規定されておらず、実装依存となっている。

今回リメイクとネイティブの差異が何処にあるかという点で深堀りしてみたが、リメイクのコードは現状でも仕様を満たしているので、修正はせずにこれで完成としたい。（というかこの調査でもう疲れきった…）

Array のメソッドはまだ少しあるので、そちらに力を割くことにしよう…

つづく

（余談）ブラウザで実行してみたら…

JSFiddle で以下のコードを実行してみたところ、Firefox のみ違うソート結果となってしまった。node と Chrome は同じ v8 を使っているから同じ結果なのだろうか。Array#sort が頻繁に実装依存と言われているのはこういうことなんだな。

node

array = [1, undefined, 'z', 2, 'a', 0, null]
array.sort((x, y) => x - y)
console.log(array)

// > [ null, 1, 'z', 2, 'a', 0, undefined ]

firefox

array = [1, undefined, 'z', 2, 'a', 0, null]
array.sort((x, y) => x - y)
console.log(array)

// > [0, null, 'a', 'z', 1, 2, undefined]

Chrome

array = [1, undefined, 'z', 2, 'a', 0, null]
array.sort((x, y) => x - y)
console.log(array)
// > [null, 1, "z", 2, "a", 0, undefined]

参考