クイックソート（C言語、Go言語）

クイックソートを C言語と Go言語で実装してみました。クイックソートは、配列の中からひとつ任意にサンプルを取ってきます。これを「ピボット」といいます。あとは、配列からピボットを除いたものを、その値がピボットより大きいか小さいかで二つの配列に分け、さらにその二つを再帰的にクイックソートします。最後はそれらを「小、ピボット、大」の順に連結します。これだけです。

C言語。じつは最初は自力で実装しようとしたのですが、うまい方法がどうしても思いつきませんでした。で、アルゴリズムの教科書を参照してみたのですが、配列の分割にとても巧みな方法が採用されていて、びっくりしました。下の partition() ですね。クイックソートは C でこんなに簡単に実装できるのだな。いや、まいりました。
quick_sort.c

#include <stdio.h>

int partiton(int ar[], int p, int r) {
    int x, i, j, tmp;
    
    x = ar[r];
    i = p - 1;
    for (j = p; j < r; j++) {
        if (ar[j] <= x) {
            i++;
            tmp = ar[i]; ar[i] = ar[j]; ar[j] = tmp;
        }
    }
    ar[r] = ar[i + 1];
    ar[i + 1] = x;
    
    return i + 1;
}

void quick_sort(int ar[], int p, int r) {
    if (p < r) {
        int q = partiton(ar, p, r);
        quick_sort(ar, p, q - 1);
        quick_sort(ar, q + 1, r);
    }
}

int main() {
    int ar[] = {3, 1, 5, 2, 9, 7, 0};
    int len = sizeof ar / sizeof(int);
    
    quick_sort(ar, 0, len - 1);
    
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d, ", ar[i]);
    }
    printf("\b\b]\n");
    
    return 0;
}

　
Go言語。Cとはまったくちがう実装ですが、これも大変にシンプルに実装できます。クイックソートは優秀なソート法として知られますが、実装も簡単なのがすばらしいですね。
Go は append() 関数があるのがラクでいいですね。Go でスライスを扱うには、append() の挙動を正確に理解しておくことが重要だと思います。
quick_sort.go

package main
import "fmt"

func quick_sort(ar []int) []int {
    var left, right []int
    if len(ar) > 1 {
        x := ar[0]
        for _, a := range ar[1:] {
            if a < x {
                left  = append(left , a)
            } else {
                right = append(right, a)
            }
        }
        left  = quick_sort(left)
        right = quick_sort(right)
        ar = append(append(left, x), right...)
    }
    return ar
}

func main() {
    ar := quick_sort([]int{3, 1, 5, 10, 2, 9, 7, 0})
    fmt.Println(ar)
}

ちなみに Ruby だとこんな感じです。実質 3行。Go言語版とやっていることは同じです。何というか、アルゴリズムがそのままコードになっているという印象ですね。

class Array
  def quick_sort
    return [] if empty?
    x, xs = first, drop(1)
    xs.select{|i| i < x}.quick_sort + [x] + xs.select{|i| i >= x}.quick_sort
  end
end

アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)

マージソート（C言語、Go言語）

マージソートを C と Go で実装してみました。このソートは二つの配列をマージ（統合）する作業がキモです。それぞれソートされた二つの配列を、統合してひとつのソートされた配列を作るわけですね。これができればあとは簡単です。

C言語。
merge_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void merge(int ar[], int p, int q, int r) {
    int n1, n2, i, j, k;
    int *left, *right;
    
    n1 = q - p + 1;
    n2 = r - q;
    
    left  = malloc(sizeof(int) * (n1 + 1));
    right = malloc(sizeof(int) * (n2 + 1));
    
    for (i = 0; i < n1; i++) left[i]  = ar[p + i];
    for (i = 0; i < n2; i++) right[i] = ar[q + i + 1];
    
    left[n1]  = (int)INFINITY;
    right[n2] = (int)INFINITY;
    
    i = j = 0;
    for (k = p; k <= r; k++) {
        if (left[i] < right[j]) {
            ar[k] = left[i++];
        } else {
            ar[k] = right[j++];
        }
    }
    
    free(right);
    free(left);
}

