挿入ソート(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 のスライスにどうやって渡したらいいかわからなかった。