"""
コード例1: 操作パターンによるデータ構造選択の比較
 
要件: 大量の整数データに対して「存在確認」を頻繁に行う
"""
import time
from typing import List, Set
 
 
def benchmark_membership_test(data_list: List[int], data_set: Set[int],
                               queries: List[int]) -> None:
    """リストとセットでの存在確認の性能差を示す"""
 
    # --- リストでの存在確認: O(n) ---
    start = time.perf_counter()
    count_list = 0
    for q in queries:
        if q in data_list:
            count_list += 1
    elapsed_list = time.perf_counter() - start
 
    # --- セットでの存在確認: 期待 O(1) ---
    start = time.perf_counter()
    count_set = 0
    for q in queries:
        if q in data_set:
            count_set += 1
    elapsed_set = time.perf_counter() - start
 
    print(f"データ件数: {len(data_list):>10,}")
    print(f"クエリ件数: {len(queries):>10,}")
    print(f"リスト検索: {elapsed_list:.4f} 秒  (ヒット数: {count_list})")
    print(f"セット検索: {elapsed_set:.4f} 秒  (ヒット数: {count_set})")
    print(f"速度比:     {elapsed_list / max(elapsed_set, 1e-9):.1f} 倍")
    print()
 
 
if __name__ == "__main__":
    import random
    random.seed(42)
 
    for size in [1_000, 10_000, 100_000]:
        data = list(range(size))
        data_set = set(data)
        queries = [random.randint(0, size * 2) for _ in range(10_000)]
        benchmark_membership_test(data, data_set, queries)

"""
コード例2: 検索パターン別の最適構造
"""
 
 
# --- 完全一致検索: dict / set が最適 ---
def build_user_lookup(users: list[dict]) -> dict[int, dict]:
    """ユーザーリストから ID → ユーザー情報のルックアップテーブルを構築"""
    return {user["id"]: user for user in users}
 
 
# 使用例
users = [
    {"id": 1, "name": "Alice", "email": "alice@example.com"},
    {"id": 2, "name": "Bob", "email": "bob@example.com"},
    {"id": 3, "name": "Charlie", "email": "charlie@example.com"},
]
lookup = build_user_lookup(users)
print(lookup[2])  # O(1) で取得: {'id': 2, 'name': 'Bob', ...}
 
 
# --- 複数条件での検索: 複合インデックスの構築 ---
from collections import defaultdict
 
 
def build_multi_index(users: list[dict]) -> dict:
    """複数のキーでインデックスを構築"""
    index = {
        "by_id": {},
        "by_email": {},
        "by_name_prefix": defaultdict(list),
    }
    for user in users:
        index["by_id"][user["id"]] = user
        index["by_email"][user["email"]] = user
        # 名前の各プレフィックスでインデックス（簡易 Trie 的アプローチ）
        name = user["name"].lower()
        for i in range(1, len(name) + 1):
            index["by_name_prefix"][name[:i]].append(user)
    return index
 
 
multi_idx = build_multi_index(users)
print(multi_idx["by_email"]["bob@example.com"])     # O(1)
print(multi_idx["by_name_prefix"]["ch"])             # O(1) + 結果数

"""
コード例3: 範囲検索の実装（bisect モジュール活用）
"""
import bisect
from datetime import datetime, timedelta
 
 
class TimeSeriesIndex:
    """タイムスタンプベースの範囲検索を効率的に行うインデックス"""
 
    def __init__(self):
        self._timestamps: list[float] = []
        self._values: list[dict] = []
 
    def insert(self, timestamp: datetime, value: dict) -> None:
        """タイムスタンプ順を維持しながらデータを挿入"""
        ts = timestamp.timestamp()
        pos = bisect.bisect_left(self._timestamps, ts)
        self._timestamps.insert(pos, ts)
        self._values.insert(pos, value)
 
    def range_query(self, start: datetime, end: datetime) -> list[dict]:
        """指定した時間範囲内のデータを取得 - O(log n + k)"""
        start_ts = start.timestamp()
        end_ts = end.timestamp()
        left = bisect.bisect_left(self._timestamps, start_ts)
        right = bisect.bisect_right(self._timestamps, end_ts)
        return self._values[left:right]
 
    def __len__(self) -> int:
        return len(self._timestamps)
 
 
