Golangでマージソートの問題を解いてみた
前回同様、AOJの問題を解いてみます。 yuki-toida.hatenablog.com
マージソートの問題を解いてみた
問題
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B
自分が書いたコードはこちら
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) var cnt int // マージソート func main() { sc := bufio.NewScanner(os.Stdin) sc.Split(bufio.ScanWords) sc.Scan() n, _ := strconv.Atoi(sc.Text()) A := make([]int, n) for i := 0; i < n; i++ { sc.Scan() A[i], _ = strconv.Atoi(sc.Text()) } sorted := mergeSort(A) fmt.Println(strings.Trim(fmt.Sprint(sorted), "[]")) fmt.Println(cnt) } // Runs mergeSort algorithm on a slice single func mergeSort(slice []int) []int { if len(slice) <= 1 { return slice } mid := len(slice) / 2 left := mergeSort(slice[:mid]) right := mergeSort(slice[mid:]) return merge(left, right) } // Merges left and right slice into newly created slice func merge(left, right []int) []int { size, k, j := len(left)+len(right), 0, 0 tmp := make([]int, size) for i := 0; i < size; i++ { if len(left) <= j { tmp[i] = right[k] k++ } else if len(right) <= k { tmp[i] = left[j] j++ } else if right[k] < left[j] { tmp[i] = right[k] k++ } else { tmp[i] = left[j] j++ } cnt++ } return tmp }
AOJからのフィードバック
これで、まだまだ基本のアルゴリズムっていうのがなかなかハードだなーという印象。
ここまでの間にGolangの基本的な構文や実装方法は結構理解できてきたからもういいかなー。
Golangで挿入ソートの問題を解いてみた
前回同様、AOJの問題を解いてみます。 yuki-toida.hatenablog.com
挿入ソートの問題を解いてみた
問題
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_A
自分が書いたコードはこちら
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) // 挿入ソート func main() { sc := bufio.NewScanner(os.Stdin) sc.Split(bufio.ScanWords) n := nextInt(sc) ary := make([]int, n) for i := 0; i < n; i++ { ary[i] = nextInt(sc) } print(ary) insertionSort(ary, n) } func nextInt(sc *bufio.Scanner) int { sc.Scan() num, _ := strconv.Atoi(sc.Text()) return num } func print(ary []int) { fmt.Printf("%v\n", strings.Trim(fmt.Sprint(ary), "[]")) } func insertionSort(ary []int, n int) { for i := 1; i < n; i++ { v := ary[i] j := i - 1 for 0 <= j && v < ary[j] { ary[j+1] = ary[j] j-- } ary[j+1] = v print(ary) } }
AOJからのフィードバック
難しくなってきたー。
挿入ソートは離れた要素を直接交換することなく、取り出した値vより大きい要素のみを後方に移動するので、安定ソートアルゴリズムです。
挿入ソートの計算量を考える
最悪の場合、各iループがi回発生するので(N2 - N) / 2 となるので、O(N2) となりそうです。
ただデータの並びが、昇順に並んでいると移動の必要が無くN回のみなので、O(N)で済みそうですね。
Golangで文字列変換の問題を解く
前回同様、AOJの問題を解いてみます。 yuki-toida.hatenablog.com
文字列変換の問題をやってみた
問題
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/9/ITP1_9_D
自分が書いたコードはこちら
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) // 文字列変換 func main() { sc := bufio.NewScanner(os.Stdin) sc.Scan() str := sc.Text() sc.Scan() q, _ := strconv.Atoi(sc.Text()) for i := 0; i < q; i++ { sc.Scan() ary := strings.Split(sc.Text(), " ") a, _ := strconv.Atoi(ary[1]) b, _ := strconv.Atoi(ary[2]) switch ary[0] { case "replace": str = str[:a] + ary[3] + str[b+1:] case "reverse": str = str[:a] + reverse(str[a:b+1]) + str[b+1:] case "print": fmt.Printf("%v\n", str[a:b+1]) } } } func reverse(s string) string { runes := []rune(s) for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 { runes[i], runes[j] = runes[j], runes[i] } return string(runes) }
AOJからのフィードバック
Golangのスライスの部分取得が便利だったので抜粋。
str[:] // 0 から len(str)-1 まで str[a:] // a から len(str)-1 まで str[a:b] // a から b-1 まで str[:a] // 0 から aまで
これはとても分かりやすく良いですね、使っていこう。
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しばらく追っかけようかな。
