Go/iter.Seq版エラトステネスの篩
iter.Seqの応用 - エラトステネスの篩を実装する
[編集]Go 1.23で導入されたiterパッケージは、イテレータの新しい標準的な仕組みを提供します。その中でもiter.Seq[T]型は、遅延評価やストリーミング処理を可能にする強力な抽象化です。この記事では、古典的なアルゴリズムである「エラトステネスの篩」をiter.Seqを使って実装し、その応用例を紹介します。
iter.Seqとは
[編集]iter.Seq[T]は、型Tの値のシーケンスを表すイテレータです。以下のような関数型として定義されています：
type Seq[V any] func(yield func(V) bool) bool
この型は、yield関数を呼び出すことで値を一つずつ生成し、yieldがfalseを返した場合に処理を停止します。これにより、必要な分だけ値を生成する遅延評価が可能になります。
エラトステネスの篩の実装
[編集]エラトステネスの篩は、素数を効率的に見つけるアルゴリズムです。基本的な考え方は以下の通りです：
- 2から始まる自然数の列を用意する
- 最初の数（素数）を取り出す
- その数の倍数をすべて除去する
- 残った数から次の素数を取り出し、2-3を繰り返す
無限数列の生成
[編集]まず、2から始まる無限の数列を生成するジェネレータを作成します：
func generate() iter.Seq[int] { return func(yield func(int) bool) { for i := 2; yield(i); i++ { } } }
この関数はiter.Seq[int]を返し、2から始まって無限に続く数列を生成します。yield(i)がfalseを返すまで値を生成し続けます。
フィルタリング
[編集]次に、特定の素数で割り切れない数だけを通すフィルタを作成します：
func filter(inputSeq iter.Seq[int], prime int) iter.Seq[int] { return func(yield func(int) bool) { for i := range inputSeq { if i%prime != 0 { if !yield(i) { return } } } } }
この関数は、入力シーケンスinputSeqから値を受け取り、primeで割り切れない値のみを新しいシーケンスとして返します。
篩アルゴリズムの実装
[編集]最後に、エラトステネスの篩のメインロジックを実装します：
func sieve() iter.Seq[int] { return func(yield func(int) bool) { inputSeq := generate() // 最初の入力は無限数列 for { next, stop := iter.Pull(inputSeq) // プル方式に変換 { defer stop() // イテレータを停止 // 次の素数を取得 prime, ok := next() if !ok { break } // 素数を出力 if !yield(prime) { break } // 新しいフィルタリングされたシーケンスを作成 inputSeq = filter(inputSeq, prime) } } } }
このアルゴリズムの重要なポイントは以下の通りです：
- iter.Pull()の使用:
iter.Pull()を使ってプッシュ方式のイテレータをプル方式に変換し、必要な時に値を取得できるようにします - 動的フィルタリング: 新しい素数が見つかるたびに、その素数の倍数を除去する新しいフィルタを適用します
- 遅延評価: 実際に値が要求されたときにのみ計算が実行されます
実行例
[編集]実装したエラトステネスの篩を使って、100以下の素数を出力してみましょう：
func main() { for prime := range sieve() { if prime > 100 { break } fmt.Print(prime, " ") } }
実行結果：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
iter.Seqの利点
[編集]この実装から、iter.Seqの以下の利点が見えてきます：
- メモリ効率
- 無限数列を扱っているにも関わらず、必要な分だけメモリを使用します。全ての値を事前に配列に保存する必要がありません。
- 組み合わせ可能性
generate()、filter()、sieve()といった各部品を独立して実装し、組み合わせることができます。これにより、コードの再利用性と保守性が向上します。
- 遅延評価
- 値は実際に必要になったときにのみ計算されます。これにより、大きなデータセットや無限シーケンスを効率的に扱えます。
- 自然な制御フロー
for rangeループを使った自然な記述が可能で、従来のスライスやチャネルと同じような感覚で使用できます。
まとめ
[編集]iter.Seqを使ったエラトステネスの篩の実装を通じて、Go 1.23の新しいイテレータ機能の強力さを確認できました。遅延評価、メモリ効率、そして組み合わせ可能性といった特徴により、従来は難しかった無限シーケンスの処理や、大規模データの効率的な処理が可能になります。
この機能を活用することで、よりエレガントで効率的なGoプログラムを書くことができるでしょう。iter.Seqは、関数型プログラミングのパラダイムをGoに自然な形で取り入れる重要な機能と言えます。
附録
[編集]- 全体の実装
package main import ( "fmt" "iter" ) // 2, 3, 4, ...という無限の数列を生成するジェネレータ関数 func generate() iter.Seq[int] { return func(yield func(int) bool) { for i := 2; yield(i); i++ { } } } // フィルタジェネレータ関数 // 'inputSeq'から値を受け取り、'prime'で割り切れない値を返す func filter(inputSeq iter.Seq[int], prime int) iter.Seq[int] { return func(yield func(int) bool) { for i := range inputSeq { if i%prime != 0 { if !yield(i) { return } } } } } // 素数篩 (Sieve) のジェネレータ関数 // 素数を生成する func sieve() iter.Seq[int] { return func(yield func(int) bool) { inputSeq := generate() // 最初の入力は無限数列のシーケンス for { next, stop := iter.Pull(inputSeq) // イテレータ関数をpull方式に変換する { defer stop() // イテレータを止める // 次の素数を取得 prime, ok := next() if !ok { break } // 素数を出力 if !yield(prime) { break } // 取得した素数でフィルタリングする新しいシーケンスを作成 inputSeq = filter(inputSeq, prime) } } } } // 素数を100まで出力してテストする func main() { for prime := range sieve() { if prime > 100 { break } fmt.Print(prime, " ") } }