ふと耳にしたので箇条書きでメモる。間違ってたらごめんなさい。 「パッケージ」はモジュールより細かい、可視性の制御単位 Golangaでは、依存グラフがどのように解決されたかの情報を含むlockファイルは存在しない。 以下の方法で解決している。 go.modには下限制約しか書けず、インストールするモジュールは最小(最古)バージョンに解決する (c.f) bundleだと上限も制限でき、インストールするモジュールは依存関係を満たした上での最新バージョンになっていたはず 同一パッケージの下限制約のmajor versionが違ったらどうなる？ どうなるかはわからないが、以下の方法でこの問題を避けることはできる。 メジャーバージョンをパッケージ名に含める(e.g. module github.com/my/mod/v2)ことで、プロジェクト内で同一パッケージの複数のバージョンが共存することが許容される。(Semantic Import Versioningと呼ばれる) → 参考

Goでプログラミングの基礎を学ぶシリーズ スクールでは教えてくれないプログラミングの基礎、データ構造とアルゴリズムをGoで学んでいくシリーズです。 そのデータ構造がどのようなものであるかは、理解を助けてくれるサイトを紹介しつつ、簡単な説明に留めさせていただきます。(ご自身でも調べてみてください！) 筆者自身、Exerciseに取り組みながら理解を深めていったので、コードの解説を中心に記事を書いていきたいと思います。 タイトル #0 はじめに (環境構築と勉強方法) #1 Pointer, Array, String (ポインタと配列と文字列と) #2 File operations (ファイル操作) #3 Linked List (連結リスト) #4 Stack & Queue (スタックとキュー) #5 Search algorithms (探索アルゴリズム) #6 Tree (木構造) #7 Sorting algorithms (ソートアルゴリズム) #8 String pattern matching algorithms (文字列探索アルゴリズム) ☜ here 最終回となる今回は#8 String pattern matching algorithms (文字列探索アルゴリズム)です。 String pattern matching とは 文字列探索とは、ある文字列の中から、別のある文字列を探索することであり、さまざまなアルゴリズムがあります。 ここでは中でも代表的な文字列探索のアルゴリズムの Go での実装例をみていきます。 Naive algorithm (ナイーブ法) ナイーブ法は、Brute Force algorithm (力まかせ探索) とも呼ばれます。 文字列( text )と探索文字列( pattern )を先頭から1文字ずつ探索し、不一致があった場合は探索文字列を1文字だけずらして、再度探索文字列の先頭から1文字ずつ探索していくアルゴリズムです。 文字列の長さを n, 探索文字列の長さを m としたときの時間計算量は $O(mn)$ ですが、これは文字列および探索文字列のなかで、同じ文字が何度も続く場合の計算量になりますので、実質はほぼ $O(n)$ となるようです。 func NaiveSearch(txt, pat string) { if len(txt) <= len(pat) { fmt.Println("text is shorter than pattern!") } patLastIndex := len(pat) - 1 // pattern の最後の index var idx []int // pattern と一致した text 部分の先頭の index を格納する slice for i := 0; i < len(txt)-patLastIndex; i++ { for j := 0; j < len(pat); j++ { if txt[i+j] != pat[j] { break // 文字が一致しないとき、 i を一つ進める } if j == patLastIndex { // pattern がすべて一致したとき idx = append(idx, i) } } } if len(idx) != 0 { fmt.Printf("match index: %v\n", idx) } else { fmt.Println("no matching index!") } } func main() { NaiveSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy") } ☟ 出力結果 match index: [7 17] Knuth-Morris-Pratt algorithm (KMP法) KMP法 (クヌース・モリス・プラット法)は、探索文字列の先頭から探索していくのは ナイーブ法 と同様ですが、余計な探索を避けるための工夫がなされています。 文字列の長さを n, 探索文字列の長さを m としたときの時間計算量は $O(n)$ となりますが、実装は少々複雑になります。 詳細は以下サイトをご参考ください。 func KMPSearch(txt, pat string) { if len(txt) < len(pat) { fmt.Println("text is shorter than pattern!") } // スライドする文字数を決める ずらし表 を作成(pattern に対して pattern 自身を比較する) table := make([]int, len(pat)) table[0] = 0 for i, j := 1, 0; i < len(pat); { // j は pattern 自身の比較で直前までに一致していた文字数 if pat[i] == pat[j] { // 一致している場合 j++ table[i] = j i++ } else { // 一致しない場合 if j != 0 { j = table[j-1] } else { table[i] = 0 i++ } } } fmt.Printf("table: %v\n", table) var idx []int // pattern と一致した text 部分の先頭の index を格納する slice for i, j := 0, 0; i < len(txt); { if txt[i] == pat[j] { // 文字が一致している場合 j++ i++ if j == len(pat) { // pattern がすべて一致したとき idx = append(idx, i-j) j = table[j-1] } } else { // 文字が一致しない場合 if j != 0 { j = table[j-1] } else { i++ } } } if len(idx) != 0 { fmt.Printf("match index: %v\n", idx) } else { fmt.Println("no matching index!") } } func main() { KMPSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy") } ☟ 出力結果 table: [0 0 1 2 0] match index: [7 17] Boyer-Moore algorithm (BM法) BM法 (ボイヤー・ムーア法)は、ナイーブ法やKMP法と異なり、探索文字列の後方から探索していくアルゴリズムです。 KMP法 と同様に、余計な探索を避けるために工夫されています。 文字列の長さを n, 探索文字列の長さを m としたときの時間計算量は、最良の場合で $O(n/m)$, 最悪の場合で $O(mn)$ となります。 しかし、 ナイーブ法 と同様に、最悪の場合というのは、これは文字列および探索文字列のなかで、同じ文字が何度も続く場合になりますので、実用する上では、ナイーブ法, KMP法 よりも高速なアルゴリズムのようです。 詳細は以下サイトをご参考ください。 func BMSearch(txt, pat string) { if len(txt) < len(pat) { fmt.Println("text is shorter than pattern!") } patLastIndex := len(pat) - 1 // pattern の最後の index // スライドする文字数を決める ずらし表 を作成 table := make(map[byte]int) for i, j := patLastIndex, 0; i >= 0; i, j = i-1, j+1 { // j は pattern の末尾からの文字数 if _, ok := table[pat[i]]; !ok { // pattern に含まれる文字でまだ table に存在しない場合 table[pat[i]] = j } } var idx []int // pattern と一致した text 部分の先頭の index を格納する slice for i := patLastIndex; i < len(txt); { // pattern の後方から探索を行う for j := 0; j < len(pat); j++ { // j は pattern の末尾からの文字数 // 文字が一致している場合 if txt[i-j] == pat[patLastIndex-j] { if j == patLastIndex { // pattern がすべて一致したとき idx = append(idx, i-j) } else { continue } } // 文字が一致しない場合 または pattern がすべて一致した場合、比較位置をずらす slide, ok := table[txt[i-j]] // スライドする文字数を table から取得 if !ok { // 比較している text の文字が pattern の中にない場合 slide = len(pat) } // スライドする文字数を求める if slide-j > 0 { i += slide - j } else { // 現在の位置より前にスライドしてしまう場合 i++ // 1 だけスライドする } break // j++ しても文字が一致することはないので break } } if len(idx) != 0 { fmt.Printf("match index: %v\n", idx) } else { fmt.Println("no matching index!") } } func main() { BMSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy") } ☟ 出力結果 table: map[120:2 121:0] match index: [7 17] おわりに Exerciseの解答例はあくまで例なので、もっといい書き方あるよ！という方、ぜひコメントをお寄せください！ 説明についても、筆者自身が初心者であるため、ご指摘や補足は大歓迎でございます。 株式会社Link Sportsでは、あらゆるスポーツを楽しむ人たちに送る、チームマネジメントアプリを開発しています。 未経験でも経験豊富なエンジニアの方でも、スポーツ好きなら活躍できる環境があります！ 絶賛エンジニア募集中です！ Wantedly ▶︎ https://www.wantedly.com/projects/324177 Green ▶︎ https://www.green-japan.com/job/82003 データ構造とアルゴリズムを Go での実装例とともに学習してきましたが、いかがでしたか？ プログラミングスクールでは、全体像を掴むためにフレームワークを用いて簡単なアプリを作ったりすることと思いますが、いざ就職してみると、思うようにコードが書けない！なんてことになりませんでしたか？ 筆者自身は、データ構造とアルゴリズムを学習してからのほうが、格段にコードが書きやすくなりました。 このシリーズがプログラミング初心者の方の助けになれば幸いです。