2016-05-03

diff を清書する、加えて gem にする

気がつけば。diff を実装してから7年も経っていました。

diffをつくる(3) -後編 - エンジニアのソフトウェア的愛情

案の定、考え方がかなり頭から抜けて行ってしまっているのですが、当時 diff について詳しい記事を書かれていた方がいらっしゃって、加えてこの記事にリンクを貼ってくださっていたおかげでそれを辿って当該記事にたどり着くことができて、どうにか再実装にこぎつけることができました。感謝です。

Diff algorithm - 枕を欹てて聴く

C++ で再実装

少々思うところがあって。C++の実装を書き直してみました。

職業プログラマに転向してからは主に Ruby を使っていて、C++ の方はすっかり進歩が止まってしまっていたものと思っていたのですが、それでも7年前のコードを見ると粗が目に付きます。

GitHub - mattsan/myers_diff: Myers' Diff Algorithm

利用例。

#include <iostream>
#include <vector>
#include <string>

#include "myers.h"

int main(int, char* [])
{
    using namespace emattsan::myers;

    std::string fooBarBaz = "fooBarBaz";
    std::string FooBazBar = "FooBazBarfoz";

    std::vector<EditType> ses = diff(fooBarBaz, FooBazBar);

    std::string::const_iterator i1 = fooBarBaz.begin();
    std::string::const_iterator i2 = FooBazBar.begin();
    std::for_each(ses.begin(), ses.end(), [&](EditType edit_type) {
        switch(edit_type)
        {
        case DELETE:
            std::cout << "- " << *i1 << std::endl;
            ++i1;
            break;
        case ADD:
            std::cout << "+ " << *i2 << std::endl;
            ++i2;
            break;
        default:
            std::cout << "  " << *i1 << std::endl;
            ++i1;
            ++i2;
            break;
        }
    });

    return 0;
}

ビルド & 実行。

$ g++ --std=c++11 -o sample sample.cpp 
$ ./sample
- f
+ F
  o
  o
  B
  a
- r
+ z
  B
  a
+ r
+ f
+ o
  z

Ruby で再実装

gem 作りの練習をしているので勢いで Ruby で実装してみた。

GitHub - mattsan/ruby_myers_diff: Myers' Diff Algorithm

利用例。

Gemfile 。

gem 'myers_diff', github: 'mattsan/ruby_myers_diff'

サンプル。

require 'myers_diff'

FooBarBaz = "fooBarBaz";
FooBazBar = "FooBazBarfoz";

ses = MyersDiff.diff(FooBarBaz, FooBazBar)

i1 = FooBarBaz.chars.each
i2 = FooBazBar.chars.each

ses.each do |edit_type|
  case edit_type
  when :DELETE
    puts "- #{i1.next}"
  when :ADD
    puts "+ #{i2.next}"
  else
    puts "  #{i1.next}"
    i2.next
  end
end

インストール。

$ bundle install --path vendor/bundle

実行。

$ bundle exec ruby sample.rb 
- f
+ F
  o
  o
  B
  a
- r
+ z
  B
  a
+ r
+ f
+ o
  z

2016-04-29

Config

Ruby Rails めも

GitHub - railsconfig/config: Easiest way to add multi-environment yaml settings to Rails, Sinatra, Pandrino and other Ruby projects.

Gemfile

gem 'config'

install

$ be rails g config:install
      create  config/initializers/config.rb
      create  config/settings.yml
      create  config/settings.local.yml
      create  config/settings
      create  config/settings/development.yml
      create  config/settings/production.yml
      create  config/settings/test.yml
      append  .gitignore

config/settings.yml

format: 'Hello, %s!'

config/settings/development.yml

world: 'development world'

config/settings/test.yml

world: 'test world'

config/settings/production.yml

world: 'production world'

$ bundle exec rails r 'puts Settings.format % Settings.world'
Hello, development world!

$ RAILS_ENV=development bundle exec rails r 'puts Settings.format % Settings.world'
Hello, development world!

$ RAILS_ENV=test bundle exec rails r 'puts Settings.format % Settings.world'
Hello, test world!

$ RAILS_ENV=production bundle exec rails r 'puts Settings.format % Settings.world'
Hello, production world!

