探索アルゴリズム入門：線形検索からベクトル検索・量子探索まで

import time, random, bisect
n = 10_000_000data = sorted(random.random() for _ in range(n))target = data[n // 2]   # 中央の値を探す
# 線形（リストの index ＝ O(n)）t0 = time.perf_counter()data.index(target)print(f"線形: {time.perf_counter() - t0:.4f} s")
# 二分（O(log n)）t0 = time.perf_counter()bisect.bisect_left(data, target)print(f"二分: {time.perf_counter() - t0:.4f} s")

import time, random
n = 10_000_000keys = list(range(n))random.shuffle(keys)d = {k: i for i, k in enumerate(keys)}   # ハッシュテーブル構築
t0 = time.perf_counter()for _ in range(100_000):    _ = d[random.randint(0, n-1)]   # O(1) アクセスprint(f"100,000 回のハッシュ検索: {time.perf_counter()-t0:.3f} s")

from collections import deque
# 0=通路, 1=壁。S=start, G=goal は座標でmaze = [    [0,0,1,0,0],    [1,0,1,0,1],    [0,0,0,0,0],    [0,1,1,1,0],    [0,0,0,0,0],]start, goal = (0, 0), (4, 4)
def bfs(maze, start, goal):    H, W = len(maze), len(maze[0])    q = deque([(start, [start])])    seen = {start}    while q:        (r, c), path = q.popleft()        if (r, c) == goal:            return path        for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:            nr, nc = r+dr, c+dc            if 0 <= nr < H and 0 <= nc < W and maze[nr][nc] == 0 and (nr,nc) not in seen:                seen.add((nr,nc))                q.append(((nr,nc), path + [(nr,nc)]))    return None
path = bfs(maze, start, goal)print("最短経路:", path)

import numpy as np
# 仮の文書ベクトル（本来は埋め込みモデルで作る）docs = {    "犬は哺乳類": np.array([0.9, 0.1, 0.0, 0.2]),    "猫は哺乳類": np.array([0.85, 0.15, 0.0, 0.25]),    "魚は脊椎動物": np.array([0.1, 0.0, 0.9, 0.05]),    "鳥は脊椎動物": np.array([0.2, 0.0, 0.85, 0.1]),    "石は鉱物": np.array([0.0, 0.9, 0.0, 0.0]),}
def cosine(a, b):    return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
# 「ペット」っぽいクエリベクトルquery = np.array([0.88, 0.12, 0.0, 0.22])
scored = sorted(docs.items(), key=lambda kv: cosine(query, kv[1]), reverse=True)for name, v in scored:    print(f"{cosine(query, v):.3f}  {name}")