void merge_sort(int ar[], int p, int r) {
    if (p >= r) return;
    int q = (p + r) / 2;
    merge_sort(ar, p, q);
    merge_sort(ar, q + 1, r);
    merge(ar, p, q, r);
}

int main() {
    int ar[] = {3, 1, 5, 2, 9, 7, 0};
    int len = sizeof ar / sizeof(int);
    
    merge_sort(ar, 0, len - 1);
    
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d, ", ar[i]);
    }
    printf("\b\b]\n");
    
    return 0;
}

　
Go言語。C言語と同じように考えていましたが、C の配列と Go のスライスはかなりちがうので、勘ちがいで苦しみました。最初から考え直してみてやっとできました。実際、C と全然ちがいますよね。
merge_sort.go

package main
import "fmt"

func merge(left, right []int) []int {
    result := []int{}
    for len(left) > 0 && len(right) > 0 {
        if left[0] < right[0] {
            result = append(result, left[0])
            left = left[1:]
        } else {
            result = append(result, right[0])
            right = right[1:]
        }
    }
    return append(result, append(left, right...)...)
}

func merge_sort(ar []int) []int {
    if len(ar) > 1 {
        q := len(ar) / 2
        ar = merge(merge_sort(ar[:q]), merge_sort(ar[q:]))
    }
    return ar
}

func main() {
    ar := merge_sort([]int{3, 1, 5, 10, 2, 9, 7, 0})
    fmt.Println(ar)
}

　
C は return で配列が返せないけれど、Go はスライスを返せるというちがい…。

Ruby 版。

class Array
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result.push((a[0] <= b[0]) ? a.shift : b.shift)
      end
      result + a + b
    }
    
    return self if length <= 1
    q = length / 2
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end

挿入ソート（C言語、Go言語）

C言語で挿入ソートです。挿入ソートは遅いけれどわかりやすい。カードで考えると、（ソート済の）並んだカードの正しい位置に、残ったカードをそれぞれ一枚ずつ挿入していく（なのでそれもソート済になっている）というやり方で全体をソートします。
insertion_sort.c

#include <stdio.h>

void insertion_sort(int ar[], int len) {
    int i, j, key;
    
    for (j = 1; j < len; j++) {
        key = ar[j];
        i = j - 1;
        while (i >= 0 && ar[i] > key) {
            ar[i + 1] = ar[i];
            i--;
        }
        ar[i + 1] = key;
    }
}

int main () {
    int ar[] = {3, 1, 5, 2, 9, 7, 0};
    int len = sizeof ar / sizeof(int);
    
    insertion_sort(ar, len);
    
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d, ", ar[i]);
    }
    printf("\b\b]\n");
    
    return 0;
}

　
Ruby FFI 化してみる。C言語だけで配列をシャッフルしてベンチマークを取るのが面倒くさい。
insertion_sort_ffi.rb

require 'ffi'

module MyModule
  extend FFI::Library
  ffi_lib "./insertion_sort.so"
  attach_function :insertion_sort, [:pointer, :int], :void
end

p ar = [*0..10].shuffle
size = ar.size
pointer = FFI::MemoryPointer.new(:int, size)
pointer.put_array_of_int(0, ar)

MyModule.insertion_sort(pointer, size)
p pointer.read_array_of_int(size)

ベンチマーク。

require 'ffi'
require 'benchmark'

ar = [*0..10000].shuffle

Benchmark.bm do |x|
  x.report {MyModule.insertion_sort(pointer, size)}
end

結果。

       user     system      total        real
   0.090000   0.000000   0.090000 (  0.090020)

pure Ruby からほぼ14倍くらいの高速化ということになるのかな（参照）。まったく同様のコードの場合と比較すれば、25倍以上速くなったことになる。ちなみに Ruby 組み込みの sort メソッドを使えば、この C言語（FFI）の場合と比べものにならないくらい速い。何ソートなのだろうな。

※参考
Ruby FFI でエラトステネスの篩 - Camera Obscura
　

Go言語版

C と似た Go言語だとこんな感じかな。
insertion_sort.go

package main
import "fmt"

