Hatena::ブログ(Diary)

エンジニアのソフトウェア的愛情 このページをアンテナに追加 RSSフィード Twitter

2017-01-09

Prolog だって Key-Value を扱いたい

不思議な記述を見つけました。

An object in JSON is presented as a bunch of keys and values within curly braces, in Prolog I have used a function and a KV list like so:

obj([key1-value1, key2-value2, ...]).

Present your terms like that and everything should be fine. See the source file json_encode.pl for a full explanation and some examples that should hopefully explain it all.

https://github.com/emacstheviking/gnuprolog-json


Prolog に “key-value” といった記法があったけ? と数日考え込んだのですが、Prolog では明示的に評価するまで記述した内容がそのまま値として扱われるということを利用しているということに思い至りました。


$ gprolog
| ?- A = 2 - 1.
A = 2-1

変数 A の値は 1 ではなく 2-1 であることがわかります。

2-11 とはマッチしません。

| ?- 1 = 2 - 1.
no

2-1 を明示的に評価することで値として 1 がえられます。

| ?- A is 2 - 1.
A = 1
yes
| ?- A is 2 - 1, 1 = A.
A = 1
yes


と、いうことは。評価前であれば演算子 - も含めた形で変数にマッチさせることができます。

| ?- A - B = 2 - 1.
A = 2
B = 1
yes

-演算は評価されないので、数値でなくても構いません。

| ?- A - B = abc - def. 
A = abc
B = def
yes

評価すると当然のようにエラーになります。

| ?- A is abc - def.   
uncaught exception: error(type_error(evaluable,abc/0),(is)/2)

これが “key-value” の正体だったようです。


これらを踏まえて。

key_value.pro を用意。

find(_, [], not_found) :- !.
find(K, [K-V|_], V) :- !.
find(K, [_|KVs], V) :- find(K, KVs, V).

GNU-Prolog で実行。

$ gprolog
| ?- ['key_value.pro'].
yes
| ?- find(a, [a-1, b-2, c-3], V).
V = 1
yes
| ?- find(b, [a-1, b-2, c-3], V).
V = 2
yes
| ?- find(c, [a-1, b-2, c-3], V).
V = 3
yes
| ?- find(d, [a-1, b-2, c-3], V).
V = not_found
yes

ペアが作れればよいので [ [a, 1], [b, 2], [c, 3] ] でもよいのですが、見やすさ書きやすさ誤った形式の排除という点で key-value という記述のメリットはありそうです。

ちなみに。

評価されなければよいので演算子- でなくても構いません。

| ?- A + B = abc + def.
A = abc
B = def
yes
| ?- A / B = abc / def.
A = abc
B = def
yes
| ?- A : B = abc : def.
A = abc
B = def
yes

いつか読むはずっと読まない:青春ものだった

私はサンリオSF文庫は読んだことはないのですが、こうして復刊されたものを読むと良書ぞろいだったのだろうなぁと思わずにはいられません。

ハローサマー、グッドバイ (河出文庫)

ハローサマー、グッドバイ (河出文庫)

2016-12-23

塗らずに蹂躙する〜どう書くE10の問題から

今月の初めの土曜日、秋葉原/神田開催どう書くの第10回が開催されました。

問題とみなさんの回答へのリンクはこちらから。

当日の時間内にテストにパスするコードを書けなかっただけでなく、理屈の上ではパスするものの到底時間内に実行が終わらないアイディアしか思い浮かばず。惨敗しました。

セルを塗り分けるには隣接したセルを調べて同じ色であれば同じ番号をふるということが必要になります、素朴なアイディアでは。しかしここが落とし穴。セルの数は 3入力の文字列のながさ×2 になるため、もっとも長い文字列の入力ではセルの数が 4,782,969 になり、隣の隣の隣の…と調べに行ったままなかなか帰ってこないというありさまでした。加えて、再帰を使うと簡単に書けるのですが帰ってくる前にメモリが尽きるという様相に。

で。作戦変更。端からセルを一つ一つ走査する方法を 3 日ぐらいかけて考えていました。

