Pythonでフロイドの循環検出アルゴリズムを使ってみる　#449

leetcodeでハッピーナンバー判定を実装していて、表題のアルゴリズムの存在を知りました。

ある数nがハッピーかどうかを判定するアルゴリズムを書きなさい。
ハッピーナンバーとは、以下のプロセスで定義される数である：

・任意の正の整数から始め、その数を桁の2乗の和で置き換える。
・その数が1に等しくなるまで（そのまま）、あるいは1を含まないサイクルでエンドレスにループするまで、この処理を繰り返す。
・この処理が1で終わる数はハッピーナンバーである。

nが幸福な数であればtrueを、そうでなければfalseを返す。

leetcode

つまりは特定の処理を通じて「1」に行き着くか、無限ループに入ってしまうかどうかを判定する、というものです。

このお題に対して、まずは試行錯誤のうえハッシュセットを使って以下のように実装しました。わざわざハッシュセットを自作せずset()を使ってもパフォーマンスは同じだったのですが、まぁハッシュセットの問題だったのでこちらにしました。

class Solution:
    def __init__(self, capacity=5):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]

    def hash(self, key: int) -> int:
        # シンプルなハッシュ関数：キーをバケット数で割った余り
        return key % self.capacity

    def isHappy(self, n: int) -> bool:
        def _get_next(number):
            total_num = 0
            while number > 0:
                number, digit = divmod(number, 10)
                total_num += digit ** 2
            return total_num
        
        while n != 1 and n not in self.buckets[self.hash(n)]:
            self.buckets[self.hash(n)].append(n)
            n = _get_next(n)
            
        return n == 1

結果が1になる (=true)か、もしくは結果が既出の数字と一致する (=無限ループに入っている=false) までwhileでループする仕組みです。

パフォーマンス結果は以下の通りで、まずまずの速度でした。

Runtime: 39 ms
Memory Usage: 16.4 MB

ただ、leetcode全体の中では真ん中くらいの速度で、上位層と比べて何が違うのか気になりました。

そこで色々と調べて行き着いたのがフロイドの循環検出アルゴリズムです。
まず結論から、以下のように実装しました。

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0
            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit ** 2
            return total_sum
        
        slow, fast = n, get_next(n)
        while fast != 1 and slow != fast:
            slow = get_next(slow)
            fast = get_next(get_next(fast))
        
        return fast == 1    

パフォーマンス結果は以下の通り高速化し、速度面で上位に食い込むことができました（メモリは変わらずでしたが）。

Runtime: 26 ms
Memory Usage: 16.5 MB

それではアルゴリズムについて解説します。

フロイドの循環検出アルゴリズムとは

フロイドの循環検出アルゴリズムは、リンクリストの循環検出や、数列内の循環パターンの検出、アルゴリズム内での無限ループの検出など、多様な用途に使用されます。

ハッピーナンバーの判定のような数学的問題においても、数値の変化が特定の循環パターンを形成するかどうかを検出できます。

基本概念

遅いポインタ（トータス）と速いポインタ（ヘア）の2つを使用します。

これらはデータ構造の開始点から開始し、トータスは一度に1ステップ進み、ヘアは一度に2ステップ進みます。もしデータ構造内に循環が存在すれば、ヘアが1周してトータスに追いつく（両者が同じ要素を指す）という事実を利用して循環を検出します。

上記のコードではslowが1ステップずつ、fastが2ステップずつ進み、その2つが一致すると「追いついた = 循環が発生して無限ループに入った」と判定しています。

アルゴリズムの限界

基本概念から類推できるように、このアルゴリズムは「ある要素が次に進む要素を一意に決定する」という前提に基づいています。

つまり連続する要素が同じ値を持つような配列やリストの場合、特にそれが循環を形成していない場合には、このアルゴリズムを直接適用することは適切ではありません。

適した配列の例「1, 2, 3, 4, 5, 6, 4, 5, 6, 4, 5, 6」
適さない配列の例「1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5」

後者の方では1ステップ先と2ステップ先が同じ値になってしまい、追いついてないのに追いついたと誤認してしまいます。そのため、循環検出したい配列がどのような性質を持っているか、見極めたうえで使用しなければいけません。

アルゴリズムで検出できること

このアルゴリズムでは以下がわかります。

①循環が発生しているかどうか
②循環に入るまでの長さ
③循環の長さ

上記のコード例では①しか使用していません。
②と③の導き方はこちらのブログが大変わかりやすく解説してくださっていました。

Rでフロイドの循環検出法を可視化する - Qiita

図がとてもわかりやすかったので、ぜひご覧になってみてください。

ここまでお読みいただきありがとうございました！！

参考

Rでフロイドの循環検出法を可視化する - Qiita