Cute Algorithms!
稲葉 一浩
at #spro12

まずは準備運動です！

SLOWEST
SORT
Thanks to: @y_benjo @rng_58 @hos_lyric @oxy @xhl_kogitsune @args1234

アルゴリズムと言えば！

ソート！
BubbleSort
Insertion
Sort

Quick
Sort

Radix
Sort
Shell
Sort

Merge
Sort
Heap
Sort

ソートと言えば！
O(n log n) ! Quick
BubbleSort
Insertion
Sort

Sort

Radix
Sort
Shell
Sort

Merge
Sort
Heap
Sort

では、逆に・・・
ソートの「遅さの限界」は？

最遅ソート!?
一番たくさん大小比較を実行するソート法は？

「最も遅い」ソート法は？
• よくある答え： ボゴソート– ランダムに並替→ソートされたら終了 のループ

• 問題点： ずるい。
– 無駄に同じ比較を繰り返しているだけ。
– それがありなら幾らでも人工的に遅くできる。
「無駄」な比較はノーカウントで、一番多く大小比較をするソートアルゴリズムは？

Bubble Sort
「最悪」 O(n) : 入力がソート済みのとき

1＜ 2＜ 3＜ 4＜ 5＜ 6
速すぎる！
function bubble_sort(A) {for(i ← 0..n-2)
for(j ← 1..n-1)
if(A[j-1] > A[j])swap(A[j-1], A[j])}Insertion Sort
「最悪」 O(n)1＜ 2＜ 3＜ 4＜ 5＜ 6「平均」 は Ω(n2)

挿入時平均で真中まで動く

1 3 4 6 2 5

Quick Sort
「最悪」 Ω(n log n) 安定して遅い！
– 証明: Quick Sort は無駄比較をしない。

4 6 3 5 2 1
3 2 1 ＜ 4 6 5理論限界は？
BubbleInsertQuickMerge

理論限界

最悪nnn log nn log nn log n平均???

n2n log nn log nn2• どんなに遅くても「平均」は O(n2)– n(n-1)/2 通りしか比較するものがない• どんなに遅くても「最悪」は O(n log n)– 「最速」のO(n log n)とほぼ完全に同じ証明

