Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

in-place merge sort を実装してみた

こちらの論文を参考に書きました。

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D04E90C1CB92030C1B92452FB9E192A0?doi=10.1.1.22.8523&rep=rep1&type=pdf

実装

さくっと実装をまずお見せします。

const mergeSort = (arr: number[], L = 0, R = arr.length) => {
  if (R - L <= 1) {
    return;
  }
  const mid = L + Math.floor((R - L) / 2);
  mergeSort(arr, mid, R); // Qをソート

  for (let r = mid; L < r; ) {
    if (r - L === 1) {
      // Pのサイズが1のときは愚直にバブルさせる
      for (let i = L; i + 1 < R && arr[i] > arr[i + 1]; i++) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
      }
      break;
    }
    const p1Size = L + Math.floor((r - L) / 2),
      p2Size = L + Math.ceil((r - L) / 2);
    mergeSort(arr, L, p1Size); // P1 をソート
    // P2 をワーキングエリアにしてソートしていく
    for (let i = p1Size, p1 = L, p2 = p2Size, q = r; i > 0; ) {
      if (q < R && arr[q] < arr[p1]) {
        [arr[p2++], arr[q++]] = [arr[q], arr[p2]];
        continue;
      }
      [arr[p1++], arr[p2++]] = [arr[p2], arr[p1]];
      i--;
    }
    // P1 + Q が新たなQとなるので、rを更新
    r = p2Size;
  }
};

なにをやっているのか

  1. 配列を半分にわけ、左をP、右をQとする。
  2. Q をソート
  3. P をさらに半分にわけ、左をP1、右をP2とする。
  4. P1 をソート
  5. P2 を利用して P1 と Q をマージ(詳しくは後述)
  6. マージすると、[P2, P1 と Q をマージしたもの] という並びになるので、P2 を新しいP、 P1+Q を新しい Q として3から繰り返す
  7. P のサイズが1になったら愚直にバブルソートを行い終了

こんな感じで、作業スペースをつくることでうまく in-place でマージできます。

マージ処理について

マージはそこまで難しくないです。

  1. P1 と Q の先頭の要素を比較する
  2. 小さいほうと P2 の先頭の要素をスワップ(ただし、P1 と P2 のサイズが異なる場合、スワップするのはP2の最初から2番目の要素)
  3. これを [P2, P1 と Q をマージしたもの] となるまで繰り返す

こんな感じです。

論文ではさらに賢いやり方が紹介されています(スワップ操作の計算量を落とすテクなど)。ただ、in-place マージソートの実装ができればいいやと思ってあんまりちゃんと読んでないです…

lookahead lookbehind(先読み、後読み)まとめ

  • lookahead (?=pattern)
  • negative lookahead (?!pattern)
  • lookbehind (?<=pattern)
  • negative lookbehind (?<!pattern)

lookahead はこの後の文章から判断する。lookbehind はここまでの文章から判断する。以上。

(?<!Promise<)void(?!>)
(?<=Promise<)void(?=>)

1年に100回くらい「先読みとあと読みってどっちがどっちだ?どっちがどういう記法だっけ?」って悩むのでほんといい加減にしてほしい

軽量な summary/details を作りたい

detailsを閉じているときに DOM を消しておきたいので作りました(作成時間5分)

const Details: VFC<{ summary: ReactNode; detail: () => ReactNode }> = ({
  summary,
  detail,
}) => {
  const [showsDetail, setShowsDetail] = useState(false);
  return (
    <details open={showsDetail} onToggle={() => setShowsDetail((v) => !v)}>
      <summary tw="cursor-pointer select-none">{summary}</summary>
      {showsDetail && detail()}
    </details>
  );
};

<Details summary="サマリーの文言" detail={()=> <div>detail</div>}>

特に解説することもないです。

LINE のコーディングテストを Rust で解いてみた

Rust の練習としてLINEのコーディングをやってみました。以前からずっとやりたかったのですが、問題も長くて面倒でやってなかったんですよね(実際めんどうだった)…

今回解いた問題

以下解説していきます

(注: 入出力の例が一切なく、ジャッジシステムも見当たらなかったので、コードが問題の意図通り動いているか保証されていません。仕様の誤読やコーディングミスがある恐れがあります)

問題概要

問題本文はこちら

タクシーの走行記録が入力として渡されるので料金を求めよ。

  • 走行距離に応じた料金と、低速走行時間に応じた料金の合計が料金
    • 走行距離は初乗り410円、1052m以降は237mごとに80円
    • ただし、深夜時間帯は走った距離が1.25倍されて計算される
    • 低速走行とは、10km/h以下で走ることを指す。降車までの総低速時間に対して90秒ごとに80円かかる。

