Golangでプロコンの問題を解く 行列編
前回同様、AOJの問題を解いてみます。 yuki-toida.hatenablog.com
行列の問題をやってみた
問題
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/7/ITP1_7_D
自分が書いたコードはこちら
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) // 行列の積 func main() { sc := bufio.NewScanner(os.Stdin) sc.Scan() nml := strings.Split(sc.Text(), " ") n, _ := strconv.Atoi(nml[0]) m, _ := strconv.Atoi(nml[1]) l, _ := strconv.Atoi(nml[2]) A := make([][]string, n) B := make([][]string, m) for i := 0; i < n; i++ { sc.Scan() A[i] = make([]string, m) for j, v := range strings.Split(sc.Text(), " ") { A[i][j] = v } } for i := 0; i < m; i++ { sc.Scan() B[i] = make([]string, l) for j, v := range strings.Split(sc.Text(), " ") { B[i][j] = v } } C := make([][]int64, n) for i := 0; i < n; i++ { C[i] = make([]int64, l) for j := 0; j < l; j++ { for k := 0; k < m; k++ { v1 := parseInt64(A[i][k]) v2 := parseInt64(B[k][j]) C[i][j] += v1 * v2 } } } for _, x := range C { fmt.Printf("%v\n", strings.Trim(fmt.Sprint(x), "[]")) } } func parseInt64(s string) int64 { v, _ := strconv.ParseInt(s, 10, 64) return v }
AOJからのフィードバック
最後の配列を出力する際に、Cとxの入れ子にするのではなく、fmtパッケージ使うと少し実行時間とメモリの省力化に繋がりました。
ただ[]の見た目がかなりイケてないのでプロダクションで使うなら util パッケージに押し込めるのがいいかもですね。
for _, x := range C { fmt.Printf("%v\n", strings.Trim(fmt.Sprint(x), "[]")) }
Golangでアルゴリズムを学ぶ
Aizu Online Judge を使って、プログラミングコンテストの過去問やアルゴリズムの問題をGolangで解いてみようと思います。
今までプロコンに出場したこともないし、アルゴリズムをしっかり勉強したことも無いので、Golangを覚えがてら一緒に学習してしまおうというのが動機です。
AOJ(Aizu Online Judge)とは
AOJはオンラインジャッジシステムのひとつです。会津大学が運営を行っています。
ICPCやパソコン甲子園などで過去に出題された問題が掲載されている様子。
ユーザーは問題文に書かれている仕様や制限(CPU時間やメモリ使用量)を満たすプログラムを作成します。それをAOJのWebサイトからPOSTすると、仕様に基づいた入力に対して正しい出力を行っているか を自動で判定し即座にフィードバックしてくれます。
組み合わせの問題をやってみた
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/7/ITP1_7_B
問題
1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。
例えば、1 から 5 までの数から３つを選んでそれらの合計が 9 となる組み合わせは、
1 + 3 + 5 = 9
2 + 3 + 4 = 9
の２通りがあります。
Input
複数のデータセットが入力として与えられます。各データセットでは、空白で区切られた n、x が 1 行に与えられます。
n、x がともに 0 のとき入力の終わりとします。
Output
各データセットについて、組み合わせの数を１行に出力して下さい。
↑ こんな感じで出題されるので、Golangでプログラミングしてその結果をサイトからPOSTする感じです。 課題を与えられそれを解くという学生の本分を思い出し、やる気湧いてきちゃいますね。
自分が書いたコードはこちら
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) // 組み合わせの数 func main() { sc := bufio.NewScanner(os.Stdin) for { sc.Scan() ary := strings.Split(sc.Text(), " ") n, _ := strconv.Atoi(ary[0]) x, _ := strconv.Atoi(ary[1]) if n == 0 && x == 0 { break } cnt := 0 for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { if j <= i { continue } for k := 1; k <= n; k++ { if k <= i || k <= j { continue } else if i+j+k == x { cnt++ } } } } fmt.Println(cnt) } }
AOJからのフィードバック
こんな感じです。
コンパイル後、複数のテストケースを走らせてるようですね、CPU時間やメモリ量などもみれて良き良き。
しばらくAOJから問題を抜粋してGolang使って問題解いていこうと思っています。
Docker の multi-stage builds 試してみた
multi-stage buildsとは
まずはドキュメントから。
Use multi-stage builds | Docker Documentation
multi-stage buildsとは、アプリケーションのビルド環境と実行環境を分けることが出来る機能 っぽいです。
これは最高ですね。
今開発しているElixirアプリケーションのDockerfileでは、Elixirのビルド環境で使用したソースや、依存ライブラリを最後に削除しております。
こういう使い方してるところ多いんじゃないかなと思いますが、すべてはコンテナイメージを軽量化するためですね、以下例。
FROM elixir:1.6-alpine
-- 省略 --
# Install
RUN apk update && \
apk upgrade && \
apk add bash && \
apk --no-cache add imagemagick && \
apk --no-cache add --virtual build-dependencies build-base musl-dev && \
mix local.hex --force && \
mix local.rebar --force
-- 省略 --
# Delete
RUN apk del --purge build-dependencies && \
rm -f opt/app/.mix && \
cp ${TARBALL} ${APP}.tar.gz && \
ls | grep -v ${APP}.tar.gz | xargs rm -r && \
tar xfz ${APP}.tar.gz && \
rm -f ${APP}.tar.gz
Golangで試す
前回Golangで作ったmp4連結アプリのDockerfileをmulti-stage builds で書いてみます。
FROM golang:latest as builder
WORKDIR /go/src/github.com/yuki-toida/video-concater/
COPY . .
RUN go get -u github.com/golang/dep/cmd/dep && \
dep ensure -v && \
CGO_ENABLED=0 GOOS=linux ENV=dev go build -o app .
FROM alpine:latest
EXPOSE 8080
ENV ENV=dev \
GOOGLE_APPLICATION_CREDENTIALS="./cred/gcs.json"
RUN apk update && \
apk upgrade && \
apk add --no-cache ca-certificates && \
apk add --no-cache ffmpeg
WORKDIR /opt/app
COPY --from=builder /go/src/github.com/yuki-toida/video-concater/app .
COPY --from=builder /go/src/github.com/yuki-toida/video-concater/index.html .
COPY --from=builder /go/src/github.com/yuki-toida/video-concater/config ./config
COPY --from=builder /go/src/github.com/yuki-toida/video-concater/cred ./cred
CMD ["./app"]
いいですね。
最初のfromがビルド環境、次のfromが実行環境。
見ての通りビルド環境のイメージはgolang:latestで、実行環境のイメージはalpine:latestになってます。
実行環境ではビルド環境でビルドされた実行ファイルをCOPYしてるだけのシンプルな構成です。
まとめ
おそらく今後は基本 multi-stage builds 使うんじゃないかなというくらい良いですね。
ビルドとランタイムでは担っている責務が大きく違うので、見通しがよいmulti-stage buildsを使うのが自然ですね。
GolangでMP4を連結するWebアプリ作ってみた
Golangを書いてみたかったので、仕事上必要そうなmp4を連結するアプリを実装してみました。
※ 勉強がてら作ったものなので、グローバルにホストしたコンテナは削除してしまいました。
アプリケーション概要
フロントエンドはVue.js(SPA)、バックエンドはGolang、WAFはGin使いました。
ffmpegに依存しています、事前にインストール必要です。
実際のUIですが、mp4ファイルを順番に input に追加していくだけです。
以下UIのキャプチャです。
サーバーサイドの処理
- Formから取り出したファイルをテキストファイルに書き込みリスト化
- リストを ffmpeg の concat コマンドに突っ込む
- 連結された mp4 ファイルを Cloud Storage にアップロード
err = exec.Command("ffmpeg", "-f", "concat", "-i", inputText, "-c", "copy", mp4).Run() if err != nil { panic(err) }
って感じです。
GCPのクライアントを使いたかったので、GCSにアップロードしてみました。
ファイル名は xid 使って難読化しています。
最終的なソースコードはこちら
github.com
Golang良き良き
Golangいいですね、すごく手に馴染む。
スターティングGo言語 Kindle版 で勉強しました。
覚える構文も少ないし学習コスト低いなーと。
vscode で書いてみたんですが、golint や gofmt 等の開発ツールがとても優秀で生産性高く開発できそうです。
ただ、ちょっとコード量が大きくなるのがいただけない気もしますね。
大規模アプリのバックエンドを新規でつくってみたいなー。
Golangしばらく追っかけようかな。
ElixirライブラリをHexに公開してみた⑥ Chatwork編
Elixirのライブラリ公開シリーズ第6弾
ドキュメント
必要な部分だけ実装。
何も問題なし。
ソースコード
公開
#!/bin/sh ENV=dev # get dependencies MIX_ENV=$ENV mix deps.get # build MIX_ENV=$ENV mix compile # publish hex MIX_ENV=$ENV mix hex.publish
無事Hexに公開されました。
ElixirライブラリをHexに公開してみた④ Instagram Login編
Elixirのライブラリ公開シリーズ第4弾
ドキュメント
Instagram Developer Documentation
今後大幅にAPIに変更が入る模様。
実装するタイミングミスったかもしれない。
ソースコード
公開
#!/bin/sh ENV=dev # get dependencies MIX_ENV=$ENV mix deps.get # build MIX_ENV=$ENV mix compile # publish hex MIX_ENV=$ENV mix hex.publish
無事Hexに公開されました。
