Debounce - 関数実行の遅延とキャンセル制御

アルゴリズム概要

calls = [
  {"t": 50, "inputs": [1]},
  {"t": 75, "inputs": [2]}
]
Output: [{"t": 125, "inputs": [2]}]

説明: 1回目の呼び出しは2回目によってキャンセルされる
     2回目は75ms + 50ms = 125msに実行される

calls = [
  {"t": 50, "inputs": [1]},
  {"t": 100, "inputs": [2]}
]
Output: [{"t": 70, "inputs": [1]}, {"t": 120, "inputs": [2]}]

説明: 1回目は50ms + 20ms = 70msに実行
     2回目は100ms + 20ms = 120msに実行

ステップバイステップ解説

Python実装

from __future__ import annotations
from typing import Callable, Any
from threading import Timer


def debounce(fn: Callable[..., Any], t: float) -> Callable[..., None]:
    """
    関数の実行をデバウンスする（遅延実行＆キャンセル機能付き）

    Args:
        fn: デバウンス対象の関数
        t: 遅延時間（ミリ秒）

    Returns:
        デバウンスされた関数

    Complexity:
        Time: O(1) per call
        Space: O(1)
    """
    # タイマーオブジェクトを保持するクロージャ変数
    timer: Timer | None = None

    def debounced_func(*args: Any, **kwargs: Any) -> None:
        nonlocal timer

        # 既存のタイマーがあればキャンセル
        if timer is not None:
            timer.cancel()

        # 新しいタイマーをセット（t/1000 秒後に fn を実行）
        # threading.Timer は秒単位なので、ミリ秒を秒に変換
        timer = Timer(t / 1000.0, fn, args=args, kwargs=kwargs)
        timer.start()

    return debounced_func


# LeetCode形式の実装例
class Solution:
    """
    LeetCode形式のラッパークラス
    実際のLeetCodeにはこの問題はJavaScript/TypeScriptのみだが、
    Pythonで同等の機能を提供
    """

    def debounce(self, fn: Callable[..., Any], t: int) -> Callable[..., None]:
        """
        Args:
            fn: デバウンス対象の関数
            t: 遅延時間（ミリ秒、整数）

        Returns:
            デバウンスされた関数
        """
        timer: Timer | None = None

        def debounced(*args: Any, **kwargs: Any) -> None:
            nonlocal timer

            # 基底条件: タイマーが存在すればキャンセル
            if timer is not None:
                timer.cancel()

            # 遷移: 新しいタイマーを作成して開始
            # t ミリ秒 = t/1000 秒
            timer = Timer(t / 1000.0, fn, args=args, kwargs=kwargs)
            timer.start()

        return debounced

フローチャート

フローの説明：
1. デバウンス関数が呼ばれると、まず既存のタイマーの有無を確認
2. タイマーがあれば即座にキャンセル（前の実行を中止）
3. 新しいタイマーを t/1000 秒後に設定
4. 呼び出し時の引数をクロージャに保存
5. タイマーを開始し、t ミリ秒待機
6. 待機完了後、保存された引数で元の関数 fn を実行

計算量分析