func insertion_sort(ar []int) []int {
    for j := 1; j < len(ar); j++ {
        key := ar[j]
        i := j - 1
        for ; i >= 0 && ar[i] > key; i-- { ar[i + 1] = ar[i] }
        ar[i + 1] = key
    }
    return ar
}

func main() {
    ar := insertion_sort([]int{3, 1, 5, 2, 9, 7, 0})
    fmt.Println(ar)
}

明らかに C言語っぽいのだけれど、随分とすっきりしていますね。出力もラクだし。自分はこちらの方が好きだなあ。
しかし Ruby から呼び出すのはわからんね。FFI を使おうと思ったが、Go のスライスにどうやって渡したらいいかわからなかった。

あみだくじの横線（Ruby）

アルゴリズム・パズルです。

問題：
1 ~ 7 の数字を並べてあみだくじを作ることを考えます。引く横線の数を 10本とするとき、下に得られる数字の並びは何とおりになるでしょうか。ただし、下に得られる数字の並びが 10本より少ない横線のあみだくじで既に得られる場合、それは除くことにします。

　
Ruby で解いてみました。
q57.rb

require 'set'

N = 7
List = "1234567"

def exchange(i, ls, num)
  ls[i], ls[i + 1] = ls[i + 1], ls[i]
  if num == 10
    @result << ls
  else
    @store << ls
    (N - 1).times do |j|
      next if i == j
      exchange(j, ls.dup, num + 1)
    end
  end
end

@store = Set[List]
@result = Set.new
(N - 1).times {|i| exchange(i, List.dup, 1)}
puts (@result - @store).size    #=>573

答えはいちおう 573通りと求められたのですが、時間が約 16秒もかかってしまいました。exchange() の呼び出しは 14648436回もあります。力任せのやり方で、これではダメですね。

模範解答の一。

v, h = 7, 10
total = 0

[*0..v - 1].permutation do |final|
  cnt = 0
  v.times do |i|
    cnt += final.take_while {|j| j != i}.count {|k| k > i}
  end
  total += 1 if cnt == h
end
puts total

超シンプルなコードなのだが、これで 0.1秒。さらに高速なアルゴリズムも紹介されている…。すごいな。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

公平に分けられたケーキ（Ruby）

アルゴリズム・パズルです。

問題：
16cm × 12cm の長方形のケーキがあります。二人で交互にケーキを切るのですが、ケーキを切った人が小さい方のケーキを取り、交代して残りをさらに切るというようにします。（ただし切り方は、辺に平行に直線的に切り、しかも切ってできたケーキの辺の長さは cm 単位になるようにします。）これを最小が 1cm × 1cm になるまで続けます。
さて、切り終えたとき二人の取ったケーキのそれぞれの総量が等しくなるとします。このような切り方は何とおりもありますが、その中で切った「切り口」の長さの総和を出すとき、その最小値を求めなさい。

　
Ruby で解いてみました。コードは以下です。
q56.rb

require 'set'

#(x, y)のケーキを切ってできる全ての (面積, 切った長さの合計) のペアを返す
#ただし面積はここでカットした人の総計
def cut(x, y)
  x, y = y, x if x < y
  return @memo[[x, y]] if @memo.has_key?([x, y])
  return Set[[1, 1]] if x == 2 and y == 1
  
  result = Set.new
  
  #前の人がカットしたところから自分の分を求める
  calc = proc do |s, t|
    cut(s, t).each do |sqar, ln|
      square = x * y - sqar
      next if square > X * Y / 2    #高速化
      length = ln + s
      result << [square, length]
    end
  end
  
  #可能なあらゆる場合でケーキを切る
  (x / 2).times {|i| calc.call(y, x - i - 1)}
  (y / 2).times {|i| calc.call(x, y - i - 1)}
  
  @memo[[x, y]] = result
end

X, Y = 16, 12
@memo = {}

result = cut(X, Y)
p result.select {|sqar, _| sqar == X * Y / 2}.sort_by {|_, ln| ln}[0]    #=>[96, 47]

答えは 47cm です。これはかなりむずかしかったです。あまりいい解き方とも思えません。実行時間は自分の環境で 1.5秒ほどでした。もっとも深いループの回数は 1386985回です。