# 使用例
index = TimeSeriesIndex()
base_time = datetime(2025, 1, 1)
 
# データ挿入
for i in range(1000):
    t = base_time + timedelta(hours=i)
    index.insert(t, {"event_id": i, "time": t.isoformat()})
 
# 範囲検索: 最初の24時間のイベント
results = index.range_query(
    base_time,
    base_time + timedelta(hours=24)
)
print(f"最初の24時間のイベント数: {len(results)}")  # 25
print(f"最初のイベント: {results[0]}")
print(f"最後のイベント: {results[-1]}")

"""
コード例4: 用途に応じたキュー選択
"""
import heapq
from collections import deque
 
 
# --- 通常のキュー (FIFO): deque ---
class TaskQueue:
    """単純な先入先出のタスクキュー"""
 
    def __init__(self):
        self._queue = deque()
 
    def enqueue(self, task: str) -> None:
        self._queue.append(task)
 
    def dequeue(self) -> str:
        if not self._queue:
            raise IndexError("キューが空です")
        return self._queue.popleft()  # O(1)
 
    def __len__(self) -> int:
        return len(self._queue)
 
 
# --- 優先度キュー: heapq ---
class PriorityTaskQueue:
    """優先度付きタスクキュー（数値が小さいほど高優先度）"""
 
    def __init__(self):
        self._heap: list[tuple[int, int, str]] = []
        self._counter = 0  # タイブレーカー（同一優先度の安定性）
 
    def enqueue(self, task: str, priority: int) -> None:
        heapq.heappush(self._heap, (priority, self._counter, task))
        self._counter += 1
 
    def dequeue(self) -> tuple[int, str]:
        if not self._heap:
            raise IndexError("キューが空です")
        priority, _, task = heapq.heappop(self._heap)  # O(log n)
        return priority, task
 
    def peek(self) -> tuple[int, str]:
        if not self._heap:
            raise IndexError("キューが空です")
        priority, _, task = self._heap[0]  # O(1)
        return priority, task
 
    def __len__(self) -> int:
        return len(self._heap)
 
 
# 使用例
print("=== 通常のキュー ===")
tq = TaskQueue()
for task in ["メール送信", "ログ出力", "DB更新"]:
    tq.enqueue(task)
while len(tq) > 0:
    print(f"  処理: {tq.dequeue()}")
 
print("\n=== 優先度キュー ===")
pq = PriorityTaskQueue()
pq.enqueue("バグ修正", priority=1)       # 最高優先度
pq.enqueue("新機能開発", priority=3)     # 低優先度
pq.enqueue("セキュリティ修正", priority=1)  # 最高優先度
pq.enqueue("ドキュメント更新", priority=5)  # 最低優先度
pq.enqueue("パフォーマンス改善", priority=2)
 
while len(pq) > 0:
    pri, task = pq.dequeue()
    print(f"  優先度 {pri}: {task}")

# 集合演算の活用例
admin_permissions = {"read", "write", "delete", "admin"}
editor_permissions = {"read", "write"}
viewer_permissions = {"read"}
 
# 和集合: ユーザーが持つ全権限
user_roles = ["editor", "viewer"]
all_permissions: set[str] = set()
role_map = {
    "admin": admin_permissions,
    "editor": editor_permissions,
    "viewer": viewer_permissions,
}
for role in user_roles:
    all_permissions |= role_map[role]  # O(len(smaller_set))
print(f"全権限: {all_permissions}")  # {'read', 'write'}
 
