Time Limited Cache - 有効期限付きキャッシュ

アルゴリズム概要

Input:
actions = ["TimeLimitedCache", "set", "get", "count", "get"]
values = [[], [1, 42, 100], [1], [], [1]]
timeDelays = [0, 0, 50, 50, 150]

Output: [null, false, 42, 1, -1]

説明:
t=0: キャッシュを構築
t=0: set(1, 42, 100) → false（新規キー）
t=50: get(1) → 42（未期限切れ）
t=50: count() → 1（アクティブなキー）
t=100: key=1 が期限切れ
t=150: get(1) → -1（期限切れ）

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

TypeScript実装

/**
 * キャッシュエントリの内部構造
 * @property value - 保存された値
 * @property expiresAt - 期限時刻（ミリ秒、Date.now()ベース）
 */
interface CacheEntry {
    value: number;
    expiresAt: number;
}

/**
 * 有効期限付きキャッシュクラス（遅延削除方式）
 * @description タイマーを使わず期限時刻で管理することで高速化
 */
class TimeLimitedCache {
    private cache: Map<number, CacheEntry>;

    constructor() {
        this.cache = new Map<number, CacheEntry>();
    }

    /**
     * キーと値を設定し、有効期限を指定
     * @param key - キー (0 <= key <= 10^9)
     * @param value - 値 (0 <= value <= 10^9)
     * @param duration - 有効期限（ミリ秒、0 <= duration <= 1000）
     * @returns 既存の未期限切れキーが存在した場合true、それ以外false
     * @complexity Time: O(1), Space: O(1)
     */
    set(key: number, value: number, duration: number): boolean {
        // 現在時刻と期限時刻を計算
        const now = Date.now();
        const expiresAt = now + duration;

        // 既存エントリの確認
        const existingEntry = this.cache.get(key);

        // 既存エントリが存在し、かつ未期限切れかチェック
        const hadUnexpiredKey = existingEntry !== undefined
            && existingEntry.expiresAt > now;

        // 新しいエントリを設定（タイマー不要）
        this.cache.set(key, { value, expiresAt });

        return hadUnexpiredKey;
    }

    /**
     * キーに対応する値を取得
     * @param key - 取得するキー
     * @returns 未期限切れのキーが存在すれば対応する値、存在しなければ-1
     * @complexity Time: O(1), Space: O(1)
     */
    get(key: number): number {
        const entry = this.cache.get(key);

        // エントリが存在しない場合
        if (entry === undefined) {
            return -1;
        }

        // 期限切れチェック
        if (entry.expiresAt <= Date.now()) {
            // 遅延削除: get時に初めて削除
            this.cache.delete(key);
            return -1;
        }

        return entry.value;
    }

    /**
     * 未期限切れキーの数を取得
     * @returns アクティブなキーの数
     * @complexity Time: O(n), Space: O(1)
     */
    count(): number {
        const now = Date.now();
        let count = 0;

        // 全エントリを走査して有効なもののみカウント
        for (const entry of this.cache.values()) {
            if (entry.expiresAt > now) {
                count++;
            }
        }

        return count;
    }
}

/**
 * 使用例:
 * const timeLimitedCache = new TimeLimitedCache()
 * timeLimitedCache.set(1, 42, 1000); // false
 * timeLimitedCache.get(1) // 42
 * timeLimitedCache.count() // 1
 */

フローチャート: set メソッド

フローの説明：
1. 期限時刻を計算: Date.now() + duration で期限時刻を算出
2. 既存エントリのチェック: Mapから既存エントリを取得
3. 期限切れ判定: 既存エントリがある場合、expiresAt > now で有効性を確認
4. フラグ設定: 未期限切れなら true、それ以外は false
5. エントリ更新: 新しい値と期限時刻でMapを更新
6. 結果を返却: hadUnexpiredKey を返す

計算量分析