AOJ - ALDS1_11_A,B,C (グラフアルゴリズム) を解いてみた
AOJ - ALDS1_11は、グラフアルゴリズムです。
グラフの表現 | アルゴリズムとデータ構造 | Aizu Online Judge
深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge
幅優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge
解くと以下の３つを覚えられるのでとても有用です。
どれももっと早く覚えておけばよかったと悔やまれる非常に使いでのあるアルゴリズムです。これらが解けると、以下のAtCoderの問題も解けます（そのままなので…）
アルゴリズム自体の解説はWikipediaとかヨークカレッジペンシルバニア校の授業用の教科書が良かったです。
あと、最初にコレを見たほうが理解が早そう
ALDS1_11_A (隣接行列)
自分の解答
以下メモ
- N個の頂点があるグラフをN * Nの行列で表すことを隣接行列と言うようだ（頭いい考えだな〜）
- N個の頂点があった場合、そのうち１つのある頂点Aから他の頂点へつながる数はN-1…
- 頂点AからAに対する数も含むような行列になってしまうがそれは気にしない
ALDS1_11_B (深さ優先探索)
アルゴリズム
Wikipediaに疑似コードがあるので、それをそのまま実装すれば良い
function 深さ優先探索(v) v に訪問済みの印を付ける v を処理する for each v に接続している頂点 i do if i が未訪問 then 深さ優先探索(i)
自分の解答
ここでもRubyのStructが活躍しており、
- :u → ノードの番号（１〜）
- :k → ノードから出る辺の本数
- :v → 対向ノードの番号（１〜）
- :visited → 訪問したか否か
ぐらいの意味で使っている
Node = Struct.new(:u, :k, :v, :visited)
lines = $stdin.read array = lines.split("\n") Node = Struct.new(:u, :k, :v, :visited) class Graph attr :nodes, :d, :f def initialize(n) @nodes = Array.new(n){ Node.new } @d = Array.new(n) @f = Array.new(n) end def set_graph_node(u, k, v) @nodes[u-1].u = u @nodes[u-1].k = k @nodes[u-1].v = v @nodes[u-1].visited = false end def dfs(start = 0, count = 1) # puts "visit = #{@nodes[start].to_s}, count = #{count}" @nodes[start].visited = true @d[start] = count count = count + 1 for i in @nodes[start].v count = dfs(i-1, count) unless @nodes[i-1].visited end # puts "visited = #{@nodes[start].to_s}, count = #{count}" @f[start] = count count = count + 1 count end end N = array[0].to_i graph = Graph.new(N) for i in 1...array.length seps = array[i].split(" ") u = seps.drop(0).first.to_i k = seps.drop(1).first.to_i v = seps.drop(2).map(&:to_i) graph.set_graph_node(u, k, v) end start, count = 0, 1 while graph.nodes.any?{|n| n.visited == false} start = graph.nodes.find_index{|n| n.visited == false } count = graph.dfs(start, count) end # puts "d #{graph.d.to_s}" # puts "f #{graph.f.to_s}" 1.upto(N).each do |n| puts "#{n} #{graph.d[n-1]} #{graph.f[n-1]}" end
これはそんなに詰まらなかった。
ALDS1_11_C (幅優先探索)
アルゴリズム
Wikipediaに疑似コードがあるが、これだと問題がある。あるノードからあるノードへの最短距離がわからない。。。すごく悩んだ
function 幅優先探索(v) v に訪問済みの印を付ける v をキューに追加 while キューに要素を含む do v ← キューから取り出す v を処理 for each v に接続している頂点 i do if i が未訪問 then i に訪問済みの印を付ける i をキューに追加
最終的に、アメリカの大学*1が公開していたアルゴリズムの手順をそのまま実装した。
ポイントはノードに到達したかどうか、探索済みかどうかを３色で表すことだ。また、各ノードへの距離はノード自体のクラスに設定する。
BFS(G,s) for each vertex u ∈ G.V - {s} u.color == WHITE u.d = INF u.pi = NIL s.color = GRAY s.d = 0 s.pi = NIL Q = ∅ ENQUEUE(Q,s) while Q ≠ ∅ u = DEQUEUE(Q) for each v ∈ G.Adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v.pi = u ENQUEUE(Q,v) u.color = BLACK
自分の解答
いろいろ試してノードのクラスはこんな感じになった。
Node = Struct.new(:u, :k, :v, :c, :d, :pi)
- :u → ノードの番号（１〜）
- :k → ノードから出る辺の本数
- :v → 対向ノードの番号（１〜）
- :c → 訪問状況を３値（＝３色）で
- :d → ノード間の距離の記録
- :pi → 一つ前に探索したノードの記録
# Queue class Array alias_method :enqueue, :push alias_method :dequeue, :shift end # u : Index of nodes starting from 1...N # k : degree of this node # v : array of vertices connected with this node # c : :white(=undiscovered), :gray(=frontier), :black(finished searching) # d : distance when the vertex is first discovered # pi: predecessor vertex Node = Struct.new(:u, :k, :v, :c, :d, :pi) class Graph attr :nodes, true def initialize(n) @nodes = Array.new(n){ Node.new } end def add_graph_node(u, v) @nodes[u-1].u = u if not v.nil? (@nodes[u-1].v ||= []).push(v) @nodes[u-1].k = @nodes[u-1].v.length ||= 0 else @nodes[u-1].v = [] if @nodes[u-1].v.nil? @nodes[u-1].k = 0 end @nodes[u-1].c = :white @nodes[u-1].d = -1 @nodes[u-1].pi = nil end def reset() @nodes.each do |node| node.c = :white node.d = -1 node.pi = nil end end def dist() puts "d : #{@nodes.map{|node| node.d}.to_a.to_s}" puts "pi: #{@nodes.map{|node| node.pi}.to_a.to_s}" end def bfs(start, queue) start_idx = (start - 1).to_i @nodes[start_idx].c = :gray @nodes[start_idx].d = 0 @nodes[start_idx].pi = nil queue.enqueue(@nodes[start_idx]) while not queue.empty? u = queue.dequeue break if u.v.nil? u.v.each do |label| v = @nodes[label-1] if v.c == :white v.c = :gray v.d = u.d.to_i + 1 v.pi = u queue.enqueue(v) end end u.c = :black end end end # start lines = $stdin.read array = lines.split("\n") N = array[0].to_i graph = Graph.new(N) for i in 1...N+1 seps = array[i].split(" ") u = seps.drop(0)[0].to_i k = seps.drop(1)[0].to_i vs = seps.drop(2).map(&:to_i) #puts "add_graph_node(#{u} <--> #{v})" for v in vs graph.add_graph_node(u, v) end graph.add_graph_node(u, nil) if vs.length == 0 end graph.bfs(1, []) graph.nodes.each_with_index do |elem, idx| puts "#{idx+1} #{graph.nodes[idx].d.to_i}" end
各アルゴリズムをどう使うかなども書きたいのだが、それは後日
mavenで本番用/開発用のwarファイル切り替え
成果物の設定情報切り替え
ユースケース
システム開発を行う際、DBやサーバを本番環境、開発環境（あるいは＋ステージング環境）に用意することは当たり前のことだろう。
上記のようにすることで
- 開発環境で事前にテストすることでバグが発見しやすくなる
- 本番環境のデプロイのノウハウがたまってミスりにくくなる
ここからさらに進めて自動デプロイ環境、いわゆるCIを用意していくのが最近の潮流です。というかそうしないで人の手でやるのは時間がかかるしミスが多い。
mavenで本番用/開発用のwarファイル切り替え
profile
mavenにはビルドの際にオプションとして「-P env」という形式で切り替え用の環境を与えられます。
maven resources plugin
profileごとに使用するプロパティファイルを切り替えるとき Maven Resources Plugin が使えます。
環境ごとの切り替えの実装
プロパティファイルの値の置き換え
- resource タグで指定された場所にあるファイルが、変数の置き換え対象になります
<project> ... <name>jdbc:postgresql://localhost/test</name> ... <build> ... <resources> <resource> <directory>src/main/resources</directory> <filtering>true</filtering> </resource> ... </resources> ... </build> ... </project>
- src/main/resources/config.properties
jdbc.url=${name}
こういう風に設定しておくと、mavenでのビルド後にプロパティファイルの中身が書き換わります。
jdbc.url=jdbc:postgresql://localhost/test
書き換わったファイルが入るのは、ビルド後にクラスファイルが入る target/classes 以下になります。
プロパティの置き換えを「-P env」オプションで行う
以下のサイトの内容の受け売りになりますが
pom.xmlの中身を以下のように設定すると
- 「mvn -P dev compile」
- 「mvn -P prod compile」
- 「mvn -P test compile」
で切り替えられるようになります。
<!-- プロファイル設定 --> <profiles> <profile> <id>dev</id> <activation> <activeByDefault>true</activeByDefault> </activation> <properties> <build.profile.id>dev</build.profile.id> </properties> </profile> <profile> <id>prod</id> <properties> <build.profile.id>prod</build.profile.id> </properties> </profile> <profile> <id>test</id> <properties> <build.profile.id>test</build.profile.id> </properties> </profile> </profiles> <!-- プロパティ値の取得元(dev/prod/testというディレクトリ)を用意しておく --> <filters> <filter>profiles/${build.profile.id}/config.properties</filter> </filters> <!-- プロパティ値の適用先ファイル --> <resources> <resource> <directory>src/main/resources</directory> <filtering>true</filtering> </resource> </resources>
Bitnami版Jenkinsとコンソール出力の自動更新
AWS上で使用するJenkinsにBitnamiが提供しているUbuntuのイメージを使っているのですが
どうもこれが原因でビルド結果の自動更新がうまく動いてなかったらしい。
対象チケット
[JENKINS-25026] Console output stops populating after several seconds - Jenkins JIRA
参考になったコメント
Daniel Beck added a comment - 2015-01-08 23:33
And that's why you don't use some random vendor's preconfigured shit. It's broken.Disable mod_pagespeed (whatever the hell that is) in Apache and things start working.What a waste of time.
訳
あんたらがITベンダーによって設定済みのクソを使わないのはこういうわけだな、こいつは壊れてる。Apacheの中のmod_pagespeed（ちくしょう!）を無効化したらうまく動き出した。なんて時間の無駄だ…
実際の変更手順
- Jenkins 2.73.1 で検証
$ cd /opt/bitnami $ sudo ./ctlscript.sh stop $ sudo vim /opt/bitnami/apache2/conf/pagespeed.conf # Turn on mod_pagespeed. To completely disable mod_pagespeed, you # can set this to "off". - ModPagespeed on + ModPagespeed off $ sudo ./ctlscript.sh start
これでちゃんとコンソール出力が自動更新されるようになった。
