【WEB+DB PRESS Vol.99】k8sの記事での利用コマンド
概要
WEB+DB PRESS Vol.99 の記事を参考にk8sを利用してみました。
詳しい内容は、記事をご参照いただければと思います。(非常にわかりやすい記事でした)
下記は、記事に書いてあるコマンドのままですが、メモ書き程度に思っていただければ。
コマンド
gcloud側の設定
# project の設定 % gcloud config set project xxxx # ゾーンの設定 % gcloud config set compute/zone asia-northeast1-a # 認証設定 % gcloud auth login
コンテナクラスタ起動
# クラスタ起動 % gcloud container clusters create one \ --cluster-version=1.6.7 \ --machine-type=g1-small Creating cluster one...done. Created [https://container.googleapis.com/v1/projects/xxxxx/zones/asia-northeast1-a/clusters/one]. kubeconfig entry generated for one. NAME ZONE MASTER_VERSION MASTER_IP MACHINE_TYPE NODE_VERSION NUM_NODES STATUS one asia-northeast1-a 1.6.7 35.190.233.232 g1-small 1.6.7 3 RUNNING
GCRにイメージをbuildしてpush
# Container build file % cat manifest/cloudbuild.yaml env: ['PROJECT_ROOT=one'] args: ['build', '-o', 'goneup'] - name: 'gcr.io/cloud-builders/docker' env: ['PROJECT_ROOT=one'] args: ['build', '--tag=asia.gcr.io/$PROJECT_ID/one/goneup', '.'] images: ['asia.gcr.io/$PROJECT_ID/one/goneup']% # push gcr % gcloud container builds submit --config=manifest/cloudbuild.yaml .
kubernetes利用
Pod単独
% cat manifest/pod.yaml apiVersion: v1 kind: Pod metadata: name: goneup spec: containers: - image: asia.gcr.io/[project]/one/goneup:latest imagePullPolicy: Always name: goneup # create pod % kubectl create -f manifest/pod.yaml # port forward % kubectl port-forward [pod name] [local port]:[external port]
ReplicaSet
apiVersion: extensions/v1beta1 kind: ReplicaSet metadata: name: goneup spec: replicas: 3 template: metadata: labels: name: goneup spec: containers: - image: asia.gcr.io/[project]/one/goneup:latest imagePullPolicy: Always name: goneup # create replicaset % kubectl create -f manifest/replicaset.yaml # check replicasets % kubectl get replicasets NAME DESIRED CURRENT READY AGE goneup-1100937273 2 2 2 57s # replace replicaset % kubectl replace -f manifest/replicaset.yaml
Deployment
% cat manifest/deployment.yaml apiVersion: apps/v1beta1 kind: Deployment metadata: name: goneup spec: replicas: 3 template: metadata: labels: name: goneup spec: containers: - image: asia.gcr.io/[project]/one/goneup:latest imagePullPolicy: Always name: goneup # create deployment % kubectl create -f manifest/deployment.yaml # check deployment % kubectl get deployment NAME DESIRED CURRENT UP-TO-DATE AVAILABLE AGE goneup 2 2 2 2 50s
Service
% cat manifest/service.yaml apiVersion: v1 kind: Service metadata: name: goneup spec: type: LoadBalancer selector: name: goneup ports: - port: 8080 # create service % kubectl create -f manifest/service.yaml
Ingress
% cat manifest/ingress.yaml apiVersion: extensions/v1beta1 kind: Ingress metadata: name: goneup spec: rules: - http: paths: - path: /* backend: serviceName: goneup servicePort: 8080 # create ingress % kubectl create -f manifest/ingress.yaml
まとめ
各マニフェストファイルを作成することで、簡単にGCP上にk8sを構築できました。
また情報にアクセスしたい際は、kubectl get xxx
で簡単にアクセスできるところが非常にいいなと感じました。
基本的な設定しか入れていないので、利用してみてもっと詳細な設定まで使いこなせると良いかと思います。
Dockerについて
概要
Dockerについて、本当に簡単な部分だけまとめてみました。
(ここから、Docker->ECS->k8s->GKEと進めていければなぁと思っています。)
Dockerとは
Software Container Platform
=コンテナが動作するプラットフォーム
Containerとは
- 一つSoftwareが実行されるために必要なすべてをパッケージングしたもの
- Softwareを動かすために必要なライブラリと設定のみが入っている
- Container内で、独自にリソースを持つ(メモリ/プロセス/ネットワーク)
どういった問題を解決するのか
「自分のローカルに環境で動いたけど、検証サーバーに載せると動かない..」
→ こういった、環境差分
を解決することができる
Containerにくるむことで、どこでも同じように安全に動作することが保証されます。 そのため、Containerにくるんでおけば安心して、検証、本番環境へとSoftwareをリリースすることができます。
Container(= Docker Container)の作り方
Dockerfileを書きましょう。
Dockerfileとは
- Docker Containerの設計が書かれたファイル
- Dockerfile` というファイル名で作成する
- 記述はDockerfile用DSL
- Dockerエンジン + Dockerfile + ソースファイル があればどの環境でも同じように実行可能
Docker image
- Dockerfileに記述されたOSやアプリケーションコード等をまとめたテンプレート
- Containerはimageを実体化したもの
- Dockerfileをbuildすることで作成することができる
- Dockerエンジン + Docker image があればどの環境でも同じように実行可能
- imageを作成して、Docker Hub等のコンテナ管理サービスにpushしておく
- Docker Hub等からimageをpullしてくるだけで実行可能に
Docker Containerの生成手順
- Dockerfile記述
- BuildしてDocker imageの作成
- imageをもとにRunしてContainerの起動
例: Go Appの実行
下記のようなGolangのHello WorldのコードをContainer内で実行してみます。
package main import "fmt" func main() { fmt.Println("Hello World!") }
\1. Dockerfile記述
下記のようなDockerfileを作成します。(詳細はコメント参照)
# ベースイメージの指定 # Docker Hub(https://hub.docker.com/)上に様々なイメージが公開されている # そちらから利用したいベースイメージを選択 FROM golang:1.8.3-alpine3.6 # 作業を行うディレクトリを選択 WORKDIR /go/src # コマンドを実行 # golangイメージは Alpine Linuxをもとに作成(軽量のためDockerでよく利用される) # linuxコマンド(ls,mkdir)等が実行可能 RUN mkdir hello # 作業を行うディレクトリを変更 WORKDIR /go/src/hello # 作業ディレクトリからコンテナ内にファイルをコピー # COPY [ホスト側] [コンテナ内] COPY . . # Go Appをbuild RUN go build -o hello main.go # コンテナ起動時に実行されるコマンド CMD ["/go/src/hello/hello"]
\2. BuildしてDocker imageの作成
% ls Dockerfile main.go # imageの作成 # (-t でタグを設定できる) % docker build -t hello:1.0 ./ # imageの確認 % docker images REPOSITORY TAG IMAGE ID CREATED SIZE hello 1.0 df9a562be589 10 minutes ago 259MB
\3. imageをもとにRunしてContainerの起動
# コンテナの実行
% docker run hello:1.0
Hello World
まとめ
docker-composeやswam等は別途まとめようかなと思います。 また、詳細なDockerfileのDSLや、docker build/runオプションについてもまとめられたら良いですね。
参考
エンジニアとして学びたいこと(歴2年目)
概要
エンジニアとして、どのあたりを学んでいこうかなぁとの備忘録
項目
Golang
最近ずっと利用しているメイン言語です。仕事上ではJavaを利用することが多いですが、 書いている時間も量もそろそろ超えてくるのではと思っています。
好きなところはこんな感じです。
- ビルドしたバイナリがあればどの環境でも動かしやすい点
- 型あり
- Httpサーバーの起動しやすさ
- プログラマーならたぶん誰でも読める
- ドキュメントが読みやすい
学びたいこと
- パッケージの構成方法
- 自由に書けてしまってどこに何を書くかが明確になっていない
- パッケージの切り方
- 各ファイル内のinterface,strcut,methodの構成
- 周辺ツールの利用方法
- ツールが充実しているのことで、きっちり使い方を抑えたい(pprofとか)
- 実務上でのコードレベル
- OSSのライブラリ等を読んでみる等ですかね
- 体系的な知識
- Webでの情報がメインのため、体系的な知識が身についてない疑惑
- 書籍でまとまったものがあれば一度読むのも良いかも
次のステップ
- 標準ライブラリ読む
- OSS読む
- 本をよむ
- 実務での利用
- 布教
クラウド
実務できっちり利用できていない分、プライベートで学んでおかないと遅れが目立ってしまう印象です。
学びたいこと
次のステップ
- GAEにGoサービスを載せてみる
- WEB+DB PRESS Vol.99を読む
低レイヤー
Goならわかるシステムプログラミングを読んでいて感じましたが、低レイヤーの知識が圧倒的に足りないと感じます。このあたりのコンピュータサイエンスについて、きっちり抑えておきたいです。
低レイヤー周りを最適化したコードを実装できるように、理解を深めたいです。
学びたいこと
次のステップ
- Web記事を読む
- 書籍を読む
まとめ
ざっくりと思い当たることについて、並べて書いてみました。自分の整理にはなったかなとは思います。
学ぶのに良い情報をお持ちの方がいたら、ぜひ教えていただけると幸いです。
まだまだ、手を動かしてコードを書く経験値が足りなさすぎるので、手はとにかく日々動かし続けていきたいとは思っています。
GoSNS
概要
AmazonSNS likeな、簡易メッセージングサーバーを練習がてら書いてみました。
(Amazon SNSちゃんと使ったことないので、ぜんぜん違うかもしれないですが…)
モデルは、Pub/Subを意識しています。
機能概要
- Channel登録
- Channelに対して購読登録
- 購読手段はSlackのWebHook一択(Mail等の対応も検討中)
- 新規Channelの開設
- Handshakeリクエスト
簡易API Doc一覧
メルカリ製のgo-httpdocを利用してドキュメント生成しました。
I/F
基本POSTリクエストでサーバーとやり取りをします。
POSTのBodyに下記のRequest構造のJSON
を書き込んでリクエストします。
Channel登録 (/meta/channel)
新規に開設したい、Channelを登録します。
Request
名前 | 型 | 概要 |
---|---|---|
channel | String | 登録したいchannel名 |
サンプル
{ "channel": "golang" }
Response
JSON構造
名前 | 型 | 概要 |
---|---|---|
channel | String | 登録したchannel名 |
successful | String | 登録成否 |
error (optional) |
String | エラー |
購読登録 (/meta/subscribe)
購読の登録をします。
現在は、Slack通知(WebHook URL)を用いての手法にのみ対応しております。
Request
名前 | 型 | 概要 |
---|---|---|
channel | String | /meta/subscribe |
client_id | String | ID(現在は適当な文字列) |
subscriptions | Array(String) | 購読したいchannelのリスト |
method | Method | 購読手法 |
Method
名前 | 型 | 概要 |
---|---|---|
method | String | 購読手段(下記選択) - slack |
webhook_url | String | Slack WebHookURL (slack選択時必須) |
サンプル
{ "channel": "/meta/subscribe", "client_id": "MRAjWwhTHcgagka", "subscription" : [ "/golang" ], "method" : { "format": "slack", "webhook_url": "https://hooks.slack.com/services/XXX" } }
Response
JSON構造
名前 | 型 | 概要 |
---|---|---|
channel | String | /meta/subscribe |
successful | String | 購読成否 |
client_id | String | ID |
subscriptions | Array(String) | 購読したchannelのリスト |
error (optional) |
String | エラー |
Topic登録 (/topic)
Channelに対して、Topicを登録します。
Request
名前 | 型 | 概要 |
---|---|---|
channel | String | Topic登録するchannel名 |
data | String | Topic内容 |
{ "channel": "/golang", "data" : "*Update GAE Go1.8*" }
Response
文字列
文字列 | |
---|---|
成功 | ok |
失敗 | not found channel |
内部実装
どのように実装をしているか、メモ書き程度に残しておきます。
Pub/Sub Model
PublisherとSubscriberの関係は、1Topicに限ると1対多の関係です。
PublisherはどのSubscriberに送信するかといった情報には関与しません。
Publisherはtopicを送るだけ、Subscriberは送られたTopicを購読するだけといった構成です。
データ保持
購読データの保持は、JSONファイル
にて行っております。
(DB等の利用がベタ-かと思いましたが、ファイルが一番楽だったので選びました)
ファイルI/Oを呼び出しごとに発生させたくなかったため、内部でキャッシュを持たせています。 キャッシュとファイルは常に同期している想定です。
ただ、キャッシュから時間でデータが破棄されることもあり、キャッシュにない場合はファイルを見にいくようにしてます。
ユーザー認証
完全に未実装です。認証なくPOSTが送れたら自由にデータの書き換えができます。
テスト
go-httpdoc に記法にならって記述しています。
API I/Fの部分以外で書けていないところは、順次書き足したいです。
パッケージ管理
depを利用しています。 管理ファイルがtomlファイルになってて驚きましたが、問題なく使えています。
利用しているライブラリ一覧
- API Documet作成用 github.com
- 購読情報のキャッシュ github.com
- パッケージ管理 github.com
感想
Goを触り始めて、初めてある程度ましな成果物を作成しました。
AmazonSNSのドキュメントを読んで、メッセージングサーバーの面白さを感じ、とりあえず自分でも作ってみたといった感じです。
書いてて感じたことですが、パッケージ構成の方法
がよくわからなかったです。
パッケージの切り方や、同一パッケージ内でのファイル分割の方法等で、いまいち方針がなく何度も再構成しました。
他の方のソースを読んで、このあたりは勉強していこうかなと思います。
総じて、楽しく書けたのでGoはかなり自分にあっている気がします。
sync.Poolの挙動について(Golang)
概要
標準パッケージのsync.Pool
を利用して、ファイルの中身を常にメモリ上(=キャッシュ)におきたかったのですが、動作が不定のためうまく利用できなかった話です。
Go version
% go version go version go1.8.1 darwin/amd64
sync.Pool概要
概要としては、以下の認識です
- オブジェクトを一時的に、保持するための機能
- 再利用されるオブジェクトをキャッシュする利用法
- 複数のgoroutineで安全に利用可能
- copy禁止(
noCopy
structが埋め込まれている)
メソッド
Get
func (p *Pool) Get() interface{}
- Poolよりitemを取り出す
- 取り出されたitemはPoolから削除
- Putで入れた値とGetで取り出す値の関係を考慮すべきでない
Put
func (p *Pool) Put(x interface{})
- Poolに値を追加する
動作確認
下記のコードを利用して、Getした際とPutした際の挙動を確認してみました。
https://github.com/midorigreen/gopool/blob/master/main.go
package main import ( "fmt" "net/http" "sync" ) var pool = sync.Pool{ New: func() interface{} { return "init" }, } func main() { mux := http.NewServeMux() mux.HandleFunc("/pool", poolHandler) mux.HandleFunc("/pool/change", poolChangeHandler) http.ListenAndServe(":8888", mux) } func poolHandler(w http.ResponseWriter, r *http.Request) { fmt.Println("----------------------------------") fmt.Println("/pool") fmt.Println(get().(string)) fmt.Println("----------------------------------") } func poolChangeHandler(w http.ResponseWriter, r *http.Request) { fmt.Println("----------------------------------") s := get().(string) fmt.Println("/pool/change") pool.Put(s) fmt.Println("-- changed --") fmt.Println("----------------------------------") } func get() interface{} { s := pool.Get().(string) cpS := s // Getした値を再度Poolに戻している pool.Put(s) return cpS }
出力例
実際の出力例です。
上記コードより、get()
で呼び出した際は、Get→Put
としているため
同じ値がGet()
で取得されて欲しいところです。
ですが、一度/pool/change
APIを叩いた後も"init"が出力されていることから、
Get→Put
で値を戻したところで、必ず同じ値をGet()
してくれるわけではなさそうです。
---------------------------------- /pool init ---------------------------------- ---------------------------------- /pool/change -- changed -- ---------------------------------- # ↓ これ以降はすべて "change handler" が出力されていて欲しい ---------------------------------- /pool change handler ---------------------------------- ---------------------------------- /pool init ---------------------------------- ---------------------------------- /pool change handler ---------------------------------- ---------------------------------- /pool init ---------------------------------- ---------------------------------- /pool change handler ---------------------------------- ---------------------------------- /pool init ---------------------------------- ---------------------------------- /pool change handler ---------------------------------- ---------------------------------- /pool change handler ---------------------------------- ---------------------------------- /pool init ----------------------------------
感想
Callers should not assume any relation between values passed to Put and the values returned by Get. → Putで入れた値とGetで取り出す値の関係を考慮すべきでない
とあるように、Put()
で入れたからGet()
で必ず入れた値が取得できるわけではないことを念頭に置いて開発しないといけないようです。
ファイルの中身をキャッシュしておいて、書き換え時は更新等を行いたかったのですが、
更新をしたデータをPut()
で突っ込んでも返ってくるとは限らなくなってます。
結論、あまり良い使い方ではなさそうです。(一意にキャッシュを保てないので、実データと差分がでてしまうため)
補足
@nobonoboさんにも指摘頂きました。
Get処理でGet&Putしてるわけですね。Poolは内部にもつデータのどれをGetで返すのかは不定です。Put多数->Get多数と、Get&Putを繰り返す場合の挙動は異なるのでご注意を。
— nobonobo🐦 (@nobonobo) 2017年6月25日
参考
Bayeux プロトコルの仕様について
はじめに
Pub/Sub Messaging
を勉強するにあたって、Bayeuxプロトコルでの実装があるとのことだったので、Bayeux プロトコル日本語訳を読んでメモを取ってみました。
枯れた仕様(検索であまり当たらない)な気もしていますが、せっかく読んだので公開しようかと思います。
Bayeuxプロトコル概要
- Webサーバー間でメッセージを非同期にやりとりするためのプロトコル
- メッセージは名前付きチャネルを経て、ルーティング及び送達される
- サーバ <=> クライアント
- ajaxを利用したサーバープッシュ型のテクニック=「comet」
- 準拠要求
- 全てのMUST及びREQUIREDを満たし、かつ、全てのSHOULDを満たすものは、"完全準拠(unconditionally compliant)"
- 1つでもSHOULDを満たさないモノは「条件付き準拠(conditionally compliant)」
- ワード定義
HTTPプロトコル
- リクエスト/レスポンス型のプロトコル
- クライアント -> サーバー
- サーバー -> クライアント
- ステータスライン
- プロトコルバージョン
- 基本的にサーバー -> クライアントへはクライアントの要求なしに通信を走らせない
- Bayeuxでは、双方向の非同期通信を走らせるためサーバー・クライアント間で複数コネクションをサポートしている
- 通常アクセス用コネクション
- ロングポーリング用コネクション
- (MUST NOT)Bayeuxプロトコルも、サーバーが全てのアプリケーションに対して処理を行うために3本以上のコネクションをはらない
様々なルール
- (MUST) クライアントはブラウザのシングルオンポリシーを尊守しなければならない
- シングルオンポリシー = JSからはそれがダウンロードされたサーバー以外への接続は許可されない
- 2コネクション処理
- (MUST) Bayeux実装はHTTPのパイプライン処理を制御し、リクエスト順を保持して実行しなければならない
- ポーリング
- レスポンスを受け取った後、メッセージをサーバーに対して送信する
- 次のメッセージを受け取れるようにする処理
- Bayeux実装は、ロングポーリングと呼ばれる形式のポーリングをサポートする必要がある
- レスポンスを受け取った後、メッセージをサーバーに対して送信する
- 接続ネゴシエーション
- 接続の際、コネクション/認証/を交換して合意するネゴシエーションが行われる
- その際、ハンドシェークメッセージがかわされる
- クライアントの状態
-------------++------------+-------------+----------- +------------ State/Event || handshake | Timeout | Successful | Disconnect || request | | connect | request || sent | | response | sent -------------++------------+-------------+----------- +------------ UNCONNECTED || CONNECTING | UNCONNECTED | | CONNECTING || | UNCONNECTED | CONNECTED | UNCONNECTED CONNECTED || | UNCONNECTED | | UNCONNECTED -------------++------------+-------------+------------+------------
// BNF記法 alpha = lowalpha | upalpha lowalpha = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" upalpha = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" alphanum = alpha | digit mark = "-" | "_" | "!" | "~" | "(" | ")" | "$" | "@" string = *( alphanum | mark | " " | "/" | "*" | "." ) token = ( alphanum | mark ) *( alphanum | mark ) integer = digit *( digit )
- チャネル
channel_name = "/" channel_segments channel_segments = channel_segment *( "/" channel_segment ) channel_segment = token
メッセージフィールド定義
名 | 説明 |
---|---|
channel | - メッセージの配送先および配送元を示す - リクエスト: 配送先 - レスポンス: 配送元 |
supportedConnectionTypes | - /meta/handshake へ送受信の際に利用 - どの転送タイプを用いるか決める - (MUST) long-polling,callback-polling等が存在 |
clientId | - クライアントをユニークに識別するもの - /meta/handshake ,投稿メッセージ以外の全てのメッセージに付与が必須 |
id | 全てのメッセージに付与可能 |
timestamp | - ISO 8601形式(YYYY-MM-DDThh:mm:ss.ss ) - GMTで表記 |
successful | -リクエストの成否 - /meta/* 系のレスポンスに必須 |
error | エラー |
メタメッセージ定義
handshake
クライアントは、/meta/handshake
channelに対してメッセージを送ることで接続ネゴシエーションを開始する
handshake request (MUST field)
field | 説明 |
---|---|
channel | /meta/handshake という値 |
version | クライアントで処理されるバージョン |
supportedConnectionTypes | 接続タイプの文字列 |
handshake response
field | 説明 |
---|---|
channel | /meta/handshake という値 |
version | クライアントで処理されるバージョン |
supportedConnectionTypes | クライアント・サーバー共にサポートする接続タイプ |
clientId | クライアント固有のID |
successful | true/false |
connect
クライアントは、/meta/connection
channelにメッセージを送ることでコネクションを開始する。
connection request
field | 説明 |
---|---|
channel | /meta/connection という値 |
clientId | クライアント固有のID |
connectionType | 接続タイプ |
connection response
field | 説明 |
---|---|
channel | /meta/connection という値 |
successful | true/false |
clientId | クライアント固有のID |
subscribe
チャネルへの登録を行うために、/meta/subscribe
にリクエストを行い、配信登録を行う。
subscribe request
field | 説明 |
---|---|
channel | /meta/subscribe という値 |
clientId | クライアント固有のID |
subscription | 購読するチェネル名/チャネルパターン/配列 |
subscribe response
field | 説明 |
---|---|
channel | /meta/subscribe という値 |
successful | true/false |
clientId | クライアント固有のID |
subscription | 購読するチェネル名/チャネルパターン/配列 |
イベントメッセージ定義
イベントメッセージ投稿
channelに対して、イベントを投稿する処理のこと
publish request
field | 説明 |
---|---|
channel | 投稿するchannel名 |
data | JSONオブジェクトの形をしたメッセージ |
publish response
field | 説明 |
---|---|
channel | 投稿したchannel名 |
successful | true/false |
イベントメッセージ配信
channelからクライアントへイベントを配信する
field | 説明 |
---|---|
channel | 投稿するchannel名 |
data | JSONオブジェクトの形をしたメッセージ |
ポーリング
long-polling
特徴
- 配送すべきメッセージが届くまでコネクションをオープンにし続ける
- 伝送遅延を最小化
- フェールセーフとして、classicalな数秒ごとのポーリング処理を行う
- POSTメッセージのボディで伝送される
- 形式
application/x-www-form-urlencoded
text/json
参考
GolangのSort処理について
GolangのSort処理
GolangのSort処理について、まとめました。
(// package sort
と記載があるサンプルコードは、Golang本体のソースコードです)
Sort
Sort Interface
Golangでは、struct
のソートを行うため、sort.Interface
を実装する必要があります。
(実際はGo1.8以降、下記の sort.Slice()
を利用して、ソートすることができるようになりました。参考)
// sort.Interface type Interface interface { // Len is the number of elements in the collection. Len() int // Less reports whether the element with // index i should sort before the element with index j. Less(i, j int) bool // Swap swaps the elements with indexes i and j. Swap(i, j int) }
メソッド | 特徴 |
---|---|
Len() int | 配列・リストの要素数 |
Less(i, j int) bool | i < j を満たすかの真偽値 |
Swap(i,j int) | iとjの要素を入れ替える |
Sortの方法
標準パッケージで対応している型は下記になります。
- float64
- int
- string
ここでは、ソートの方法をint配列をもとにみていきます。
sort.Ints(a int[])
Ints()
メソッドは、int[]型をソートするメソッドです。
これは、昇順(increacing)にソートされます。
nums := []int{4, 3, 2, 10, 8} sort.Ints(nums) fmt.Println(nums) // output: [2 3 4 8 10]
内部では、 IntSlice
型のstructにつめかえを行い、Sort関数を呼んでいます。
(sort.Interface
を実装するルールは同じ)
// package sort // Ints sorts a slice of ints in increasing order. func Ints(a []int) { Sort(IntSlice(a)) } // IntSlice // Len,Less,Swapを実装したstruct // IntSlice attaches the methods of Interface to []int, sorting in increasing order. type IntSlice []int func (p IntSlice) Len() int { return len(p) } func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] } func (p IntSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
sort.Reverse(data Interface) Inteface
Reverse(data Interface)
は、sort.Interface型のソート方法を逆順に修正する関数です。
実際に内部で行っていることは、下記の2点です。
\1. reverse struct
にstruct
を詰め替える
reverse struct
は、 sort.Interface
を埋め込んでいます。
// package sort type reverse struct { // This embedded Interface permits Reverse to use the methods of // another Interface implementation. Interface } // Reverse returns the reverse order for data. func Reverse(data Interface) Interface { return &reverse{data} }
\2. Lessメソッドの引数をスワップ
reverse struct
は、実装を参照したところ、
Less(i,j int) bool
のみを再実装しています。
これにより、比較条件を逆にすることで、逆順ソートを実現しています。
// Less returns the opposite of the embedded implementation's Less method. func (r reverse) Less(i, j int) bool { return r.Interface.Less(j, i) }
sort.Search(n int, f func(int) bool) int
nの長さの配列内でf()=true
となる最小のindexを返却します。
→ 配列内で指定のvalueがあるかどうかを調べる関数です。
特徴
- 条件を満たさなかった場合、nが返却
- 一致を探すことも、ある数値以上の値を探すことも可能
- binary search(二分探索)で検索
- ソートされた配列に対して実行しないと正確な結果が返却されない
- 下記は
Search
のラッパー関数- func SearchFloat64s(a float64, x float64) int
- func SearchInts(a int, x int) int
- func SearchStrings(a []string, x string) int
// package sort // binary sort の実装 func Search(n int, f func(int) bool) int { // Define f(-1) == false and f(n) == true. // Invariant: f(i-1) == false, f(j) == true. i, j := 0, n for i < j { h := i + (j-i)/2 // avoid overflow when computing h // i ≤ h < j if !f(h) { i = h + 1 // preserves f(i-1) == false } else { j = h // preserves f(j) == true } } // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. return i } // Int ラッパー関数 func SearchInts(a []int, x int) int { return Search(len(a), func(i int) bool { return a[i] >= x }) }
利用サンプル
nums := []int{4, 3, 2, 10, 8} x := 8 // 事前にソートしておく sort.Ints(nums) // search asc index = sort.Search(len(nums), func(i int) bool { return nums[i] >= x }) if index < len(nums) && nums[index] == x { // nums[index] = 8 = x } else { // x は nums[]中に存在しなかった // だが、indexはnums[]の中にxをインサートする位置にある }
sort.Slice(slice interface{}, less func(i, j int) bool)
渡したsliceを、ソートする関数。
less関数で定義された順にソートされる。
特徴
- Go1.8以上
- sort.Interfaceを実装していなくてもソートが可能となっている
- stable sort(安定ソート)を保証していない
- sort.SliceStableを利用することで保証される
(参考)実際のソート処理の中身について
sort.Sort(data sort.Interface) は渡されるデータによってソートの種別変えています。
流れとしては、基本的にクイックソートを利用して、条件を満たした際の他のソート手法に切り替わるといった挙動です。
- ヒープソート
- 条件: log(n+1)の整数値の2乗の深さとなった場合
- 右に1ビットずつシフト演算して0になるまでの回数の2乗が最大の深さ(
maxDepth
) maxDepth
が0となったときに、ヒープソートに切り替わる
- 右に1ビットずつシフト演算して0になるまでの回数の2乗が最大の深さ(
- 条件: log(n+1)の整数値の2乗の深さとなった場合
// package golang // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
- シェルソート
- 条件: スライスが12より短い場合
// package golang // Use ShellSort for slices <= 12 elements
- クイックソート
- 条件: 上記条件に当てはまらない場合
まとめ
Golangのsortパッケージについて、学びました。
実際のソート処理の中身までは、深く追求しませんでしたが、
ソートを行う利用方法については触れられたかなと思います。