なお、標準添付ライブラリの set を使っていますが、これを配列でやると飛んでもないことになってしまいます。

※追記（3/7）
ハッシュを使ってほんの少し書き替えたところ、劇的に高速化しました。実行時間は 0.05秒ほどになりました。じつに 30倍の高速化です。アルゴリズムはまったく同じですが、探索の際にうまく枝刈りをする方法を思いつきました。もっとも深いループの回数は 33192回なので、ほぼ 1 / 40 になっています。コードはこちら。30cm × 30cm の場合でも 0.5秒足らずで終了します。
　
※再追記（4/14）
あとから見なおしたらよくこんなこと思いついたなと思いました。関数 calc で前の面積から次の面積を求めるところが我ながら巧妙かと感じます。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

GTK+ でカラーパレットを作る（Ruby）

いつも色がうまく選べないので、自分用に GTK+ を使って色を試すことのできるコマンドを作ってみました。Gem 'thor', 'gtk2' が必要です。

コード。
color_p

require 'thor'
require 'gtk2'

class MyWindow < Gtk::Window
  def initialize
    super("color palette")
    set_default_size(250, 250)
    set_resizable(false)
    
    colorsel = Gtk::ColorSelection.new
    entry  = Gtk::Entry.new
    
    vbox = Gtk::VBox.new
    add(vbox)
    vbox.pack_start(colorsel, false, true, 0)
    vbox.pack_start(entry, true, true, 0)
    colorsel.current_color = Gdk::Color.new(0, 0, 0)
    
    # カラーパレット変更時
    colorsel.signal_connect("color-changed") do |w|
      c = w.current_color
      t = "(#{c.red.to_s(16)}, #{c.green.to_s(16)}, #{c.blue.to_s(16)})"
      entry.set_text(t)
    end
    
    signal_connect("destroy") {Gtk.main_quit}
    show_all
  end
end

class ColorPalette < Thor
  default_command :select
  desc 'select', 'Run color palette.'
  def select
    w = MyWindow.new
    Gtk.main
  end
end

ColorPalette.start

　
下のサイトを参考にさせて頂きました。ありがとうございます。
Ruby Entry markup: いち雑記

スパイログラフを描いてみる（Ruby）

スピログラフ デラックス 【日本正規品】

「スパイログラフ」というのは商品名で、数学的には「内トロコイド」というものになります。2つの円を組み合わせて図形を描くもので、これで遊んでみたことのある方は少なくないのではないでしょうか。

こんなのです。クリックで拡大します。

　

Ruby で描いてみました。描画には自作の Gem 'oekaki' を使っています。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた（Ruby） - Camera Obscura
spirograph.rb

require 'oekaki'

Width, Height = 620, 620
R = 300

r1, r2, ratio = 16.0, 11.0, 0.8

Oekaki.app width: Width, height: Height, title: "spirograph" do
  w, h = Width / 2, Height / 2
  draw do
    clear(color(0x0bff * 0.3, 0xe0ff * 0.3, 0xe6ff * 0.3))
    circle(true, w, h, R, color(0xffff, 0xffff, 0xffff))
    color(0xffff, 0, 0xffff)
  end
  
  step = PI / 180 * 10
  rot = ->(θ) { Matrix[[cos(θ), -sin(θ)], [sin(θ), cos(θ)]] }
  r = r2 / r1
  v1 = Vector[R * (1 - r), 0]
  v2 = Vector[R * r * ratio, 0]
  
  position = ->(θ) { rot.(θ) * v1 + rot.(θ * (1 - 1 / r)) * v2 }
  
  e = Enumerator.new do |y|
    θ = 0
    a = position.(θ)
    loop do
      θ += step
      b = position.(θ)
      y << [a, b]
      a = b
    end
  end
  
  timer(10) do
    p1, p2 = e.next
    line(w + p1[0], h - p1[1], w + p2[0], h - p2[1])
  end
end

パラメータ r1, r2, ratio を変えるといろいろな図形が描画されます。ただし r1 > r2, 0 < ratio < 1 にして下さい。