Elixirでエラトステネスのふるいを実装してみた
はじめに
Elixirを用いて「エラトステネスのふるい」を実装してみました。
ソースコード(※ まだドキュメント等は整備中)
「エラトステネスのふるい」とは？
特徴
Elixirによるエラトステネスのふるいを実装した他のライブラリとの差として、エラトステネスのふるいをタプルで表現しています。
「エラトステネスのふるい」は指定された範囲までの素数をリストアップした素数表を生成し、素数判定時に素数表を参照して判定を高速化する手法です。つまり、生成された素数表を何度も使い回すことになります。
素数表をリストで作成した場合、リストは先頭から探索されるので素数表が大きくなればなるほど探索に時間が掛かります。
その点、タプルであれば素数表のサイズが大きくなったとしても高速でアクセスできると考えました。
タプルのドキュメントにも高速アクセスが特徴であると記載されています。
Tuples store elements contiguously in memory. This means accessing a tuple element by index or getting the tuple size is a fast operation.
ただ、良いベンチマークライブラリを見つけていないので実際のところ速度比較はできていません。
私の環境では、10000までは現実的な時間で素数表を生成することができます。
100000は全然結果が帰ってきませんでした。
そのため、まだまだ高速化の余地があると考えています。
使い方
Sieve.make/1で必要な範囲までの素数表を返します。
Sieve.is_prime?/2に、判定したい値と素数表を渡すことで素数かどうかを判定します。
iex> primes = Sieve.make(100)
iex> Sieve.is_prime?(3, primes)
true
iex> Sieve.is_prime?(8, primes)
false
余談
今回の実装はほぼLiveBook上で行いました(テスト等は別)
シンタックスハイライトや補完機能があり、ソースコード実行も可能なので非常に便利でした。
Fly.ioへのデプロイを使えば、何の準備も無い状態から10分でLiveBookを使い始めることが可能なのでオススメです。
Discussion