ざっと要約するとこんな感じです。

方針

仕様があまりに複雑なので、テスト駆動っぽく解きました。

  1. 走行距離のみ考慮して計算する(深夜時間帯、低速走行を含まないケースのテストを書く)
  2. 深夜時間帯を考慮して計算する
  3. 低速走行を考慮して計算する

だいたいこんな感じで段階を踏みながら関数をリファクタリングしていきました。

実際のコード

テストコードを抜いておよそ80行になりました。

use std::io::{self, BufRead, BufReader};

type Record = Vec<(f64, f64)>;
fn to_sec(h: u32, m: u32, s: f64) -> f64 {
    ((h * 60 + m) * 60) as f64 + s
}
fn is_midnight(s: f64) -> bool {
    // 22時になってから5時になるまで(5時を含まない)が深夜時間帯
    match s {
        t if t < to_sec(5, 0, 0.0) => true,
        t if t >= to_sec(22, 0, 0.0) => true,
        _ => false,
    }
}
// 走行距離を求める関数。深夜時間帯は実際に走った距離の1.25倍走行したと見なす
fn measure_distance(v: &Record) -> f64 {
    let mut distance = v.into_iter().fold(0.0, |sum, (_, meter)| sum + meter);
    for x in v.windows(2) {
        let (t1, ..) = x[0];
        let (t2, meter2) = x[1];
        if is_midnight(t1) && is_midnight(t2) {
            distance = distance + 0.25 * meter2;
        }
    }
    distance
}
// 低速(10km/h以下)で走った総時間を求める関数。深夜時間帯は実際の低速走行時間の1.25倍走行したと見なす。
fn sum_slow_running_time(v: &Record) -> f64 {
    let mut slow_running_time = 0.0;
    for x in v.windows(2) {
        let (t1, ..) = x[0];
        let (t2, meter2) = x[1];
        let dt = t2 - t1;
        if (meter2 / dt) * 60.0 * 60.0 > 10000.0 {
            continue;
        }

        slow_running_time += if is_midnight(t1) && is_midnight(t2) {
            dt * 1.25
        } else {
            dt
        }
    }
    slow_running_time
}
// 走行距離に応じた料金
fn calc_distance_based_fare(v: &Record) -> u32 {
    410 + ((measure_distance(v) - 1052.0) / 237.0).ceil() as u32 * 80
}
// 低速で走った時間に対する料金
fn calc_slow_fare(v: &Record) -> u32 {
    (sum_slow_running_time(v) / 90.0).floor() as u32 * 80
}
fn calc_fare(v: &Record) -> u32 {
    calc_distance_based_fare(v) + calc_slow_fare(v)
}

fn read_from_stdin() -> Record {
    let mut time_records: Record = vec![];
    let mut reader = BufReader::new(io::stdin());
    let mut s = String::new();

    while reader.read_line(&mut s).expect("Failed to read line.") > 0 {
        let v: Vec<_> = s.split_whitespace().collect();

        let meter = v[1].parse().unwrap_or(0.0);
        let time: Vec<_> = v[0].split(':').collect();

        let hour = time[0].parse().unwrap_or(0);
        let min = time[1].parse().unwrap_or(0);
        let sec = time[2].parse().unwrap_or(0.0);
        time_records.push((to_sec(hour, min, sec), meter));
        s.clear();
    }
    time_records
}
fn main() {
    let time_records = read_from_stdin();
    println!("{}", calc_fare(&time_records));
}

テストコードはこんな感じです。

