開発備忘録：JavaScriptの速度最適化の経験

JavaScriptで次のようなコードを速度で最適化する必要があった。

// 関数correct_originの最初の候補。この関数を速度で最適化しないといけない。
function correct_origin(origin_x, period_x, left, width) {
    while (origin_x < left)
        origin_x += period_x;
    while (origin_x >= left + width)
        origin_x -= period_x;
    return origin_x;
}

そこで次のようなジョブをマーケットに投げた：

// JavaScriptと数学のできる人が対象です。
//
// JavaScriptで次の性質を満たすcorrect_origin関数を考案しなさい。
// ret = correct_origin(origin_x, period_x, left, width);
//
// - 引数origin_xは実数。
// - 引数period_xは正の実数。
// - 引数leftは実数。
// - 引数widthは正の実数。
// - 戻り値retは次に述べる性質を満たす：
// 「ある整数nが存在して(left - period_x < ret && ret < left + width &&
//   origin_x + n * period_x ≒ ret)である」。ただし、≒の誤差は充分に小さいものとする。

// 関数correct_originの最初の候補。この関数を速度で最適化しないといけない。
function correct_origin(origin_x, period_x, left, width) {
    while (origin_x < left)
        origin_x += period_x;
    while (origin_x >= left + width)
        origin_x -= period_x;
    return origin_x;
}

// min以上max以下の乱数を生成する関数。
function generate_random(min, max) {
  return Math.random() * (max - min) + min;
}

// テストケースを生成する関数。
function generate_testcase() {
  let large_number = 100000;
  let ret = null;
  let error = null;
  let origin_x = generate_random(large_number, 2 * large_number) * (Math.random() > 0.5 ? -1 : 1);
  let period_x = generate_random(2, 100);
  let left = generate_random(large_number, 2 * large_number) * (Math.random() > 0.5 ? -1 : 1);
  let width = generate_random(100, 200);
  return [ret, error, origin_x, period_x, left, width];
}

// 負の浮動小数点数を受け付ける剰余関数。
function mod(x, y) {
  return ((x % y) + y) % y;
}

// テストケースをテストする関数。
function do_testcase(testcase) {
  let ret = testcase[0];
  let origin_x = testcase[2];
  let period_x = testcase[3];
  let left = testcase[4];
  let width = testcase[5];
  let error = Math.abs(period_x - mod(ret - origin_x, period_x));
  if(error > period_x / 2)
    error = period_x - error;
  testcase[1] = error;
  const threshould = 0.0001;
  if (left - period_x < ret && ret < left + width && error < threshould) {
    return true;
  }
  console.log(testcase);
  return false;
}

// 関数correct_originに対するテストを行い、結果を出力する関数。
function test_correct_origin(correct_origin) {
  let testcases = [];
  let testcases_count = 100000;
  for(let i = 0; i < testcases_count; ++i) {
    testcases.push(generate_testcase());
  }

  console.log("計算中...");
  let time0 = new Date().getTime();
  for(let testcase of testcases) {
    let ret = correct_origin(testcase[2], testcase[3], testcase[4], testcase[5]);
    testcase[0] = ret;
  }
  let time1 = new Date().getTime();
  let diff_time = time1 - time0;
  console.log("計算完了。");

  let passed = true; // 合格したか？
  let error = 0; // 誤差。
  for(let testcase of testcases) {
    if(passed)
      passed = do_testcase(testcase);
    else
      do_testcase(testcase);
    error += Math.abs(testcase[1]);
  }

  console.log(`passed: ${passed}, diff_time: ${diff_time}, error: ${error}`);
}

// 実際にテストする。
test_correct_origin(correct_origin);

すると次のような答えが得られた：

function correct_origin(origin_x, period_x, left, width) {
  if (origin_x <= left) {
    const n = Math.ceil((left - origin_x) / period_x)
    origin_x += n * period_x
  }
  if (origin_x >= left + width) {
    const n = Math.ceil((origin_x - (left + width)) / period_x)
    origin_x -= n * period_x
  }
  return origin_x;
}

この答えは確かに速く、精度も高い。これを採用することとした。

補記

テストに境界チェックを付けた方が良かったようだ。

最適化に人工知能を使ってみた。Bing Chatでは次の結果を得た。これは役に立たない。

ChatGPTでは次の結果を得た：

これも充分速い。

補記

コメント