ハノイの塔を実装する
前提
- 3つの杭を3つの配列(orig, tmp, to)で表現する
- 各配列をスタックとみなし行える操作はpushとpopのみ
- 円盤1つを配列内のintとして表現。大きな円盤は大きな数字で
- 例えば、3段のハノイの塔は
[3,2,1]といった形で表現する
- 例えば、3段のハノイの塔は
目標
- n段のorigをtoに移し替えること
まずは
- 1段のとき、2段のとき、3段のときを考えてその法則性を探る
1段
- orig (1)-> to
orig = [] tmp = [] to = [1]
2段
- orig (1)-> tmp
# 1段と同じ操作をorig -> tmp orig = [2] tmp = [1] to = []
- orig (2)-> to
# 1段と同じ操作 orig = [] tmp = [1] to = [2]
- tmp (1)-> to
# 1段と同じ操作をtmp -> to orig = [] tmp = [] to = [2,1]
3段
- orig (1)-> to
- orig (2)-> tmp
- to (1)-> tmp
# 2段のときと同じ操作を orig -> tmp で実行 orig = [3] tmp = [2,1] to = []
- orig (3)-> to
# 1段のときと同じ操作 orig = [] tmp = [2,1] to = [3]
- tmp (1)-> orig
- tmp (2)-> to
- orig (1)-> to
# 2段目のときと同じ操作を tmp -> to で実行 orig = [] tmp = [] to = [3,2,1]
ちょっと多いけど4段目
- orig (1)-> tmp
- orig (2)-> to
- tmp (1)-> to
- orig (3)-> tmp
- to (1)-> orig
- to (2)-> tmp
- orig (1)-> tmp
# 3段のときと同じ操作を orig -> tmp で実行 orig = [4] tmp = [3,2,1] to = []
- orig (4)-> to
# 1段のときの操作 orig = [] tmp = [3,2,1] to = [4]
- tmp (1)-> to
- tmp (2)-> orig
- to (1)-> tmp
- tmp (3)-> to
- orig (1)-> tmp
- orig (2)-> to
- tmp (1)-> to
# 3段のときと同じ操作を tmp -> to で実行 orig = [] tmp = [] to = [4,3,2,1]
上記の試行から3つの手順に分けられる
N段のハノイの場合
- N-1段をorig->tmpに移動
- 1番下(N段目)をorig->toに移動
- N-1段をtmp->toに移動
手順1と3を再帰的に行うことで
コードにすると(python)
動かした回数を出したい場合は、実際に動かす操作を行なっている箇所、つまりto.appendの前後どちらかでカウントをインクリメントすればよい
def move(n, orig, to, tmp): if n == 0: return # n-1段をorigからtmpに移動する move(n-1, orig, tmp, to, cnt) # n段目をtoに移動する to.append(orig.pop()) # n-1段をtmpからtoに移動する move(n-1, tmp, to, orig, cnt) import sys # 引数でハノイの塔の高さを指定する if len(sys.argv) != 2: exit N = int(sys.argv[1]) # N段の塔、空の塔を配列で擬似的に表す orig = [i for i in range(N, 0, -1)] tmp = [] to = [] # origの塔をtoに動かす move(N, orig, to, tmp)
カウントありのpythonコード
goのチャネルの簡単なまとめ
Goならわかるシステムプログラミングを読んで。
概要
- キュー構造である
- ただしランダムアクセスはできず、投入と取り出しのみ行うことができる
- 並列処理されても正しくデータを受け渡す同期機構である
- goroutine間での情報共有としての利用が推奨されている
- 読み込み・書き込みで準備ができるまでブロックする機能である
- データがない状態で取り出そうとすると、他のgoroutineがデータを投入して読み込みの準備ができるまでブロックして待つ
- バッファに空きがない状態で書き込もうとすると、他のgoroutineがデータを取り出して空きができるまでブロックして待つ
sample
下記スクリプトを実行する。
package main import ( "fmt" "time" ) func main() { fmt.Println("script start") done := make(chan bool) go func() { fmt.Println("start sub()") time.Sleep(2 * time.Second) fmt.Println("sub() is finished") done <- true }() fmt.Println("I'm waiting for tasks to be done") <-done fmt.Println("all tasks are finished") }
main は <-done の箇所で、チャネルであるdoneに何らかのデータが入るのを待っている。
goroutineがdoneにtrueを入れると、all tasks are finishedとなる。
参考
mattnさんのこの記事とても分かりやすいです
ブラウザアクセスでファイルをダウンロードさせる方法
やり方
HTTPレスポンスヘッダーにContent-Disposition: attachmentをセットする。
デフォルトでは、Content-Disposition: inlineとなっており、Webページとして表示される。
ちなみにdispositionの意味は、何かの置き方や配置の仕方、という意味。
The way in which something is placed or arranged, especially in relation to other things
サンプル
例えばgoで書いてみるとこんな感じ。
localhost:8080 にアクセスするとファイルが素敵なお手紙がダウンロードされる。
package main import ( "bytes" "net/http" ) func handler(w http.ResponseWriter, r *http.Request) { w.Header().Set("Content-Type", "text/plain") w.Header().Set("Content-Disposition", "attachment; filename=nekootoko3.txt") var buf bytes.Buffer buf.WriteString("Hello!\n") buf.WriteString("I'm nekootoko3\n") buf.WriteString("I'm happay everyday!\n") buf.WriteString("\n") buf.WriteString("Sincerely Yours\n") buf.WriteString("nekootoko3") txt := buf.Bytes() w.Write(txt) } func main() { http.HandleFunc("/", handler) http.ListenAndServe(":8080", nil) }
参考
depを触ってみたよ
the "official experiment" dependency management tool for the Go languageというdepを触ってみた。
これがgoのライブラリ管理ツールでは公式になっていく模様。
公式ドキュメントを見ながらやってみる。
installation
macの場合、crewで入る。
$ brew install dep $ brew upgrade dep
その他の場合は下記コマンドで良さそう。
アーキテクチャ、OS、GOPATHなんかに応じてインストールしてくれる模様。
$ curl https://raw.githubusercontent.com/golang/dep/master/install.sh | sh
depのコマンドを確認
こんな感じ
bash-3.2$ dep Dep is a tool for managing dependencies for Go projects Usage: "dep [command]" Commands: init Set up a new Go project, or migrate an existing one status Report the status of the project's dependencies ensure Ensure a dependency is safely vendored in the project version Show the dep version information check Check if imports, Gopkg.toml, and Gopkg.lock are in sync Examples: dep init set up a new project dep ensure install the project's dependencies dep ensure -update update the locked versions of all dependencies dep ensure -add github.com/pkg/errors add a dependency to the project Use "dep help [command]" for more information about a command.
使ってみる
今回のサンプルに使うプロジェクトを作ってそこに移動する。
このプロジェクトが他の人やプロジェクトに利用されることを想定している場合には下記の場所に作る。
$ mkdir -p $GOPATH/src/github.com/<あなたの名前>/<プロジェクト名> $ cd $GOPATH/src/github.com/<あなたの名前>/<プロジェクト名>
今回のプロジェクトが他で利用されることはないので、今回はここに作る。
$ mkdir -p $GOPATH/src/<プロジェクト名> $ cd $GOPATH/src/<プロジェクト名>
dep initコマンドを実行し、現在のプロジェクトを解析して初期化する。
$ dep init $ ls Gopkg.lock Gopkg.toml vendor
vendorは空のディレクトリで、今後depで入るパッケージはここに。
Gopkg.toml は、現在のプロジェクトの依存関係を記述してあるファイル。
$ cat Gopkg.toml # Gopkg.toml example # # Refer to https://golang.github.io/dep/docs/Gopkg.toml.html # for detailed Gopkg.toml documentation. # # required = ["github.com/user/thing/cmd/thing"] # ignored = ["github.com/user/project/pkgX", "bitbucket.org/user/project/pkgA/pkgY"] # # [[constraint]] # name = "github.com/user/project" # version = "1.0.0" # # [[constraint]] # name = "github.com/user/project2" # branch = "dev" # source = "github.com/myfork/project2" # # [[override]] # name = "github.com/x/y" # version = "2.4.0" # # [prune] # non-go = false # go-tests = true # unused-packages = true [prune] go-tests = true unused-packages = true
Gopkg.lock は、プロジェクトが依存しているパッケージの依存関係がバージョンなんかも合わせて記載されている？
$ cat Gopkg.lock # This file is autogenerated, do not edit; changes may be undone by the next 'dep ensure'. [solve-meta] analyzer-name = "dep" analyzer-version = 1 input-imports = [] solver-name = "gps-cdcl" solver-version = 1
ここからどんな作業でどんな変化が生まれるをかを知るためgit管理して進める。
試しに、ginでwebサーバーを構築して進める。
プロジェクトのルートディレクトリにapp.goを作る。(ドキュメント丸写し)
package main import "github.com/gin-gonic/gin" func main() { r := gin.Default() r.GET("/ping", func(c *gin.Context) { c.JSON(200, gin.H{ "message": "pong", }) }) r.Run() // listen and serve on 0.0.0.0:8080 }
ここでプロジェクトの依存関係をインストールしてくれるというdep ensureを叩くと、、、
$ dep ensure -v # Gopkg.lock is out of sync with Gopkg.toml and project imports: github.com/gin-gonic/gin: imported or required, but missing from Gopkg.lock's input-imports Root project is "dep_sample" 1 transitively valid internal packages 1 external packages imported from 1 projects (0) ✓ select (root) (1) ? attempt github.com/gin-gonic/gin with 1 pkgs; 22 versions to try (1) try github.com/gin-gonic/gin@v1.2 (1) ✓ select github.com/gin-gonic/gin@v1.2 w/3 pkgs (2) ? attempt github.com/gin-contrib/sse with 1 pkgs; 1 versions to try (2) try github.com/gin-contrib/sse@master ... # Bringing vendor into sync (1/8) Wrote gopkg.in/go-playground/validator.v8@v8.18.2: new project (2/8) Wrote gopkg.in/yaml.v2@v2.2.1: new project (3/8) Wrote github.com/gin-contrib/sse@master: new project (4/8) Wrote github.com/gin-gonic/gin@v1.2: new project (5/8) Wrote github.com/golang/protobuf@v1.1.0: new project (6/8) Wrote github.com/mattn/go-isatty@v0.0.3: new project (7/8) Wrote github.com/ugorji/go@v1.1.1: new project (8/8) Wrote golang.org/x/sys@master: new project
依存関係のあるパッケージをベンダー下にインストールしてきてくれる。
Gopkg.lock にも依存関係がたくさん記述されている。
vendorは重いので、.gitignoreにしておくといいかもしれない。
おわりに
プロジェクトをdep initして、パッケージを追加したらdep ensureする。という方針でなんとなくいいのかな。
Gopkg.tomlについてもちゃんと調べよう。
その他
goまだまだこれからという人はこの記事なんかも読んでみるとよいのかも。
CentOS6にscreen-4.6.2をインストールする
ソースを取ってくる
このサイトから、screen-4.6.2.tar.gzのリンク先をコピーして/usr/local/src/下にダウンロードする。
$ cd /usr/local/src/ $ sudo wget https://ftp.gnu.org/gnu/screen/screen-4.6.2.tar.gz
インストール
まずは解凍
$ sudo tar -zxvf screen-4.6.2.tar.gz
インストール手順書を見てみる
$ cd screen-4.6.2 $ less INSTALL
コピペすると長いので割愛。
手順がいくつかに別れていて、手順0(./autogen.sh の実行。中身は /bin/autoreconf を実行するだけ)は普通やる必要ないみたい。
なので、手順1からやる。./configureの実行。
ただし、そのままやると下記のようなエラーが出る。
$ ./configure ... - select can't count configure: checking for tgetent... configure: checking libcurses... configure: checking libtermcap... configure: checking libtermlib... configure: checking libncursesw... configure: checking libtinfow... configure: checking libncurses... configure: checking libtinfo... configure: error: !!! no tgetent - no screen
どうやらtgetentなる端末制御関連のライブラリがないらしいので入れよう。
$ sudo yum install ncurses-devel
もう一度 ./configureを実行すると、最後に下のようなメッセージが出て Makefile と config.hファイルが作られる。
Now please check the pathnames in the Makefile and in the user configuration section in config.h. Then type 'make' to make screen. Good luck.
sudo makeを実行すると、screenファイルが作られるので任意の場所に置くかシンボリックリンクを貼る。
自分は下のようなやり方で、既存のscreenをoldに変えて、新しくできたscreenにシンボリックリンクを貼った。
$ sudo make $ sudo mv /usr/bin/screen /usr/bin/screen.old $ sudo ln -s /usr/local/src/screen-4.6.2/screen /usr/bin/
以上。
あとは必要に応じて、~/.screenrcを変えてもらうと良いかと。
多分CentOS7でもやり方は同じだと思う。
実践ハイパフォーマンスMySQLメモ
はじめに
- 実践ハイパフォーマンスMySQLを読む中で、知らなかった単語や気になったことのメモ
- この書籍では
5.5について書かれているが、最新は5.7なので異なる点がいくつかあるのだろうと懸念はある。
とはいえ、根本的な仕組みはそうそう変わるものではないだろう。
1章
MySQLの論理アーキテクチャ
- MySQLは3つのレイヤーに分けることができる
- 接続の処理、認証、セキュリティといったネットワークベースのほとんどのクラインアント/サーバーツールで必要となるレイヤー
- 1クライアント1スレッドが割り当てられ、スレッドは1つのコアまたはCPUに関連づけられる
- サーバーはスレッドをキャッシュするので、新たな接続の度にスレッドの作成・削除は不要
- クエリ解析、分析、最適化、キャッシュ、組み込み関数などの中枢ともいえるレイヤー
- クエリのパース・書き換え、テーブル読み取り順序の決定、使用するインデックスの選択など
- ストレージエンジンのレイヤー
- 接続の処理、認証、セキュリティといったネットワークベースのほとんどのクラインアント/サーバーツールで必要となるレイヤー
MVCC(MultiVersionConcurrencyControl)- InnoDBの行ロックで単純な行ロックと異なっている
クラッシュセーフとは
- プロセスやマシンが正常に動作しなくなって再起動した後でも以前の状態に戻って処理を再開できるということ
2章
ベンチマークについて
- 各ベンチマークツールについて、ベンチマークの手法などについての説明
- 知識として持っておくものではなく、実際にベンチマークする時にこの章を手がかりに進めていくのがいいと思う。
- 普段の業務で使わず忘れてしまうので
3章
プロファイルについて
- パフォーマンスを最適化するにあたって必要なことが示されている
- この章も2章同様、その存在や概要を把握しておくに留め、必要になった段階でその詳細に入るとよい
4章
最適なデータ型
- 可能な限り小さいデータ型を選択する
- 例えば選手の背番号とかであれば、int(4バイト)ではなくて、tinyint(1バイト)でいいよね。
- 単純なデータ型を選択する
- 文字列型よりも整数型の比較コストが低い。
- 例えば、IPは整数型に直すのがよい
- 可能であれば
NULLを使用しない- インデックスや値の比較を複雑にするのでできるだけ避けるべき
- とはいえ、意味不明なデフォルト定数を用いるくらいならNULLでいい
- 外部キーになりうる値には同じデータ型を使おう
- IDにはできるだけ整数を使おう。コストを下げる
正規化と非正規化
- テーブルを正規化した結果、インデックスが上手く利用できない場合には非正規化もあり。
- その場合には、参照頻度と更新が煩雑になる手間のトレードオフになるということを認識しよう
5章
プレフィックスインデックスの適切な設定
- 非常に長い文字列にインデックスをつける場合、最初の数文字にインデックスをつけることで記憶域を節約し、パフォーマンスを改善できるかも。
- 下記の方法で最適なプレフィックスの文字数を確認できる
mysql> SELECT COUNT(DISTINCT カラム) / COUNT(*) FROM テーブル;
=> 文字列全体でインデックスを貼ったときの選択性を出す
選択性 - カラム内の個別値の数 (カーディナリティー) をテーブル内のレコード数で割ったもの
=> 結果の値が高ければ高いほどSELECT時に除外できる件数が多くなり望ましい(カラムの値の重複が少ないので、SELECTされる行も少ない)
mysql> SELECT COUNT(DISTINCT LEFT(カラム, 1)) / COUNT(*) AS 1,
-> SELECT COUNT(DISTINCT LEFT(カラム, 2)) / COUNT(*) AS 2,
-> SELECT COUNT(DISTINCT LEFT(カラム, 3)) / COUNT(*) AS 3,
-> SELECT COUNT(DISTINCT LEFT(カラム, 4)) / COUNT(*) AS 4
-> FROM テーブル;
=> 各プレフィックスの文字数ごとの選択性を出して、文字列全体でインデックスを貼った時の値に近しい値が出たところの文字数をプレフィックスにする
複数列のインデックス
- 適切な列の順序でインデックスを設定しよう
- 何が適切かは実際に発行するクエリ、インデックスに設定される各列の値の重複が少ない(カーディナリティが高い)ものを選択しよう
カバリングインデックスとセカンダリインデックス
- 別記事にまとめる
範囲条件について
- WHERE句で範囲条件を指定できる方法は下記のように2つあり、EXPAINのtypeではどちらもrangeになるが、インデックスにおいて違いが存在する
IN()を使ってリストで指定する方法- 1クエリの中に複数用いても、インデックスを使用することができる
- 不等号やBETWEENで範囲を指定する方法
- 1クエリの中に複数使用した場合、インデックスが効かなくなってしまう
- どちらも範囲条件を指定するものではあるが、前者の場合、等値条件を複数指定しているからだと考えられる
選択性は低いが常に検索条件やSELECTで指定されるカラムのインデックス戦略
- インデックスのプレフィックスに
IN()で指定する
まとめ
- 単一行へのルックアップを回避しよう
- テーブルアクセスしての検索?
- ファイルソートを回避しよう
- インデックスのみを使用するアクセスを利用できるようなインデックスとクエリを選択するようにしよう
6章
スロークエリの原因
- アプリケーションが必要以上に多くのデータを取得していないか
- MySQLサーバーが必要以上に多くの行を解析していないか
- 下記3項目を確認
- 応答時間
- 処理時間と待ち時間(I/O処理の完了や行のロックなど)からなるので正確な計測は難しい
- 調査される行と返される行の数
- 調査される行の数とアクセスタイプ
- EXPLAINの記事参照
- 応答時間
- 下記3項目を確認
クエリ再構築
- 1度に処理するのは1000行など、クエリを分割する
- JOINされているクエリを複数クエリに分割する
- ロックの競合が少なくなる可能性がある
- 結合するテーブルのうち、変更頻度が高いものが1つだけの場合など、他のクエリでクエリキャッシュを使えるようになる
クエリがどのように実行されるか
大まかな流れ。強調した部分は下で簡単に補足・解説
- クライアントがSQLステートメントをサーバーに送信
- サーバーがクエリキャッシュをチェック。ヒットしたらキャッシュの結果を返す。なければ3へ
- サーバーがSQLステートメントを
解析し、前処理を行い、最適化してクエリ実行プランを作成 クエリ実行エンジンがストレージエンジンAPIを呼び出し、クエリ実行プランを実行する
クエリ最適化プロセス(括弧内は処理する主体)
- 解析(パーサー)
- 前処理(プリプロセッサ)
- 最適化(クエリオプティマイザ)
- 最もコストの低いクエリ実行プランに変換。ただし、メモリキャッシュ、他クエリの影響などは考慮されない
- 下記のような最適化を行う
- 結合の並び替え
- OUTER JOINからINNER JOINへの変換
- 代数的等値ルールの適用
- 例) (5=5 and a>5) は、a>5 のみに
- COUNT、MAX、MINの最適化
- インデックスを有効活用すればテーブル内の全データをみなくてもよくなる
- 定数式の評価と縮小
- カバリングインデックス
- サブクエリの最適化
- 早期終了
- auto_increment の id に -1 で検索をかけるような不可能な条件などは最適化段階で終了する
第7章
業務で使われている、パーティション、プリペアドステートメント、クエリキャッシュ
パーティション
- (主に)特定カラムの範囲で、物理的にデータを区切る。
- WHERE句でその範囲が除外された時には、オプティマイザはそのテーブルを考慮しない
プリペアドステートメント
流れは下記の通り
プリペアドステートメントが効率がよい可能性がある理由
クエリキャッシュ
- クエリキャッシュとは
- まずSELECT文の完全な結果セットをキャッシュする。
後で全く同じクエリが投げられ、キャッシュされたデータが有効な場合にはクエリの解析・最適化・実行をスキップして、結果をキャッシュ内容から返却できる
- まずSELECT文の完全な結果セットをキャッシュする。
- クエリキャッシュの注意点
- キャッシュヒットの確認
- キャッシュヒット確認時、
クエリの解析、正規化、パラメータ化を行わない。
なので、大文字、小文字、スペース等も全てが一致した場合にのみヒットする - 結果を生成したクエリが決定的でない限りキャッシュされない(CURRENT_DATE()などの関数が入っている場合などはキャッシュされない)
ただし、SELECT時にキャッシュの確認は行われる
- キャッシュヒット確認時、
- クエリキャッシュはいくつかの点でオーバーヘッドになる
- 読み込みクエリは開始する前にキャッシュをチェックしなければならない
- クエリがキャッシュ可能で、まだキャッシュに存在しなければ、結果を生成してから格納する
- 書き込みクエリが変更するテーブルを使用するクエリがあれば、そのキャッシュエントリを無効にしなければならない。
- キャッシュヒットの確認
参考
DockerとかCI試す用のアプリ作ったよ
Dockerで何かアウトプットをしておきたかったのと、
CircleCIを使ってみたかったので簡単な、本当に簡単なアプリケーションを作った。
githubに置いておいた。
使い方はリンク内のINSTALLATION AND LAUNCHを参照のこと。
このアプリケーションでCIを試す
CIについてやCicleCIの登録についてなどは、こちらのブログを見て頂くとよいかと。
github、CircleCIにこのアプリケーションを登録して、CIが機能しているかを確認するにはテストコードの値を変えてみると分かりやすい。
例えばプロジェクト内のcalculator/calculator_test.goを下記のように変更してgithubにpushするとCircleCIから失敗しましたよ、ってメールが来る。
7 func TestAdd(t *testing.T) {
8 tests := []struct {
9 left int
10 right int
11 expected int
12 }{
13 {1, 2, 3},
14 {-1, 2, 1},
15 {0, 0, 0},
+ {1, 1, 20}, // 1 + 1 = 20 を期待するテストになっているので失敗する!!
16 }
17
18 for _, tt := range tests {
19 sum := Add(tt.left, tt.right)
20 if sum != tt.expected {
21 t.Errorf("%d is expected. got=%d", tt.expected, sum)
22 }
23 }
24 }
上記の変更をpushした後、修正した箇所を削除して再びpushするとエラーが修正されたよ、ってメールが来る。
なお、ブランチはmasterのままでも別ブランチを切ってもどちらでもよい。
アプリの見所
エラー時の表示は必見