#[test]
fn distance_based_fare() {
    // 通常時間帯のみ、低速賃金や深夜割増が発生しないケース
    let record = vec![(to_sec(7, 0, 0.0), 0.0), (to_sec(7, 1, 0.0), 1052.0)];
    assert_eq!(measure_distance(&record), 1052.0);
    assert_eq!(calc_distance_based_fare(&record), 410); // 1052m/min = 63.12km/h

    let record = vec![(to_sec(7, 0, 0.0), 0.0), (to_sec(7, 1, 0.0), 1053.0)];
    assert_eq!(measure_distance(&record), 1053.0);
    assert_eq!(calc_distance_based_fare(&record), 490);

    let record = vec![(to_sec(7, 0, 0.0), 0.0), (to_sec(7, 1, 0.0), 1289.0)];
    assert_eq!(measure_distance(&record), 1289.0);
    assert_eq!(calc_distance_based_fare(&record), 490);

    let record = vec![(to_sec(7, 0, 0.0), 0.0), (to_sec(7, 1, 0.0), 1290.0)];
    assert_eq!(measure_distance(&record), 1290.0);
    assert_eq!(calc_distance_based_fare(&record), 570);
}
#[test]
fn midnight_fare() {
    // 深夜割増のケース
    let record = vec![(to_sec(0, 0, 0.0), 0.0), (to_sec(0, 1, 0.0), 841.0)];
    assert_eq!(measure_distance(&record), 1051.25);
    assert_eq!(calc_distance_based_fare(&record), 410);

    let record = vec![(to_sec(0, 0, 0.0), 0.0), (to_sec(0, 1, 0.0), 842.0)];
    assert_eq!(measure_distance(&record), 1052.5);
    assert_eq!(calc_distance_based_fare(&record), 490);

    let record = vec![(to_sec(0, 0, 0.0), 0.0), (to_sec(0, 1, 0.0), 1031.0)];
    assert_eq!(measure_distance(&record), 1288.75);
    assert_eq!(calc_distance_based_fare(&record), 490);

    let record = vec![(to_sec(0, 0, 0.0), 0.0), (to_sec(0, 1, 0.0), 1031.3)];
    assert_eq!(measure_distance(&record), 1289.125);
    assert_eq!(calc_distance_based_fare(&record), 570);
}
#[test]
fn midnight_fare2() {
    // 通常時間帯 → 深夜時間帯のケース
    let record = vec![
        (to_sec(21, 59, 0.0), 0.0),
        (to_sec(22, 0, 0.0), 927.0),
        (to_sec(22, 0, 10.0), 100.0),
    ];
    assert_eq!(measure_distance(&record), 1052.0);
    assert_eq!(calc_distance_based_fare(&record), 410);

    let record = vec![
        (to_sec(21, 59, 0.0), 0.0),
        (to_sec(22, 0, 0.0), 927.1),
        (to_sec(22, 0, 10.0), 100.0),
    ];
    assert_eq!(measure_distance(&record), 1052.1);
    assert_eq!(calc_distance_based_fare(&record), 490);

    let record = vec![
        (to_sec(21, 59, 0.0), 0.0),
        (to_sec(22, 0, 0.0), 927.0),
        (to_sec(22, 0, 10.0), 100.1),
    ];
    assert_eq!(measure_distance(&record), 1052.125);
    assert_eq!(calc_distance_based_fare(&record), 490);
}
#[test]
fn slow_fare() {
    let record = vec![(to_sec(7, 0, 0.0), 0.0), (to_sec(8, 0, 0.0), 10000.1)];
    assert_eq!(sum_slow_running_time(&record), 0.0);

    let record = vec![(to_sec(7, 0, 0.0), 0.0), (to_sec(8, 0, 0.0), 10000.0)];
    assert_eq!(sum_slow_running_time(&record), 3600.0);

    let record = vec![(to_sec(0, 0, 0.0), 0.0), (to_sec(1, 0, 0.0), 10000.0)];
    assert_eq!(sum_slow_running_time(&record), 3600.0 * 1.25);
}

document.readyState と load, DOMContentLoaded のタイミングについて

結論

  • complete になると同時に load が発火する(仕様)
  • interactive になったあとかつ complete になる前に DOMContentLoaded が発火する(仕様)

厳密には complete になったあとに load が発火するという仕様です。この前後関係があるため、 readystatechange -> load イベントの順が保証されています。

load 時に何か処理を行いたいとき

const addLoadEventListener = (f) => {
  if (document.readyState === 'complete') {
    f();
  } else {
    window.addEventListener('load', f);
  }
};

こうすると、すでに load イベントが実行済みだった場合も処理が実行されます。

readyState の変わるタイミングを検証するコード

こんな感じで検証しました。

const id = setInterval(() => {
  console.log(document.readyState);
}, 1000 / 100);

console.log('immediately',document.readyState);

window.addEventListener('DOMContentLoaded', () => {
  console.log('DOMContentLoaded', document.readyState);
});

window.addEventListener('load', () => {
  console.log('load', document.readyState);
  clearInterval(id);
});
window.addEventListener('readystatechange', () => {
  console.log('readystatechange', document.readyState);
});

DOMContentLoaded と load を数秒離すために画像を埋めて計測しました。document.readyState が complete になるのと load イベントが発火するのは必ず同時でした。