AOJ - DPL_1 D (最長増加部分列) を解いてみた
AOJ - DPL_1 Dは、最長増加部分列(Longest Increasing Subsequence)です
最長増加部分列 | 動的計画法 | Aizu Online Judge
これが解けると、AtCoderの以下の問題も解けます
D: トランプ挿入ソート - AtCoder Beginner Contest 006 | AtCoder
また、関連問題は以下のブログが詳しいです
アルゴリズム自体の解説はWikipediaやGeeksForGeekが良かったです
- Longest increasing subsequence - Wikipedia
- Longest increasing subsequence problem - Algorithms Tutorial
- Dynamic Programming | Set 3 (Longest Increasing Subsequence) - GeeksforGeeks
- Longest Increasing Subsequence Size (N log N) - GeeksforGeeks
最長増加部分列の基本
最長増加部分列(LIS)とは
問題設定
まずはWikipediaの記述から...
In the first 16 terms of the binary Van der Corput sequence
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
a longest increasing subsequence is
0, 2, 6, 9, 11, 15.
This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,
0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15
are other increasing subsequences of equal length in the same input sequence.
van der Corput 列*1の最初の16個の数値
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
において、最長増加部分列は
0, 2, 6, 9, 11, 15.
この部分列は長さ6である、ということは（当たり前だが）7要素の増加部分列を持たない。この例における最長増加部分列は一意ではない、例えば
0, 4, 6, 9, 11, 15 もしくは 0, 4, 6, 9, 13, 15
は入力された同一の列内で等しい長さを持つ他の増加部分列であると言える
アルゴリズム
線形探索版のプログラム - O(N^2)
- 与えられる配列を arr[n]、最長増加部分列をlis[n] であるとする
- arr と lis の出来上がりは以下のようになる
- 上がarrayで下がlis
lisの配列にはそのインデックスまでの配列における増加部分列の長さが入る
| 9 | 5 | 2 | 8 | 7 | 3 | 1 | 6 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 2 | 2 | 1 | 3 | 3 | 4 |
lis配列の最後に入る 4 が最長増加部分列となる。
サンプルプログラム
線形探索版のプログラム - O(N^2)
lines = <<'EOS' 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 EOS #lines = $stdin.read array = lines.split("\n") def get_lis(arr) lis_arr = Array.new(arr.length){1} length = 1 puts arr.to_s puts lis_arr.to_s for i in 1...arr.length for j in 0...i lis_arr[i] = lis_arr[j] + 1 if arr[j] < arr[i] and lis_arr[i] < (lis_arr[j]+1) end end puts lis_arr.to_s lis_arr.max end puts get_lis(array[0].split(" ").map(&:to_i).to_a)
- 探索対象の配列を i 回ループし、その中で j 回ループするので、計算量が O(n^2) になる、遅い
- これも動的計画法の１つらしい
二分探索版のプログラム - O(N log N)
lines = <<'EOS' 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 EOS #lines = $stdin.read array = lines.split("\n") def ceil_index(array, l, r, key) while r-l > 1 m = l + (r-l)/2 if array[m] >= key r = m else l = m end end r end def get_lis(arr) tail = Array.new(arr.length) len = 1 tail[0] = arr.first for i in 1...arr.length if arr[i] < tail[0] tail[0] = arr[i] elsif arr[i] > tail[len-1] # v[i] extends largest subsequence tail[len] = arr[i] len = len + 1 else # option(a): use binary search # but, ruby's Array#bsearch_index requires # all array's elements sorted #idx = tail[0..i].compact.bsearch_index do |x| # x >= arr[i] #end # option(b): implement binary search yourself idx = ceil_index(tail, -1, len-1, arr[i]) tail[idx] = arr[i] end end len end puts get_lis(array[0].split(" ").map(&:to_i).to_a)
JRubyに挑戦２
もとの記事は JRuby - FreeStyleWiki
とりあえずJRuby+Hanami+HerokuでREST APIを動かすところまでできたので記事を書いておく。
REST APIを作ってみる
最初の目的であるREST APIを作る
- HanamiによるAPIの作成手順
ほとんどコレの内容を見て作成した。使用するSQLについてはいろいろ変えている。
作りたいもの
- MySQLのお手本テーブルである employees をJSONで出力するやつ
- テーブル定義は → MySQL Sample Databases
Hanami - ドキュメント
- Hanami | Guides - Command Line: Generators
- ここにアクションやルートテーブルの生成用のコマンドが載っている
新規アプリの追加
> jruby -S bundle exec hanami generate app api
新規Action/Viewの追加
> jruby -S bundle exec hanami generate action api employees#list
これで employees というActionができる。ルートテーブルにもいろいろ追加された。
ここまででできていること
- Hanamiの全体設定としてのアプリのURL（マウント）設定
- config/environment.rb に Api アプリケーションのマウント場所が書いてある
つまり、http://{ホスト名}/api 以下にアプリが配置されるということ
Hanami.configure do mount Api::Application, at: '/api' ...
デフォルトではhtmlを返す設定になっているので、API用に以下を追記する
module Api class Application < Hanami::Application configure do # 以下を追加 default_request_format :json default_response_format :json body_parsers :json ...
- employeesのためのコントローラー
- apps/api/controllers/employees/list.rb に employeesを返すためのModuleができている
これの面白いところはコントローラーがメソッドごとに分割されているところだろう
module Api::Controllers::Employees class List include Api::Action accept:json # 追加 def call(params) end end end
これもメソッドごとに分割されている
module Api::Views::Employees class List include Api::View # 以下を追加 layout false def render "[]" end end end
モデルは単数形になることに注意
> jruby -S bundle exec hanami generate model employee
- 元となる理想のテーブル定義(MySQL)
CREATE TABLE employees ( emp_no INT NOT NULL, -- UNSIGNED AUTO_INCREMENT?? birth_date DATE NOT NULL, first_name VARCHAR(14) NOT NULL, last_name VARCHAR(16) NOT NULL, gender VARCHAR(1) NOT NULL, -- Enumeration of either 'M' or 'F' hire_date DATE NOT NULL, PRIMARY KEY (emp_no) -- Index built automatically on primary-key column -- INDEX (first_name) -- INDEX (last_name) );
- 作成されたmigrationファイルを改変する
- db/migrations/YYYYMMDD000000_create_employees.rb
Hanami::Model.migration do change do create_table :employees do primary_key :emp_no, Integer, null: false column :birth_date, Date, null: false column :first_name, String, null: false, size: 14 column :last_name, String, null: false, size: 16 column :gender, String, null: false, size: 1 column :hire_date, Date, null: false end end end
Hanamiのマイグレーションファイルの書き方は、ここに書いてある
そして、実は生のSQLでも実行できる
Hanami::Model.migration do up do execute %{ INSERT INTO `employees` VALUES (10001,'1953-09-02','Georgi','Facello','M','1986-06-26'), (10002,'1964-06-02','Bezalel','Simmel','F','1985-11-21'), (10003,'1959-12-03','Parto','Bamford','M','1986-08-28'), ... } end end
employeeのDBのテーブルを作成
以下の手順でエラーが出たときは、おそらくWindows/Unix間のパスの問題なので .env.development を見る
DATABASE_URL="jdbc:sqlite:db\\generic_dao_jruby_development.sqlite"
- 開発環境はSQLite3で動く、ゼロから始める場合は以下のコマンドでdbファイルを作成
> jruby -S bundle exec hanami db create
- その後以下のコマンドでSQLを実行
> jruby -S bundle exec hanami db migrate
JSONを返す部分を追記
とりあえず、以下の追記でサーバを再起動すればJSONが出力されるはず
- apps/api/controllers/employees/list.rb
class List include Api::Action accept :json + expose :employees def call(params) + @employees = EmployeeRepository.new.all end end end
- apps/api/views/employees/list.rb
module Api::Views::Employees class List include Api::View layout false def render - "[]" + _raw JSON.dump(employees.map{|employee| employee.to_h }) end end end
hanami-modelについての見解
さて、ここまででサーバが起動できるはず
> jruby -S bundle exec hanami s
http://localhost:2300/employee にアクセスするとJSONが返ってくる*2。
Hanamiのすごいところは、ここまででO/Rをマッピングするコードを書いていないところだ。詳しくはhanami-modelのREADMEを見れば良いと思うが、model/README.md at master · hanami/model · GitHub。これは結構すごいと思う。
つまりはDB側でカラムの更新があり、usersテーブルにbirthdayというカラムを追加したとしても特にmodelの側でコードの変更は無いということだ。
Javaのものと比べるとすると、例えばMyBatisだとmapper.xmlの中にDBのカラムとObjectのフィールド要素をマッピングするファイルが必要になる。例えばHibernateだとクラスのフィールドに対してアノテーションを付けまくる必要がある。
JRubyに挑戦１
もとの記事は JRuby - FreeStyleWiki
JRuby
環境構築
最初はJavaでSpring-bootを使おうとしたけど、連携の面倒さに辟易したのでJRubyを試してみる。
- 他の人にもインストールさせると想定してAtomを使ってみる
結局, Atom v1.19.6でatomic-emacsパッケージをインストールした。
適当にインストーラからインストールすること、バージョン 9.1.13.0
>jruby --version Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8 jruby 9.1.13.0 (2.3.3) 2017-09-06 8e1c115 Java HotSpot(TM) 64-Bit Server VM 25.112-b15 on 1.8.0_112-b15 +jit [mswin32-x86_64]
- Git
> apm install git-plus
ターミナル
bundler, railsコマンドを使いたいので以下を導入
- ここのレビューを参考にした Atomで使えるTerminalをいくつか試してみた
- Atomで使えるTerminalをいくつか試してみた
Atomを導入済みであれば、apmコマンドでパッケージをインストールできるはずなので、そうする。
> apm install platformio-ide-terminal
再起動したら Ctrl+バッククォート というすっごいわかりにくいショートカットで起動する
起動した図、これは結構うれしい
JRuby on Rails
- GettingStarted
GettingStarted · jruby/jruby Wiki · GitHub を見て、まずはRailsを入れる。
> jruby -S gem install rails
実行すると、java版のいろいろなライブラリが入る。ネイティブ（C言語連携してるやつ）のライブラリに関してはjavaで書き直す必要があったのだろう。
終わったらさっそく rails new <プロジェクト名> で作成する
→ 動きませんでした…
Hanami on Jruby
それでは、ということで最近話題のHanamiを動かしてみる
> jruby -S gem install hanami > jruby -S hanami new generic-dao-jruby > cd generic_dao_jruby > jruby -S bundle install > jruby -S bundle exec hanami s
動いた！
Hanamiについての見解
自分がHanamiフレームワークを知ったのは、以下の記事がはてブでバズっていたからです。RubyやJavaでWEB開発をしている人はぜひ見てみてください。
Rubyist Magazine - HanamiはRubyの救世主(メシア)となるか、愚かな星と散るのか
MVCにService層を追加する
WEBシステムを作る際、もはやModel/View/Controllerを分けることは古典的しぐさです。しかしながら、それなりに大きなシステムを作っていくとビジネスロジックが肥大化します。書き方が素人だとModelのコードがぐちゃぐちゃになりバグの温床になります。JavaだとそのへんService層を作るのですが、Railsだとそれがデフォルトでは存在しないのでどうやっていくか自分で考えないといけません。
Qiitaにもそれを行っている記事があります
qiita.com
Hanamiの試みとは？
Hanamiはサービス層をデフォルトで装備したフレームワークです。不勉強で知らなかったのですがこれは ドメイン駆動設計 - Wikipedia 発祥の考え方のようです。
先ほどの文章の中に、Hanamiが解決したい問題が垣間見えます*2
Railsプロジェクトに蔓延した Fat Model 、 Fat Controller 、信用できないテスト、層をまたいで依存したビジネスロジック、 難解で巧妙な Model 同士のやり取り、Rails Mountable Engine を用いた独自ルールや DSL だらけの gem 、 eager loading に頼り切った非効率な SQL 、ロジックまみれの View ……。 メンテナンス性を下げる要因はたくさんあるが、共通して言えることは、複雑な要件に対して簡単すぎる設計をしてしまっていることだ。 しかもこれらのコードの不吉な匂いは、システムをローンチする頃には既に漂い始めている。
Hanamiはこれからも発展していってほしいプロジェクトです。