基本的な考え方は、左から右へ上から下へセルを一つ一つ調べ、左か上にすでに番号のふられたセルがあればその番号と同じ番号をふり、そのようなセルがなければ新しい番号をふる、すべてのセルに番号がついたら、番号の数が塗り分けの数になる、というもの。

f:id:E_Mattsan:20161223124708j:image


この方法を単純に適用するだけでは、たとえば上の方では別の領域だったけれども下までたどったら繋がっていた、という場合にうまくいきません。そこで繋がっていた場合は一方はもう一方の別名だった、ということを記録するようにします。

番号は 1 から順番に大きくなる、先にふられた番号の方を有効とする、というルールに決めておくと、小さい方を実際の値、大きい方を別名と定義できます。すべてのセルに番号がついたら、記録しておいた別名を実際の番号にふりなおすことで繋がったセルには同じ番号がふられた状態になります。

f:id:E_Mattsan:20161223124702j:image


そうやって解いたのがこちら。

私のマシンで 10 秒程度ですべてのテストにパスするようになりました。


しかし実は領域の数だけを知りたいのであれば番号をふりなおす必要なくて、ふられた番号の中から別名として登録されている番号を引いて残る番号の、その個数が領域の数と同じになります。さらに記憶している番号に重複がなければ、全体の番号の個数から別名の個数を引いても答えがえられます。すると別名と実際の値の表を用意する必要もなく、単に別名だった番号を記録しておけばよいことになります。


そのアイディアにもとづいて書き直したのがこちら。実行時間はさらに 3 分の 1 の 3〜4 秒まで短縮することができました。

require 'benchmark'
require 'set'

PATTERNS = {
  'X' => [[1, 0], [0, 1], [2, 1], [1, 2]],
  'O' => [[0, 0], [2, 0], [1, 1], [0, 2], [2, 2]]
}

def filled_area_count(size, blocks)
  sentinel_index = size ** 2
  board = Array.new(sentinel_index)
  blocks.each {|x, y| board[y * size + x] = sentinel_index }

  alias_table = Set.new

  next_index = 0
  sentinel_index.times do |i|
    next if board[i]
    left_index  = (i % size == 0) ? sentinel_index : board[i - 1]
    upper_index = (i < size) ? sentinel_index : board[i - size]

    if (left_index == sentinel_index) && (upper_index == sentinel_index)
      board[i] = next_index
      next_index += 1
    elsif left_index == upper_index
      board[i] = left_index
    else
      actual_index, alias_index = (left_index < upper_index) ? [left_index, upper_index] : [upper_index, left_index]
      alias_table << alias_index
      board[i] = actual_index
    end
  end

  alias_table.delete(sentinel_index)
  next_index - alias_table.size
end

def solve(input)
  blacks = input.chars.reduce([[0, 0]]) {|blacks, c|
    blacks.map {|cell|
      PATTERNS[c].map {|x, y| [cell[0] * 3 + x, cell[1] * 3 + y] }
    }.flatten(1)
  }

  filled_area_count(3 ** input.length, blacks).to_s
end