最遅ソート：理論限界を達成
Quick Sort + Insertion Sort！
function slow_sort(A) {// 最悪 O(n log n)quick_sort(A[0 ... n/2])// 平均 O(n2)insertion_sort(A[0...n])}ここがCute!
• 「逆」の問題でも同じテクニックを応用– 「最速」計算量の下限と「最遅」の上限が同じように証明できる。
– 速度を求めて実用上よく使われる組み合わせ
Quick Sort + Insertion Sort
が「最遅ソート」にも使える。

最遅ソートの応用• N チームの総当たり戦を行います。
• 強弱にはだいたい順序がつくと仮定します。
「消化試合」（順位に影響しないことが確定している試合）をできるだけ減らす試合順は？
TimShellTim-○Shell×-

Comb
StoogeCombStooge

×-○-非破壊型キューFUNCTIONAL
QUEUE
出典: “Purely Functional Data Structures”, Chris Okasaki

Queue3 2 1Queue

3 2 1• push(x): キューに値 x を入れる
• pop() : キューから値を 1 個取り出す• 入れたのと同じ順番で出てくる

よくある実装
null２

class Queue<T> {class Node {Node prev;
Tvalue;１Node next;}
Node head;
Node tail;}null

Linked List で表現１null２null

Linked ListQueue
null

３

２

１null

３

２null

pop

１null

push 3

今日ご紹介する“Functional Queue”
出典: “Purely Functional Data Structures”「一度作ったデータは絶対に書き換えない」
データ構造に関するバイブル
class Queue<T> {class Node {const Tvalue;
const Node next;}
const Node head;
const Node tail;
Queue push(T v);
}

２

１null

(1) Singly Linked List を使う

３
SingleLinkなら先頭への追加は書き換え不要

２
push前の状態が残ってるので参照できる

１null

push 3class Node {Tvalue;
Node next;}

２

１null３３null(2) pop？

pop

１

２

１

２

３

null

Reverseしたリストを新しく作ってから、先頭Nodeを忘れる２

３push用

４nullnullpush 4

push 5２３push用

５４

nullpop用

３nullpop用

２nullpop用(3) もう一回 push？ リストを２つ持つ

ここまでの実装
Singly Linked List ２個で実装します

２３

null

for_pop が空の時
pop されたら
for_push を reverse

５４

null

class Queue<T> {class Node {Tvalue;Node next;}
Node for_pop;
Node for_push;}

問題点• for_pop が空の時だけ急にpopが遅い！

for_pop が空の時
pop されたら
for_push を reverse

(4) 対策：小分けにreverse

for_pop が空じゃなくても、こまめにreverse !
null

4

3null

2

1

null

1reverse!

2

null null

null

push 1, 2

push 3, 4

12nullreverse!

3

4

null

2

null

1

1

2nullreverse!

4

3

4

3

4

null

2

null

1

3

null null(5) 小分けreverseをQueueで管理！
push 3, 4

null

2

null

1

null

ListのQueue!

完成！

3

4

null

2

null

1

null

class Queue<T> {class Node { const Tvalue;
const Node next; }const Queue<Node<T>> for_pop;
const Nodefor_push; }ここがCute!
• “Bootstrapping” と呼ばれています– OS を起動するための OS– コンパイラ をコンパイルするための コンパイラ– 同じことがデータ構造/アルゴリズムでも考えられる• Queue を実装するための Queue迷路でぶーとすとらっぴんぐ

BOOTSTRAPPINGIN A MAZE
参考: http://www.kmonos.net/wlog/105.html#_2232100114

よくあるアルゴリズムの問題与えられた迷路を通り抜ける最短ルートを求めるプログラムを書きなさい

Route shortest(Maze m);ちょっと話を膨らませましょう
与えられた迷路を通り抜ける最短ルートを求めるプログラムを書きなさい
最短であることの検査ルーチンも書きなさい
Route shortest(Maze m);bool check(Maze m, Route r);
Route safe_shortest(Maze m) {Route r = shortest(m);if(!check(m,r)) throw Error;
return r;}失敗例：意味のないチェック
shortest が仮に間違っていてもshortest の結果にtrueを返してしまう
Route shortest(Maze m);bool check(Maze m, Route r) {return r.len == shortest(m).len;}– とはいえ、最短であることをチェックするには最短路を計算するしかなさそう…？

Bootstrapping!
元の迷路をそのままshortestに投げるとダメ。
「小さい」 迷路を渡すようにすれば！
Route safe_shortest(Maze m);bool check(Maze m, Route r) {// return r == safe_shortest(m);もっと“巧く”shortestを使う!!
}

最短ルート＝他の道は遠回り
これが最短ということは・・・

こういう近道がどこにもない

元のルートを通行止めにしたら元より遠くなる or
道がなくなるBootstrapping! （※詳細略）（※条件略）
bool check(Maze m, Route r) {for( p,q ← r上の場所のペア ) {m’ = mのpからqまでを全て埋め立てた迷路
if( safe_shortest(m’).len < r.len )return false;
元のルートを通行止め}
return true;}ここがCute!
• 間違ってるかもしれないルーチンを、元のルーチンの実装によらずに ※注
間違いを自分で検出するルーチンに強化！
※注： 今回の手法は、「最短じゃなくてもルートがある時は少なくとも何かルートを返す」ことを暗黙に仮定しています。

正確な実数EXACTREALS
出典: “RealLib”, Barnimir Lambov, 2007-

“誤差なし” 実数計算
http://wayback.archive.org/web/*/www.brics.dk/~barnie/RealLib/

using namespace RealLib;
int main() {Real sq3 = cos(Pi/3-Pi/2)*2;
Real x= 1;
for(int i=0; i<4; ++i) x *= sq3;
cout << setprecision(5) << x;// 9.00000

“誤差なし” 実数計算
http://wayback.archive.org/web/*/www.brics.dk/~barnie/RealLib/

cout << setprecision(50) << x;// 9.000000000000000000000000000// 0000000000000000000000000
cout << setprecision(99999) << x;// 9.000000000000000000000000000// 00000000000000000000000000000// 0000000000000.....000}

“BigDecimal”との違い
getcontext().prec = 80
x = Decimal(8)/Decimal(7)*Decimal(7)print(x)# Decimal(“7.99999....99997”)• 精度を最初に指定しなくていい• いつでも好きな精度まで正確な値が得られる
Real x = Real(8)/Real(7)*Real(7)cout << setprecision(80) << x;// 8.00000....00000

実装方法

**

*

Real sq3 = cos(Pi/3-Pi/2)*2;
Real x= 1;
for(int i=0; i<4; ++i)x *= sq3;**

19.00 でも9.00000000 でも9.00000....00000 でもなく変数に「数式」をそのまま記憶する（表示の時に必要精度まで計算）

cos

2-//π

3π2

ここがCute!
• シンプル！
• こんなのありなの？と思ってしまうくらい言われて見れば当たり前• でも効果は抜群※ 同じ効果は「無限精度で計算する処理」を「遅延評価」することでも実現できます式のまま計算：その２EXPRESSION
TREE
参考: http://www.kmonos.net/pub/files/sred_full.pdf

Tree に対する Query 言語
SELECT (x, y) WHERE
x in a AND<html>...<p>...
y in * AND<a href=“#xx”/>
x.href = y.id
<img id=“xx”/>...
AND...</p>...</html>
p > LCA(x, y)実装（概要）SELECT (x, y)
x in a ANDy in * AND
x.href = y.id
AND p > LCA(x, y)Result query(Tree t) {L = query(t.left)
R = query(t.right)
x= L.x ∪ R.x ∪t.label=“a” ? {t} : {}y= ...
xy = {(a,b) | a∈x, b∈y,...}
ans = L.ans ∪ R.ans ∪t.label=“p” ? xy : {}return {x,y,xy,ans}}
左と右の 「xっぽいもの」と「yっぽいもの」を組み合わせ、を繰り返す

問題点「最終的に無駄」
な計算をたくさんしてしまう

SELECT (x, y)
x in a AND
y in * AND
x.href = y.id
AND p > LCA(x, y)

上に p がない!

x ={大量のx っぽいもの}

y={}

大量のxy

かっこよくない解決策
query関数の構造を変えて、木の先祖ノードや、兄弟をたどる、「後で無駄にならないか？」の判定を足す
Result query(Tree t, INFO inf) {if( ... inf ... ) returninf = update_info(L)inf = update_info(R)
if(...) L = query(t.left, inf)
if(...) R = query(t.right, inf)
if(...) x=... else x=...
}かっこいい解決策
集合をいきなり値で計算するのではなく、計算式で表現。 ∪←not: {(t2, t4),(t3, t4),(t2, t5),
{t2, {t4,{}
{t1}
t3}
t5}
(t3, t5)}– 単に使われない「実は無駄」な集合は、計算する前に捨てられる– 空集合との掛け算は、あとで取り除く**

ここがCute!
• アルゴリズムを一切変えないでよい
Result query(Tree t) {L = query(t.left)
R = query(t.right)...

• データ構造だけを差し替えればよい• 簡単！

Thank you for- cast listening!
Slowest Sort

Bootstrapping
Expression Tree