# 積集合: 全ロールに共通の権限
common = admin_permissions & editor_permissions & viewer_permissions
print(f"共通権限: {common}")  # {'read'}
 
# 差集合: admin だけが持つ権限
admin_only = admin_permissions - editor_permissions
print(f"admin固有: {admin_only}")  # {'delete', 'admin'}

"""
コード例5: 重複排除の実装比較とベンチマーク
"""
import time
import random
from typing import Callable
 
 
def deduplicate_with_list(data: list[int]) -> list[int]:
    """リストを使った重複排除 - O(n^2)"""
    result: list[int] = []
    for item in data:
        if item not in result:  # O(n) の検索が毎回発生
            result.append(item)
    return result
 
 
def deduplicate_with_set(data: list[int]) -> list[int]:
    """セットを使った重複排除（挿入順保持）- O(n)"""
    seen: set[int] = set()
    result: list[int] = []
    for item in data:
        if item not in seen:  # O(1) の検索
            seen.add(item)
            result.append(item)
    return result
 
 
def deduplicate_with_dict(data: list[int]) -> list[int]:
    """dictを使った重複排除（Python 3.7+ 挿入順保持）- O(n)"""
    return list(dict.fromkeys(data))
 
 
def benchmark(func: Callable, data: list[int], label: str) -> float:
    """関数の実行時間を計測"""
    start = time.perf_counter()
    result = func(data)
    elapsed = time.perf_counter() - start
    return elapsed
 
 
