テーブルを一旦配列にしてからソート

この前の続き。自己引用。

opera:cache のキャッシュ一覧で、tr 要素が1万あるテーブルをソートしようと思ってるんだけど、直感的にやりすぎて遅かった。

originalTable という変数にこんな感じの DocumentFragment を入れて、

opr000E8	2859	http://hoge.com/hoge.jpg
opr000EH	56	http://fuga.com/fuga.js
opr000CS	4698145	http://piyo.com/piyo.flv

こんなふうに並べ変えた DocumentFragment を作ると。

opr000EH	56	http://fuga.com/fuga.js
opr000E8	2859	http://hoge.com/hoge.jpg
opr000CS	4698145	http://piyo.com/piyo.flv

テーブルのソートって何が一番良いんだろう - by edvakf in hatena

この前はバケットソートでやっていたのだが、それだとソートが10秒以上かかってしまう。

調べたところ、バケットソートだと、上の表のように比べる対象が 56,2859,4698145 と大きく離れている場合に遅いらしい。

なんてったって一番大きなフィアルサイズが 22102973 もあるのだから。

javascript:var t0=new Date().getTime();for(var i=0;i<22102973;i++);var t1=new Date().getTime();alert(t1-t0);

これだけでなんと8秒以上もかかる。

そういうわけで、テーブルを一旦配列に格納してから、普通の sort 関数でソートすることにした。

例のごとく↓は opera:cache でブックマークレットとして実行できる。でもやっても何も変化がないのでおもしろくないと思う。

javascript: (function() {
  var tbody = document.getElementsByTagName('tbody')[0];
  function copyOriginalTable() {
    var df = document.createDocumentFragment();
    var range = document.createRange();
    range.selectNodeContents(tbody);
    range.setStartAfter(range.startContainer.firstChild);
    df = range.cloneContents();
    return df;
  }
  function makeTableArray(table) {
    var rows = document.evaluate('//tr', table, null, 5, null);
    var cells = document.evaluate('//td', table, null, 5, null);
    var arr = [];
    var tr = rows.iterateNext();
    while (tr) {
      arr[arr.length] = {
        'filename': cells.iterateNext().innerText,
        'size': cells.iterateNext().innerText - 0,
        'address': cells.iterateNext().innerText,
        'tr': tr
      };
      tr = rows.iterateNext();
    }
    return arr;
  }
  function table2DocumentFragment(table) {
    var df = document.createDocumentFragment();
    for (var i = 0,
    n = table.length; i < n; i++) {
      df.appendChild(table[i].tr.cloneNode(true));
    }
    return df;
  }

  opera.postError('************\nStart\n***********');
  var t0 = new Date().getTime();
  var originalTable = copyOriginalTable();
  var tableArray = makeTableArray(originalTable);
  var t1 = new Date().getTime();
  opera.postError(t1 - t0);

  var sizeAscendantArray = tableArray.sort(function(a, b) {
    return a.size - b.size;
  });
  var sizeAscendantTable = table2DocumentFragment(sizeAscendantArray);
  var t2 = new Date().getTime();
  opera.postError(t2 - t1);

  var filenameAscendantArray = tableArray.sort(function(a, b) {
    var af = a.filename,
    bf = b.filename;
    if (af > bf) return 1;
    else if (af < bf) return - 1;
    else return 0;
  });
  var filenameAscendantTable = table2DocumentFragment(filenameAscendantArray);
  var t3 = new Date().getTime();
  opera.postError(t3 - t2);
})();

基数ソートというやつも試したのだが、自分の実装に問題があるのか、面倒な割にあまり速くならなかった。

時間を無駄にした気分。

一応それもメモとして保存。恥ずかしいから見ないでください。

function radixSort(array, key, order) {
  Array.prototype.clone = function() {
    var clone = [];
    for (var i = 0,
    n = this.length; i < n; i++) {
      clone[i] = this[i];
    }
    return clone;
  };
  Array.prototype.compactflatten = function(o) {
    var flat = [];
    var n = this.length;
    switch (o) {
    case 'ascendant':
      for (var i = 0; i < n; i++) {
        if (this[i] && this[i] != undefined) flat = flat.concat(this[i]);
      }
      break;
    case 'descendant':
      for (var i = n; i >= 0; i--) {
        if (this[i] && this[i] != undefined) flat = flat.concat(this[i]);
      }
      break;
    }
    return flat;
  };

  var getRadixValue;
  if (key == 'size') getRadixValue = function(item, key) {
    var value = item[key] % 10;
    item[key] = (item[key] - value) / 10;
    return value;
  };
  else if (key == 'filename') getRadixValue = function(item, key) {
    var value = parseInt(item[key].slice( - 1), 36);
    item[key] = item[key].slice(0, -1);
    return value;
  };

  var myarr = array.clone();
  while (true) {
    var buckets = [];
    for (var i = 0,
    n = myarr.length; i < n; i++) {
      var item = myarr[i];
      var value = getRadixValue(item, key);
      var b = buckets[value];
      if (b == undefined) {
        buckets[value] = [item];
      } else {
        buckets[value][b.length] = item;
      }
    }
    if (buckets.length == 1) break;
    myarr = buckets.compactflatten(order);
  }
  return myarr;
}