gotin blog

Whatever gotin wanna write

シュワルツ変換

Schwartzian transform - Wikipedia, the free encyclopedia

sort処理時にsort関数に比較関数を渡すような場合に、比較関数内で計算量がかかるような処理をしている場合、それはsort前に全要素に対して先にやっておいたほうがいいよね、それで比較関数内ではその重い処理はやらずに、先にやっておいた処理結果を利用するようにしたらいいよ、だってsort処理時に同じ要素に対して何度もその重い処理を繰り返す可能性があるからさ、ってことだと理解した。実際には「その重い処理」というのは軽い処理だとしても先出ししておいたほうがsort処理全体の計算量としては小さくすむのだと思われる。

ふむ。じゃぁその重い処理を先にやっておいて、sort処理後にその後始末もやるよ、っていうその二つの処理も追加で引数としてとるsort関数があったら便利だろうか。いやぁ便利じゃないな、多分。

Firebugで試したコード:(対象は整数の配列で、比較関数は平方根を比較するものとした)

function time(){
  var func = Array.prototype.shift.call(arguments);
  var args = arguments;
  var start = new Date().getTime();
  var ret = func.apply(null, args);
  var time = new Date().getTime() - start;
  return {result:ret, time:time};
}

function simpleSort(array){
  return array.sort(function(a,b){
    return Math.sqrt(a)- Math.sqrt(b);
  });
}

function schwartzSort(array){
  var tmp = array.map(function(element){
    return {value:element,sqrt:Math.sqrt(element)};
  });
  tmp =tmp.sort(function(a,b){return a.sqrt-b.sqrt;});
  var result = tmp.map(function(element){
    return element.value;
  });
  return result;
}

function makeRandomArray(size){
  var array = [];
  for(var i=0;i<10000;i++){
    array.push(Math.floor(Math.random()*10));
  }
  return array;
}

var x = makeRandomArray(8000);
var simpleSortResult = time(simpleSort, x);
var schwartzSortResult = time(schwartzSort, x);

// compare results
console.log(simpleSortResult.result.join() == schwartzSortResult.result.join());
// show time
console.log(simpleSortResult.time);   // 2112 :my environment
console.log(schwartzSortResult.time); // 1332 :my environment

サイズが大きくなるほど差が出てくるんだけど、あんまり大きいと「継続するかい?ダイアログ」が出てきちゃうのでとりあえず8000件で試しました(正確には、自分の環境でダイアログが出ず、かつそれなりに大きなサイズ、になるように調整した結果)。

でもこういう工夫をせずとももうちょっとましな手法というか、sort処理用インターフェース?がありそうな気がする。気がするだけかな。