push swapとは何だったのか

プロローグ

小耳に挟んだ馴染みのない◯◯ソートを実装したら簡単に通ってしまった。
なんとなくで通ってしまった、あの課題。
あれは一体何だったのか。

（※ネタバレ（解法）を含むので一度自力で何も見ずにアルゴリズムを考えてから読むことをお勧めします。）

問題提起

• 提出したソートアルゴリズムを学ぶ過程で得た知識は業務で活かせるだろうか
• そのソートアルゴリズムが適する場面、適さない場面を見極めることはできるだろうか
• （もっと問題意識を広げて、）課題によって任意の適したソートアルゴリズムを見極める力はついただろうか

奇抜な問題設定について

• 応用問題をその問題単体とみなして解いても応用力は養われない
• 現実の応用問題はさらに多様でそれぞれ異なる
  • よって応用問題ごとに対処しても意味は薄い
• 一見変則的な問題が与えられたとして、必ずしも奇抜な応用力を発揮して解く必要があるとは限らない
• 基礎知識からの応用という位置付けで問題を捉えられるかが大事

ソフトウェアエンジニアリングとは、ある規則を未知の事例に応用する知的技能である。
ここも参照

ソートは簡単。簡単？

「ソートなんて簡単」
「ググればすぐ出てくる話」
「世の中アルゴリズムなんていくらでもあるので他のアルゴリズムではなくソートを特別視する意味はない」
そんな声が聞こえてきそう。

世界ランキング1位のMIT（マサチューセッツ工科大学）の標準教科書と言われるアルゴリズムイントロダクションにはこう書かれている。

ソートの目的
アルゴリズムを学ぶときに最も基本的な問題はソートであると、多数の計算機科学者は考えている。それにはいくつか理由がある。
・情報をソートすることが本質的に必要な多くの応用事例が存在する。...（略）...
・ソートを重要なサブルーチンとして用いるアルゴリズムが多い。...（略）...
・...（略）...ソーティングアルゴリズムは長年にわたって研究が続けられてきたが、そこから多数の重要なアルゴリズム設計技法が派生してきた。このようにソートは歴史的に興味深い問題でもある。

ソートをきちんと学ぶのには十分な理由がありそうだ。

ソートの分類

「分けることは、分かることへの第一歩」
by 数学ガール

基本情報技術者試験の参考書を見るとこのような分類表¹が記載されている。

• 交換法
  • 基本法
    • バブルソート
  • 改良法
    • クイックソートetc
• 選択法
  • 基本法
    • 選択ソート
  • 改良法
    • ヒープソートetc
• 挿入法
  • 基本法
    • 挿入ソート
  • 改良法
    • シェルソートetc
      　
• ソートの基本形は、「交換法」「選択法」「挿入法」の３つしかない
• この世に存在する数十以上ものソートアルゴリズムがほとんど全てこの３つに集約される
• であればどんな奇抜な設定のソート問題であれ、基本の３つをベースに考えていけば解けるのではないか

ここまで調べた段階（１ヶ月）でpush swapの見通しがよくなった。
もちろん、ソートアルゴリズムの区分けの視点として、安定の有無や外部メモリの有無、比較・非比較ソート、オンラインクエリなどたくさんあるが、ソートの本質はその操作方法にあり、そしてその操作方法は大きく３つに大別されることを理解するのが大事だというのが筆者の個人的な考えだ。

大胆に比較ソートを分ける

３つの基本法について「動き」に注目して分けてみる。

• 交換法
  • 未ソート領域で２要素を比較し、必要に応じて交換する
• 挿入法
  • 未ソート領域から一つ要素を$O(1)$で取り出しソート済み領域の適切な位置に入れる
• 選択法
  • 未ソート領域から一つ要素を適切に取り出しソート済み領域に$O(1)$で入れる

挿入法と選択法には少なからず対称性²があるとここで感じた。

選択法は選択時に計算コストがかかる。挿入法は挿入時に計算コストがかかる