if __name__ == "__main__":
    random.seed(42)
 
    print("重複排除ベンチマーク")
    print("=" * 60)
 
    for size in [100, 1_000, 10_000]:
        # データの50%が重複するように生成
        data = [random.randint(0, size // 2) for _ in range(size)]
 
        print(f"\nデータ件数: {size:>10,}  (ユニーク: 約 {size // 2:,})")
        print("-" * 60)
 
        # リスト方式
        t_list = benchmark(deduplicate_with_list, data, "list")
        print(f"  list方式:     {t_list:.6f} 秒")
 
        # セット方式
        t_set = benchmark(deduplicate_with_set, data, "set")
        print(f"  set方式:      {t_set:.6f} 秒")
 
        # dict方式
        t_dict = benchmark(deduplicate_with_dict, data, "dict")
        print(f"  dict方式:     {t_dict:.6f} 秒")
 
        if t_set > 0:
            print(f"  list/set比:   {t_list / t_set:.1f} 倍")

"""
コード例6: LRU キャッシュの実装
ハッシュテーブル + 双方向連結リスト による O(1) 実装
"""
from collections import OrderedDict
from typing import Optional, Hashable
 
 
class LRUCache:
    """
    OrderedDict を用いた LRU キャッシュ
 
    OrderedDict は内部的に双方向連結リストを持ち、
    要素の順序変更を O(1) で行える。
    これにハッシュテーブルの O(1) 検索を組み合わせることで、
    get/put ともに O(1) を実現する。
    """
 
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("キャパシティは正の整数を指定してください")
        self._capacity = capacity
        self._cache: OrderedDict[Hashable, object] = OrderedDict()
        self._hits = 0
        self._misses = 0
 
    def get(self, key: Hashable) -> Optional[object]:
        """
        キーに対応する値を取得（O(1)）
        アクセスされた要素は末尾（最新）に移動する
        """
        if key in self._cache:
            self._cache.move_to_end(key)  # O(1): 最新としてマーク
            self._hits += 1
            return self._cache[key]
        self._misses += 1
        return None
 
    def put(self, key: Hashable, value: object) -> None:
        """
        キーと値を格納（O(1)）
        容量超過時は最も古い要素を削除する
        """
        if key in self._cache:
            self._cache.move_to_end(key)
        self._cache[key] = value
        if len(self._cache) > self._capacity:
            self._cache.popitem(last=False)  # O(1): 最古の要素を削除
 
    @property
    def hit_rate(self) -> float:
        total = self._hits + self._misses
        return self._hits / total if total > 0 else 0.0
 
    def __len__(self) -> int:
        return len(self._cache)
 
    def __repr__(self) -> str:
        return (f"LRUCache(capacity={self._capacity}, size={len(self)}, "
                f"hit_rate={self.hit_rate:.2%})")
 
 
# 使用例
cache = LRUCache(capacity=3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
print(cache.get("a"))   # 1（"a" が最新に）
cache.put("d", 4)       # 容量超過 → "b" が削除される
print(cache.get("b"))   # None（削除済み）
print(cache.get("c"))   # 3
print(cache)            # LRUCache(capacity=3, size=3, hit_rate=66.67%)

"""
コード例7: 主要データ構造の挿入・検索ベンチマーク
"""
import time
import random
import bisect
from collections import deque
 
 
def benchmark_insert_search(n: int) -> dict:
    """各データ構造の挿入と検索の所要時間を計測"""
    random.seed(42)
    data = [random.randint(0, n * 10) for _ in range(n)]
    queries = [random.randint(0, n * 10) for _ in range(min(n, 10_000))]
 
    results = {}
 
    # --- list ---
    start = time.perf_counter()
    lst: list[int] = []
    for item in data:
        lst.append(item)
    insert_time = time.perf_counter() - start
 
    start = time.perf_counter()
    for q in queries:
        _ = q in lst
    search_time = time.perf_counter() - start
    results["list"] = {"insert": insert_time, "search": search_time}
 
    # --- set ---
    start = time.perf_counter()
    s: set[int] = set()
    for item in data:
        s.add(item)
    insert_time = time.perf_counter() - start
 
    start = time.perf_counter()
    for q in queries:
        _ = q in s
    search_time = time.perf_counter() - start
    results["set"] = {"insert": insert_time, "search": search_time}
 
    # --- dict ---
    start = time.perf_counter()
    d: dict[int, bool] = {}
    for item in data:
        d[item] = True
    insert_time = time.perf_counter() - start
 
    start = time.perf_counter()
    for q in queries:
        _ = q in d
    search_time = time.perf_counter() - start
    results["dict"] = {"insert": insert_time, "search": search_time}
 
    # --- ソート済みリスト + bisect ---
    start = time.perf_counter()
    sorted_lst: list[int] = []
    for item in data:
        bisect.insort(sorted_lst, item)
    insert_time = time.perf_counter() - start
 
    start = time.perf_counter()
    for q in queries:
        idx = bisect.bisect_left(sorted_lst, q)
        _ = idx < len(sorted_lst) and sorted_lst[idx] == q
    search_time = time.perf_counter() - start
    results["sorted_list"] = {"insert": insert_time, "search": search_time}
 
    return results
 
 
if __name__ == "__main__":
    print("データ構造別 挿入・検索ベンチマーク")
    print("=" * 70)
 
    for n in [1_000, 10_000, 100_000]:
        print(f"\n--- n = {n:,} ---")
        results = benchmark_insert_search(n)
        print(f"  {'構造':<15} {'挿入(秒)':<15} {'検索(秒)':<15}")
        print(f"  {'-'*45}")
        for name, times in results.items():
            print(f"  {name:<15} {times['insert']:<15.6f} {times['search']:<15.6f}")

# 悪い例: データ構造を直接公開
class UserService:
    def __init__(self):
        self.users: list[dict] = []  # 内部構造が外部に露出
 
# 良い例: 抽象化層を設ける
class UserRepository:
    def __init__(self):
        self._users_by_id: dict[int, dict] = {}  # 内部構造は非公開
 
    def add(self, user: dict) -> None:
        self._users_by_id[user["id"]] = user
 
    def find_by_id(self, user_id: int) -> dict | None:
        return self._users_by_id.get(user_id)
 
    def find_all(self) -> list[dict]:
        return list(self._users_by_id.values())

# ============================================================
# アンチパターン: 何でもリストで処理する
# ============================================================
 
# --- 問題のあるコード ---
def find_duplicates_bad(items: list[str]) -> list[str]:
    """重複する要素を見つける（アンチパターン）"""
    duplicates = []
    for i, item in enumerate(items):
        if item in items[i + 1:]:       # O(n) の検索が毎回
            if item not in duplicates:   # O(n) の検索が毎回
                duplicates.append(item)
    return duplicates
    # 全体の計算量: O(n^3) ← 壊滅的に遅い
 
 
# --- 修正後のコード ---
def find_duplicates_good(items: list[str]) -> list[str]:
    """重複する要素を見つける（改善版）"""
    seen: set[str] = set()
    duplicates: set[str] = set()
    for item in items:
        if item in seen:          # O(1) の検索
            duplicates.add(item)  # O(1) の挿入
        else:
            seen.add(item)        # O(1) の挿入
    return list(duplicates)
    # 全体の計算量: O(n) ← 線形時間
 
 
# --- 性能差の検証 ---
import time
import random
import string
 
def generate_random_strings(n: int, length: int = 5) -> list[str]:
    """ランダムな文字列リストを生成"""
    return ["".join(random.choices(string.ascii_lowercase, k=length))
            for _ in range(n)]
 
if __name__ == "__main__":
    random.seed(42)
    for size in [100, 1_000, 5_000]:
        data = generate_random_strings(size, length=3)
 
        start = time.perf_counter()
        result_bad = find_duplicates_bad(data)
        t_bad = time.perf_counter() - start
 
        start = time.perf_counter()
        result_good = find_duplicates_good(data)
        t_good = time.perf_counter() - start
 
        print(f"n={size:>5,}: "
              f"list方式={t_bad:.4f}s, set方式={t_good:.6f}s, "
              f"比率={t_bad/max(t_good, 1e-9):.0f}倍")

# ============================================================
# アンチパターン: 過剰な最適化
# ============================================================
 
# --- 問題のあるコード: 設定値の管理に B+木を使う ---
# 設定項目は多くても数十件程度
# B+木の実装コストと保守コストが見合わない
 
# class ConfigStore:
#     def __init__(self):
#         self._btree = BPlusTree(order=4)  # 数十件のデータに B+木...
#
#     def get(self, key: str) -> str:
#         return self._btree.search(key)
#
#     def set(self, key: str, value: str) -> None:
#         self._btree.insert(key, value)
 
 
# --- 修正後のコード: 単純な dict で十分 ---
class ConfigStore:
    """アプリケーション設定の管理（数十件程度を想定）"""
 
    def __init__(self):
        self._config: dict[str, str] = {}
 
    def get(self, key: str, default: str = "") -> str:
        return self._config.get(key, default)
 
    def set(self, key: str, value: str) -> None:
        self._config[key] = value
 
    def get_all(self) -> dict[str, str]:
        return dict(self._config)

# --- アンチパターン ---
queue_bad: list[int] = list(range(10_000))
while queue_bad:
    item = queue_bad.pop(0)  # O(n) × n 回 = O(n^2)
 
# --- 修正 ---
from collections import deque
queue_good: deque[int] = deque(range(10_000))
while queue_good:
    item = queue_good.popleft()  # O(1) × n 回 = O(n)

# --- アンチパターン ---
# 何の構造なのか、型が不明、typo に気づけない
user = {
    "profile": {
        "name": "Alice",
        "address": {
            "city": "Tokyo",
            "zip": "100-0001"
        }
    },
    "settings": {
        "notifications": {
            "email": True,
            "push": False
        }
    }
}
# user["profile"]["adress"]["city"]  # typo に気づけない（KeyError）
 
# --- 修正: データクラスを使う ---
from dataclasses import dataclass
 
@dataclass
class Address:
    city: str
    zip_code: str
 
@dataclass
class NotificationSettings:
    email: bool = True
    push: bool = False
 
@dataclass
class UserProfile:
    name: str
    address: Address
 
@dataclass
class UserSettings:
    notifications: NotificationSettings
 
@dataclass
class User:
    profile: UserProfile
    settings: UserSettings
 
# 型チェッカーが typo を検出してくれる
user_obj = User(
    profile=UserProfile(
        name="Alice",
        address=Address(city="Tokyo", zip_code="100-0001")
    ),
    settings=UserSettings(
        notifications=NotificationSettings(email=True, push=False)
    )
)
print(user_obj.profile.address.city)  # IDE の補完が効く

# --- アンチパターン ---
WEEKDAYS = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
# 誰かが WEEKDAYS.append("Holiday") すると全体が壊れる
 
# --- 修正 ---
WEEKDAYS = ("Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun")
# tuple は不変なので append できない → 安全

def count_common_elements(list_a: list[int], list_b: list[int]) -> int:
    """2 つのリストの共通要素数を数える（改善前）"""
    count = 0
    for item in list_a:
        if item in list_b:  # ← ボトルネック: O(n) × m 回
            count += 1
    return count

from collections import defaultdict
 
# --- dict の場合: 明示的な初期化が必要 ---
word_count_dict: dict[str, int] = {}
for word in ["apple", "banana", "apple", "cherry", "banana", "apple"]:
    if word not in word_count_dict:
        word_count_dict[word] = 0
    word_count_dict[word] += 1
# または dict.get() を使う
# word_count_dict[word] = word_count_dict.get(word, 0) + 1
 
# --- defaultdict の場合: 初期化不要 ---
word_count_dd: defaultdict[str, int] = defaultdict(int)
for word in ["apple", "banana", "apple", "cherry", "banana", "apple"]:
    word_count_dd[word] += 1  # キーが存在しなければ int() = 0 が自動生成
 
# --- Counter の場合: さらに簡潔 ---
from collections import Counter
word_count_counter = Counter(["apple", "banana", "apple", "cherry",
                               "banana", "apple"])
print(word_count_counter.most_common(2))  # [('apple', 3), ('banana', 2)]

import sys
 
# メモリ比較
lst = [1, 2, 3, 4, 5]
tpl = (1, 2, 3, 4, 5)
print(f"list: {sys.getsizeof(lst)} bytes")  # list: 104 bytes (目安)
print(f"tuple: {sys.getsizeof(tpl)} bytes")  # tuple: 80 bytes (目安)

# 順序が保証されない例
s = {3, 1, 4, 1, 5, 9, 2, 6}
print(s)  # {1, 2, 3, 4, 5, 6, 9} ← この順序は保証されない
 
# 順序が必要な場合の選択肢:
# 1. ソート済みリストに変換
sorted_list = sorted(s)  # [1, 2, 3, 4, 5, 6, 9]
 
# 2. 挿入順を保持したい場合は dict.fromkeys()
ordered_unique = list(dict.fromkeys([3, 1, 4, 1, 5, 9, 2, 6]))
print(ordered_unique)  # [3, 1, 4, 5, 9, 2, 6]（挿入順を保持）

import heapq
 
# --- 最小ヒープ（そのまま） ---
min_heap: list[int] = []
for val in [5, 3, 8, 1, 9]:
    heapq.heappush(min_heap, val)
print(heapq.heappop(min_heap))  # 1（最小値）
 
# --- 最大ヒープ（符号反転） ---
max_heap: list[int] = []
for val in [5, 3, 8, 1, 9]:
    heapq.heappush(max_heap, -val)  # 符号反転して格納
print(-heapq.heappop(max_heap))  # 9（最大値）
 
# --- Top-K（最大の K 個を取得）---
data = [5, 3, 8, 1, 9, 2, 7, 4, 6]
top_3 = heapq.nlargest(3, data)    # [9, 8, 7]
bottom_3 = heapq.nsmallest(3, data)  # [1, 2, 3]