def test(input, expected)
  actual = solve(input)
  if actual == expected
    print "\x1b[1m\x1b[32m.\x1b[0m"
  else
    puts(<<~EOS)
      \x1b[1m\x1b[31m
      input:    #{input}
      expected: #{expected}
      actual:   #{actual}\x1b[0m
    EOS
  end
end

def test_all(data)
  data.each do |line|
    input, expected = line.split
    test(input, expected)
  end

  puts
end

time = Benchmark.realtime { test_all(DATA) }

puts format('%8.3f sec', time)

__END__
X 5
O 4
XX 5
OX 10
XO 9
XOO 17
OXX 21
OXO 18
OOOX 130
OXXO 29
XXOX 81
XOXXO 89
OOOOX 630
OXOOO 66
OXOXOX 2001
OXOXXO 417
OXXOXX 1601
XXXOXOO 345
OOOOOXO 3258
OXXOXXX 6401

いつか読むはずっと読まない:神・銃

短編 “The God-Gun” の翻訳「神・銃」を「ゴッド・ガン」と改め、それを表題作とした短編集。

ベイリーの本は何冊か読んでいるはずなのですが、からっきし内容を覚えていないという体たらく。新訳版となった「カエアンの聖衣」を新鮮な気持ちで読めたのでありがたいということもできなくはないのですが。

「神・銃」「ゴッド・ガン」という字面を見たときに思い出すのが「禅〈ゼン・ガン〉銃」(原題 “The Zen Gun”)ですが、これもまた物の見事に内容を思い出せない。

そのうち読み返そうと思うのですが、書籍の山から本書を探し出して引っ張り出すのが、過去の記憶を引っ張り出すのと同じぐらい大変そうというのが目下の課題。

2016-11-23

FizzBuzzを宣言的に書く、宣言できない場合は宣言っぽく書く

プログラミング Elixir を読んでいます。

プログラミングElixir

プログラミングElixir

Elixir

プログラミング Elixir の第5章で FizzBuzz を書く練習問題が出てきます。

# $ elixir fizz_buzz.exs

fizzBuzz3 = fn
  0, 0, _ -> "FizzBuzz"
  0, _, _ -> "Fizz"
  _, 0, _ -> "Buzz"
  _, _, n -> "#{n}"
end

fizzBuzz = fn n -> fizzBuzz3.(rem(n, 3), rem(n, 5), n) end

fizzBuzzSeries = fn first, last -> first..last |> Enum.map(fizzBuzz) end

fizzBuzzSeries.(1, 20) |> Enum.join("\n") |> IO.puts

Erlang

VM は同じでもシンタクスが違うので見た目が結構違って見えます。

% $ erlc fizz_buzz.erl
% $ erl -run fizz_buzz main

-module(fizz_buzz).
-export([main/0]).

fizz_buzz(0, 0, _) -> "FizzBuzz";
fizz_buzz(0, _, _) -> "Fizz";
fizz_buzz(_, 0, _) -> "Buzz";
fizz_buzz(_, _, N) -> integer_to_list(N).

fizz_buzz(N) -> fizz_buzz(N rem 3, N rem 5, N).

fizz_buzz_series(First, Last) -> [fizz_buzz(N) || N <- lists:seq(First, Last)].

main() ->
  lists:map(fun(S) -> io:format("~s~n", [S]) end, fizz_buzz_series(1, 20)),
  erlang:halt(0).

Haskell

Haskell で書いてもほぼ同じ。

-- $ ghc --make fizz_buzz
-- $ ./fizz_buzz

fizzBuzz3 0 0 _ = "FizzBuzz"
fizzBuzz3 0 _ _ = "Fizz"
fizzBuzz3 _ 0 _ = "Buzz"
fizzBuzz3 _ _ n = show n

fizzBuzz n = fizzBuzz3 (n `mod` 3) (n `mod` 5) n

fizzBuzzeSeries = [ fizzBuzz n | n <- [1..20]]

main = putStrLn $ unlines fizzBuzzeSeries

Prolog

関数でなく述語で表現するのでまた違った印象。

% $ gprolog --consult-file fizz_buzz.pro --entry-goal main

fizz_buzz(0, 0, _, "FizzBuzz") :- !.
fizz_buzz(0, _, _, "Fizz") :- !.
fizz_buzz(_, 0, _, "Buzz") :- !.
fizz_buzz(_, _, N, S) :- number_codes(N, S), !.

fizz_buzz(N, S) :- N3 is N rem 3, N5 is N rem 5, fizz_buzz(N3, N5, N, S).

fizz_buzz_series(First, Last, FBS) :- findall(FB, (between(First, Last, N), fizz_buzz(N, FB)), FBS).

puts(S) :- format("~s~n", [S]).

main :- fizz_buzz_series(1, 20, FBS), maplist(puts, FBS), halt.

Ruby

Rubyメソッドのレベルでのパタンマッチの機能が今はないので、case を使ってそれっぽく書いてみる。

# $ ruby fizz_buzz.rb

def fizz_buzz3(n3, n5, n)
  case [n3, n5, n]
  when [0,  0,  n] then 'FizzBuzz'
  when [0,  n5, n] then 'Fizz'
  when [n3, 0,  n] then 'Buzz'
  else                "#{n}"
  end
end

def fizz_buzz(n)
  fizz_buzz3(n % 3, n % 5, n)
end

def fizz_buzz_series(first, last)
  (first..last).map {|n| fizz_buzz(n) }
end

puts fizz_buzz_series(1, 20).join("\n")

C++ Template Metaprograming

パタンマッチングは、C++ にはないけれども C++ Template では使える。コード量が多いのが難点。

// $ g++ --std=c++11 -o fizz_buzz fizz_buzz.cpp
// $ ./fizz_buzz

#include <string>
#include <iostream>
#include <algorithm>

template<int N1, int N2, int N3> struct FizzBuzz3 { static const std::string value; };
template<int N3>                 struct FizzBuzz3<0, 0, N3> { static const std::string value; };
template<int N2, int N3>         struct FizzBuzz3<0, N2, N3> { static const std::string value; };
template<int N1, int N3>         struct FizzBuzz3<N1, 0, N3> { static const std::string value; };

template<int N1, int N2, int N3> const std::string FizzBuzz3<N1, N2, N3>::value = std::to_string(N3);
template<int N3>                 const std::string FizzBuzz3<0, 0, N3>::value = "FizzBuzz";
template<int N2, int N3>         const std::string FizzBuzz3<0, N2, N3>::value = "Fizz";
template<int N1, int N3>         const std::string FizzBuzz3<N1, 0, N3>::value = "Buzz";

template<int N> struct FizzBuzz { static const std::string value; };

template<int N> const std::string FizzBuzz<N>::value = FizzBuzz3<N % 3, N % 5, N>::value;

struct Nil;

template<template<int> class T, int First, int Last>
struct Range
{
    typedef T<First>                  Head;
    typedef Range<T, First + 1, Last> Tail;
};

template<template<int> class T, int Last>
struct Range<T, Last, Last>
{
    typedef T<Last> Head;
    typedef Nil     Tail;
};

template<int First, int Last>
using FizzBuzzSeries = Range<FizzBuzz, First, Last>;

template<typename R>
void puts_range()
{
    std::cout << R::Head::value << std::endl;
    puts_range<typename R::Tail>();
}

template<> void puts_range<Nil>() {};

int main(int, char* [])
{
    puts_range<FizzBuzzSeries<1, 20> >();

    return 0;
}

いつか読むはずっと読まない:バイク乗りがバイクになる(なりません)

一年半ほど前からクロスバイクに乗るようになりました。十ン年まともに運動などしたことがなかった人間が面白いぐらいにのめり込んでいます。

以前だったらアンテナにさえかからなかっただろう本書、今は描写の一つ一つに反応してしまっています。

追い風ライダー (徳間文庫)

追い風ライダー (徳間文庫)

2016-10-26

Prolog が解くに適した問題がある

Prolog でコードをたびたび書いてはいますが、実用的なプログラムProlog で書けたためしがないというのが正直なところです。使い所がつかめていないのがその原因。

今もまだつかめているわけではないのですが、Prolog ならば自然に表現できて簡単に解ける例に遭遇して、そのような問題に適用すればよいのだということに気づかされました。残る課題はそのような問題であることを見極める自身の技量なわけですが。


矩形を見つける問題

実例として見つけた問題というのが、「どう書く」で出題された中にある矩形を求める部分。


XY平面上にある複数の点のうち、矩形の頂点の位置なる 4 点 {(x1, y1), (x1, y2), (x2, y1), (x2, y2)} を見つけるというもの。


Prolog で愚直に書いた

実際に矩形探しをさせてみます。x, y とも 10〜40 の値からなり重複しない点 200 個を用意して実験。

points([
  [18, 34], [32, 14], [21, 23], [24, 29], [37, 20],   [40, 28], [16, 30], [13, 33], [40, 37], [28, 23],
  [30, 38], [23, 37], [29, 20], [34, 14], [25, 26],   [12, 27], [10, 19], [30, 18], [13, 26], [18, 13],
  [10, 32], [13, 16], [15, 19], [17, 14], [38, 30],   [36, 22], [22, 38], [18, 22], [29, 12], [17, 36],
  [20, 25], [27, 21], [21, 37], [33, 14], [28, 15],   [15, 20], [37, 31], [37, 27], [20, 27], [24, 12],
  [18, 21], [32, 19], [33, 19], [27, 18], [32, 39],   [10, 36], [37, 19], [28, 16], [32, 32], [31, 12],
  [36, 14], [19, 33], [15, 28], [35, 23], [27, 17],   [26, 27], [22, 34], [24, 18], [13, 12], [31, 30],
  [28, 14], [24, 31], [31, 25], [33, 23], [29, 16],   [20, 35], [13, 35], [30, 40], [36, 25], [35, 25],
  [11, 19], [26, 17], [37, 28], [10, 25], [20, 22],   [35, 31], [20, 17], [31, 32], [33, 33], [35, 40],
  [37, 22], [39, 40], [31, 21], [38, 29], [17, 34],   [38, 13], [35, 24], [21, 38], [24, 39], [29, 30],
  [35, 22], [25, 37], [14, 15], [13, 18], [17, 30],   [24, 30], [12, 23], [10, 21], [33, 21], [13, 21],
  [32, 28], [26, 31], [27, 31], [23, 11], [14, 21],   [33, 34], [12, 28], [30, 16], [12, 18], [28, 25],
  [23, 36], [10, 35], [27, 36], [15, 17], [37, 10],   [37, 15], [24, 36], [26, 10], [11, 11], [23, 23],
  [24, 14], [13, 10], [37, 24], [32, 30], [14, 26],   [24, 25], [29, 39], [26, 18], [13, 20], [24, 28],
  [11, 22], [16, 16], [27, 35], [16, 14], [15, 12],   [17, 28], [25, 19], [33, 16], [24, 27], [32, 20],
  [16, 18], [19, 17], [39, 12], [18, 27], [27, 15],   [15, 27], [20, 15], [12, 20], [15, 16], [37, 33],
  [33, 20], [12, 33], [16, 10], [22, 37], [24, 15],   [13, 38], [37, 25], [17, 12], [18, 35], [29, 27],
  [29, 24], [32, 13], [13, 31], [16, 39], [20, 14],   [32, 38], [25, 17], [35, 15], [28, 21], [23, 39],
  [34, 24], [17, 26], [32, 10], [33, 28], [13, 24],   [29, 29], [28, 17], [14, 39], [20, 18], [13, 27],
  [40, 20], [11, 14], [22, 18], [28, 13], [32, 12],   [37, 40], [11, 37], [25, 35], [11, 31], [18, 16],
  [19, 24], [29, 37], [34, 31], [26, 19], [34, 11],   [37, 29], [20, 37], [24, 38], [35, 32], [30, 26]
]).

rect(X1, Y1, X2, Y2) :-
  points(PS),
  member([X1, Y1], PS),
  member([X1, Y2], PS),
  member([X2, Y1], PS),
  member([X2, Y2], PS),
  X1 < X2,
  Y1 < Y2.

rects(RS) :-
  findall([[X1, Y1], [X1, Y2], [X2, Y1], [X2, Y2]], rect(X1, Y1, X2, Y2), RS).

main :-
  rects(RS),
  length(RS, L),
  format("~p~n~d~n", [RS, L]).

実行。

$ time gprolog --consult-file rect.pro --entry-goal 'main, halt'
[[[32,14],[32,19],[33,14],[33,19]], ... (略)  ... ,[[24,38],[24,39],[32,38],[32,39]]]
450

real    0m0.351s
user    0m0.322s
sys     0m0.023s

すぐに答えが表示されたのには、正直驚きました。


Ruby で愚直に書く

任意の 4 点を取得して、矩形の頂点になるものを選べばよいというのなら、combination で 4 点を選び条件に合うものを選べばよいだろうと、愚直に書き直したものです。

200 個の点は同じ値です。

def points
  [
    [18, 34], [32, 14], [21, 23], [24, 29], [37, 20],   [40, 28], [16, 30], [13, 33], [40, 37], [28, 23],
    [30, 38], [23, 37], [29, 20], [34, 14], [25, 26],   [12, 27], [10, 19], [30, 18], [13, 26], [18, 13],
    [10, 32], [13, 16], [15, 19], [17, 14], [38, 30],   [36, 22], [22, 38], [18, 22], [29, 12], [17, 36],
    [20, 25], [27, 21], [21, 37], [33, 14], [28, 15],   [15, 20], [37, 31], [37, 27], [20, 27], [24, 12],
    [18, 21], [32, 19], [33, 19], [27, 18], [32, 39],   [10, 36], [37, 19], [28, 16], [32, 32], [31, 12],
    [36, 14], [19, 33], [15, 28], [35, 23], [27, 17],   [26, 27], [22, 34], [24, 18], [13, 12], [31, 30],
    [28, 14], [24, 31], [31, 25], [33, 23], [29, 16],   [20, 35], [13, 35], [30, 40], [36, 25], [35, 25],
    [11, 19], [26, 17], [37, 28], [10, 25], [20, 22],   [35, 31], [20, 17], [31, 32], [33, 33], [35, 40],
    [37, 22], [39, 40], [31, 21], [38, 29], [17, 34],   [38, 13], [35, 24], [21, 38], [24, 39], [29, 30],
    [35, 22], [25, 37], [14, 15], [13, 18], [17, 30],   [24, 30], [12, 23], [10, 21], [33, 21], [13, 21],
    [32, 28], [26, 31], [27, 31], [23, 11], [14, 21],   [33, 34], [12, 28], [30, 16], [12, 18], [28, 25],
    [23, 36], [10, 35], [27, 36], [15, 17], [37, 10],   [37, 15], [24, 36], [26, 10], [11, 11], [23, 23],
    [24, 14], [13, 10], [37, 24], [32, 30], [14, 26],   [24, 25], [29, 39], [26, 18], [13, 20], [24, 28],
    [11, 22], [16, 16], [27, 35], [16, 14], [15, 12],   [17, 28], [25, 19], [33, 16], [24, 27], [32, 20],
    [16, 18], [19, 17], [39, 12], [18, 27], [27, 15],   [15, 27], [20, 15], [12, 20], [15, 16], [37, 33],
    [33, 20], [12, 33], [16, 10], [22, 37], [24, 15],   [13, 38], [37, 25], [17, 12], [18, 35], [29, 27],
    [29, 24], [32, 13], [13, 31], [16, 39], [20, 14],   [32, 38], [25, 17], [35, 15], [28, 21], [23, 39],
    [34, 24], [17, 26], [32, 10], [33, 28], [13, 24],   [29, 29], [28, 17], [14, 39], [20, 18], [13, 27],
    [40, 20], [11, 14], [22, 18], [28, 13], [32, 12],   [37, 40], [11, 37], [25, 35], [11, 31], [18, 16],
    [19, 24], [29, 37], [34, 31], [26, 19], [34, 11],   [37, 29], [20, 37], [24, 38], [35, 32], [30, 26]
  ]
end

def rects
  points.sort.combination(4).select {|p1, p2, p3, p4|
    p1[0] == p2[0] && p1[1] == p3[1] && p3[0] == p4[0] && p2[1] == p4[1]
  }
end

rs = rects
puts rs.to_s
puts rs.size

実行。

$ time ruby rect1.rb
[[[10, 19], [10, 21], [33, 19], [33, 21]], ... (略) ... , [[37, 20], [37, 28], [40, 20], [40, 28]]]
450

real    0m22.360s
user    0m21.820s
sys     0m0.187s

それほど速くはないだろうと思いつつも、これほど数字になるとは思っていなかったので結構驚きでした。


Ruby で工夫して書く

当然、工夫すれば速くなります。

def points
  [
    # 上記と同じなので省略
  ]
end

def rects
  points.group_by {|_, y| y }
        .map {|y, ps| [y, ps.map(&:first).sort] }
        .combination(2)
        .map {|(y1, xs1), (y2, xs2)|
    (xs1 & xs2).combination(2).map {|x1, x2|
      [[x1, y1], [x1, y2], [x2, y1], [x2, y2]]
    }
  }.reject(&:empty?).flatten(1)
end

rs = rects
puts rs.to_s
puts rs.size

実行。

$ time ruby rect2.rb 
[[[17, 34], [17, 14], [33, 34], [33, 14]], ... (略) ... , [[13, 24], [13, 10], [37, 24], [37, 10]]]
450

real	0m0.121s
user	0m0.074s
sys	0m0.041s

ずいぶん速くなります。しかし Prolog で愚直に書いた場合もこれの数倍程度の時間しかかからないということは、やはり驚きです。


いつか読むはずっと読まない:付き従う正義、付き従う剣、付き従う慈

2冊目の中間、ちょっど真ん中あたりを読んでいます。半分まで読み進めてみても「異質な感じ」が終わりません。

正直最初のうちは得体の知れない感じが苦痛に感じる時もありましたが、進むにつれその感じにのめり込んでいることに気がつかされます。

2016-09-20

Fiddle を掻き鳴らしてみる

*.dllや*.soなど、ダイナミックリンクライブラリを扱うためのライブラリです。

Ruby は痒い所に手が届く便利な言語だと知ってはいましたが、こんなに便利になっているとは思いませんでした。

と、いうわけで。


Fibonacci Number

まず。適当な .so ファイルを用意します。

// libfib.cpp

#include <map>

namespace
{

std::map<int, int> memo;

}

extern "C"
{

int fibonacci_number(int n)
{
    if(n < 1)
    {
        return 0;
    }
    else if(n <= 2)
    {
        return 1;
    }
    else
    {
        if(memo.find(n) == memo.end())
        {
            memo[n] = fibonacci_number(n - 1) + fibonacci_number(n - 2);
        }
        return memo[n];
    }
}

}

.so ファイルの生成。オプションは環境に合わせて指定してください。私は El Capitan 。

$ g++ --std=c++11 -dynamiclib -o libfib.so libfib.cpp

次に。ライブラリを呼び出すモジュールを作成。extern に続いて文字列で C 言語の関数の定義をそのまま書けば済んでしまうとか、予想外の簡単さ。

# fibonacci.rb

require 'fiddle/import'

module Fibonacci
  extend Fiddle::Importer
  dlload './libfib.so'

  extern 'int fibonacci_number(int n)'
end

サンプル用意。

# sample.rb

require './fibonacci'

puts Fibonacci.fibonacci_number(10)
puts Fibonacci.fibonacci_number(20)
puts Fibonacci.fibonacci_number(30)
puts Fibonacci.fibonacci_number(40)

実行。

$ ruby sample.rb 
55
6765
832040
102334155

簡単すぎる。


Fibonacci Series

配列を扱うときは Array#pack, Array#unpack を使って文字列(バイト列)を経由して扱う模様。

配列を扱う関数を追加。

// $ g++ --std=c++11 -dynamiclib -o libfib.so libfib.cpp

#include <map>

namespace
{

std::map<int, int> memo;

}

extern "C"
{

int fibonacci_number(int n)
{
    // 省略
}

void fibonacci_series(int n, int* s)
{
    for(int i = 1; i <= n; ++i)
    {
        s[i - 1] = fibonacci_number(i);
    }
}

}

同じ要領で .so ファイルを作成。

定義を追加。

# fibonacci.rb

require 'fiddle/import'

module Fibonacci
  extend Fiddle::Importer
  dlload './libfib.so'

  extern 'int fibonacci_number(int n)'
  extern 'void fibonacci_series(int n, int* s)'
end

呼び出し。

# sample2.rb

require './fibonacci'

s = [0].pack('i') * 10            # int 型のサイズのバイト列を 10 並べたものを用意
Fibonacci.fibonacci_series(10, s) # 関数呼び出し
puts s.unpack('i' * 10)           # int 型の値 10 個に戻す

実行。

$ ruby sample2.rb 
1
1
2
3
5
8
13
21
34
55

簡単すぎる。


いつか聴くはずっと聴かない:古楽器楽団「タブラトゥーラ」

フィドルといえば、思い出すのはタブラトゥーラ。

http://www.dowland.jp/tablatura/phot2/tab.jpg

ダウランドアンドカンパニイ 公式サイトより)


これがフィドル。

http://www.dowland.jp/tablatura/phot2/tasaki.jpg

同サイトより)


CD 購入は こちら から。サンプルも聴けます。