基礎スキルを持って改めて応用問題を観察する（フレームワーク思考）

何かと評価の低いバブルソートに代表される交換法は最もシンプルな考え方だ。実装が一番簡単だとよく紹介されもする。よってまずは交換法でpush swapが解けないか考えてみる。
配列へのランダムアクセスは許可されていない。要素の交換操作はtopとsecondでしかできない。ソートには全ての要素に少なくとも交換操作が適用されるはずだ。これだけではうまくいかない。
データへの可能な操作一覧から他に使えそうなものを探す。ちょうど配列のrotate操作がある。これを使えば全要素に対して交換操作を適用できそうだ。

//　解法１　交換法
while(!is_array_sorted)
    if (need_swap)
        swap_top_second();
    rotate();

外部メモリも使う必要なく、２つの操作のみで解くことができた。

”終わりに”

• 交換法の基本法であるバブルソートをもとにしたこのアルゴリズムの計算ステップ数は少しだけ遅い
  • １００要素のソートで１万ステップぐらい
• しかし、一度問題自体から離れ、ソートの基本を抑えたことで改良の道筋が見えるようになった
  • ステップ数の良し悪しではなく、思考プロセスの道筋の良し悪しが重要に感じる
• ここで終わったほうがより主旨を伝えやすいので”終わりに”が唐突に設置されている
  • 実際は記事をn分割した名残り
• 残りの二つの基本法である選択法と挿入法を用いるとどうなるのだろう

---

続き

前回までは３つの基本法のうち１つから思考を繋げていったが、今回は残りの２つから問題にアプローチしてみる。

前回の復習だが、選択法と挿入法はコインの両表のような特徴がある。

選択法は選択時に計算コストがかかる。挿入法は挿入時に計算コストがかかる

そして、整理済み領域と未整理領域の２つを必要としている。
改めて問題を見返すと、２つの領域が提供されているのでこれが使えそう。
元の配列をA、予備の配列をBとする。
Aを未ソート領域、Bをソート済み領域として使うのが自然だろう。

• 対称性により、どちらの解法も同等の計算コストCがかかる

//解法2-1 選択法
while(is_A_not_empty)
    find_smallest_element();
    select_the_element();
    move_the_element_to_top_of_B();// cost C
push_back_to_a();

//解法2-2 挿入法
while(is_A_not_empty)
    select_top_element();
    find_proper_location_at_B();
    insert_to_the_location();// cost C
push_back_to_a();

挿入法、選択法をベースに計算コストについて考える

• ソートにおいて発生する計算コスト³の構成要素

  • 要素の移動
    • →移動コストと便宜上呼ぶ
  • 条件をもとにした要素の移動場所の決定or移動要素の決定
    • →決定コストと便宜上呼ぶ

• コストの種類の観点から

  • 普通のソートの問題
    • 決定コストの最適化
    • 移動コストなし
  • push swap
    • 決定コストなし
    • 移動コストの最適化

まずは通常のソート。

選択法は選択時に計算コストがかかる。挿入法は挿入時に計算コストがかかる

より具体的に

選択法は選択時に（移動要素の）決定コストがかかる。挿入法は挿入時に（挿入場所の）決定コストがかかる

といえる。長くなってきたのでかっこつけたいから数式で書いていく