2016-04-26

SettingsLogic

Ruby Rails めも

GitHub - binarylogic/settingslogic: A simple and straightforward settings solution that uses an ERB enabled YAML file and a singleton design pattern.

Gemfile に追加する。

gem 'settingslogic'

config/initializers/settings.rb ファイルを追加する。

class Settings < Settingslogic
  source Rails.root.join('config', 'settings.yml')
  namespace Rails.env
end

config/settings.yml ファイルを追加する。

defaults: &defaults
  mesozoic:
    - Triassic
    - Jurassic
    - Cretaceous

development:
  <<: *defaults

test:
  <<: *defaults

production:
  <<: *defaults

設定値を取り出す。

$ bundle exec rails runner 'p Settings.mesozoic'
["Triassic", "Jurassic", "Cretaceous"]

2016-04-24

特定のモジュールをインクルードしているクラスを抽出する

Ruby めも

探せばもっとよい方法があるかもしれない。

module Hoge
  def hoge
    puts "I'm #{self.class}. I'm including Hoge."
  end
end

class Foo
  include Hoge
end

class Bar
  include Hoge
end

class Baz < Bar
end

ObjectSpace.each_object(Class).select {|klass| klass.included_modules.include? Hoge }.each do |class_including_hoge|
  class_including_hoge.new.hoge
end

$ ruby hoge.rb
I'm Baz. I'm including Hoge.
I'm Bar. I'm including Hoge.
I'm Foo. I'm including Hoge.

2016-04-13

read CSV file

Ruby めも

備忘録。

# CP932 から UTF-8 に変換し、先頭行をヘッダとして読み込む
CSV.foreach(csv_file_path, encoding: 'CP932:UTF-8', headers: true) do |row|
  p row
  # 行を Hash で欲しい場合
  # p row.to_hash
end

2016-03-03

もっと気軽に Prolog でフィボナッチ数列

Prolog めも

先日、フィボナッチ数列を求める Prolog のコードを書いたわけですが。

もっとすっきりと書けることに気がつきました。

add(X, Y, Z) :-
  Z is (X + Y).

fib(N, Fib) :-
  length(Fib, N),
  append(Fib, [_], [1|Fib2]),
  append(Fib2, [_], [1|Fib3]),
  maplist(add, Fib, Fib2, Fib3).

1番目からN番目までのフィボナッチ数の数列を Fib 、2番目からN + 1番目までのフィボナッチ数の数列を Fib2 、3番目からN + 2番目までのフィボナッチ数の数列を Fib3 とすると、つまり

Fib = { F₁, F₂, F₃, ..., F_{N - 1}, F_N }
Fib2 = { F₂, F₃, F₄, ..., F_N, F_{N + 1} }
Fib3 = { F₃, F₄, F₅, ..., F_{N + 1}, F_{N + 2} }

とすると、

Fib の要素の数は N に等しい
Fib と { F_{N + 1} } を連結した数列は、Fib2 の先頭に F₁ ( = 1 ) を追加した数列に等しい
Fib2 と { F_{N + 2} } を連結した数列は、Fib3 の先頭に F₂ ( = 1 ) を追加した数列に等しい
Fib の i 番目の要素 F_i と Fib2 の i 番目の要素 F_{i + 1} を加えたものは Fib3 の i 番目の要素 F_{i + 2} に等しい

となるので、それをそのままコードにしてみました。
ただ F_{N + 1} と F_{N + 2} の値は利用しないので、変数名を指定せずにワイルドカードにしています。

2016-02-28

Fibonacci numbers with Prolog

Prolog めも

% fib.pro

:- initialization(main).

add(X, Y, Z) :-
  Z is (X + Y).

fib(N, [1,1|Fib3]) :-
  append(Fib1, [_], Fib2),
  append(Fib2, [_], Fib3),
  length([1,1|Fib3], N),
  maplist(add, [1,1|Fib1], [1|Fib2], Fib3),
  !.

puts(N) :-
  format("~d~n", [N]).

main :-
  current_prolog_flag(argv, [_,Length|_]),
  number_atom(N, Length),
  fib(N, F),
  maplist(puts, F),
  halt.

Build.

$ gplc fib.pro

Run.