\begin{align}
選択法の1要素の計算量&=\text{（移動要素の）決定コスト} + 移動コスト0 + \text{（挿入場所の）決定コスト}0\\
挿入法の1要素の計算量&=\text{（移動要素の）決定コスト}0 + 移動コスト0 + \text{（挿入場所の）決定コスト}\\
\\
\\
整理すると　    　　　　　　　　　&\\
\\
\\
選択法の1要素の計算量&=\text{（移動要素の）決定コスト}\\
挿入法の1要素の計算量&=\text{（挿入場所の）決定コスト}\\
\\\\
一方、　　　　     　　　　　　　　&\\
\\\\
\text{push_swap}の1要素の計算量&=決定コスト0 + \text{(未ソート領域での)移動コスト}function_{cost} + \text{(ソート済み領域での)移動コスト}function_{cost} + 決定コスト0\\
&=\text{(未ソート領域での)移動コスト}function_{cost} + \text{(ソート済み領域での)移動コスト}function_{cost}\\
\\\\
により要素iの配列a,bでの移動&コスト関数をそれぞれf_a(i),f_b(i)とすると　　\\
\\\\
\text{push_swap}の要素iの計算量&=\text{(未ソート領域での)移動コスト}f_a(i) + \text{(ソート済み領域での)移動コスト}f_b(i)\\
\\\\
よってAに残る全要素の中でコス&ト関数が最小になるような要素を動かすのは解法2-1,2-2に比べて効率がいいので\\
\\\\
移動するべき要素の\text{index} &= arg\min_{i∈[0,n)}\{f_a(i)+f_b(i)\}\\　　　where　　　　　　　　　\\
f_{array}(element) &= \min(idx_{element},\ length(array) - idx_{element})\\
n &= \text{number of elements in an array}
\end{align}

擬似コード（選択＋挿入法）

// 解法3 選択＋挿入法
while(is_A_not_empty)
    while(there_is_element_left_for_evaluate_cost)
        evaluate_cost_of_select();
        evaluate_cost_of_insert();
        add_2_costs_to_return_total_cost_of_move();
    move_cheapest_cost_element();//cost C'
push_back_to_a();

より効率的に

• 明らかにrr,rrrを用いればさらに効率化できる

この段階で100要素では600程度だが500要素では5500程度になる。

さらに効率的に

• 基本法の発想だけで誘導通りに素直に進んできた
• 100要素で最高得点になるが500要素では達しないのも課題の誘導に見えてくる
• 次は改良法を取り入れる。改良法だと500要素のスコアが向上し最高得点に到達するとしたらそれは何故だろう

最終結果

Test 200 cases: arg_length=100 range=(-2147483648, 2147483647)
---- Result ----
max   : 650
median: 585
min   : 526
Test 200 cases: arg_length=500 range=(-2147483648, 2147483647)
---- Result ----
max   : 4179
median: 3975
min   : 3774

• discordのランキングを見る限り、500要素だと東京キャンパス２位（2024/6時点）
  • 1位の方は混合アルゴリズムでアドホックに問題特化しているっぽい
• このスコアはスタート地点に過ぎない
• よりよいスコアを求めていいアルゴリズムができたらぜひ教えてほしい

終わりに

• ４２の題材はどれも面白い
  • 今回の課題は今までと違い様々な条件が構築された課題設定
  • この課題はよくつくられてるなと感じた
• Q. ヒューリスティックや解探索を取り入れればもっと速くなる余地がある
  • それはそう
  • 本記事の主旨ではない
  • ぜひこの記事よりもよいスコアを叩き出していって欲しい

追記予定（）

• push swap　改良法編

予告（＝ネタバレ）

決定コスト$O(1)$により、選択アルゴリズムを使うことと、クイックソート等の背景にある分割統治法が有利な問題構造になっている

1. 非比較ソート(基数ソート、カウントソート、計数ソートなど)は比較演算以外の情報の利用が許されるソートに分類され、比較ソートとは違った特徴を持つ。データが狭い整数範囲に分布していたり、重複要素が多数あるなど限局された特徴に対してソートアルゴリズムとして選択するモチベーションが出てくる。今回はそういった条件にしっくりと当てはまらない。 ↩

2. 実は交換法と挿入法や選択法の間にも数学的関係がある。これらの関係性を双対という概念で抽象化してまとめあげることができるらしい。 ↩

3. 計算コストって移動コスト、決定コスト以外にもあるのでは？比較コストは？→鋭い。比較コストがテーマになる課題もちゃんと先の方で用意しているのが４２のカリキュラム。 ↩