10 · 向量检索与 ANN

   用户向量 u (64 维)
   物品向量 v₁, v₂, ..., v₁₀₀₀₀₀₀₀₀ (各 64 维)

   要找：和 u 点积最大的前 1000 个

   暴力算法：
     1 亿次点积 × 64 次乘法 = 64 亿次浮点运算
     单核 CPU ≈ 几秒钟
     ❌ 超预算 100 倍以上

# pip install faiss-cpu     (GPU 版: faiss-gpu)
import faiss
import numpy as np

d = 64                                  # 向量维度
n = 1_000_000                           # 物品数
item_vecs = np.random.random((n, d)).astype('float32')

# ⭐ 关键：内积检索前必须 L2 归一化，这样内积 = 余弦相似度
faiss.normalize_L2(item_vecs)

# ---------- 方案 A：小规模（< 10 万），直接暴力 ----------
index = faiss.IndexFlatIP(d)            # IP = Inner Product
index.add(item_vecs)

# ---------- 方案 B：中大规模，IVF ----------
nlist = 4096                            # 聚类中心数，经验值 ≈ 4*sqrt(n)
quantizer = faiss.IndexFlatIP(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_INNER_PRODUCT)
index.train(item_vecs)                  # ⭐ IVF 必须先训练（学聚类中心）
index.add(item_vecs)
index.nprobe = 32                       # ⭐ 查几个簇。这是精度-速度旋钮

# ---------- 方案 C：HNSW，追求低延迟 ----------
index = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT)
index.hnsw.efConstruction = 200
index.add(item_vecs)
index.hnsw.efSearch = 64                # ⭐ 线上调这个

# ---------- 方案 D：超大规模 + 内存紧张，IVF-PQ ----------
m, nbits = 8, 8                         # 分 8 段，每段 8 bit → 8 字节/向量
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, nbits)
index.train(item_vecs)
index.add(item_vecs)

# ---------- 查询（都一样） ----------
user_vec = np.random.random((1, d)).astype('float32')
faiss.normalize_L2(user_vec)
scores, ids = index.search(user_vec, k=100)
print("Top-10 物品 ID:", ids[0][:10])

# ---------- 保存 / 加载 ----------
faiss.write_index(index, "items.index")
index = faiss.read_index("items.index")

# pip install hnswlib
import hnswlib

index = hnswlib.Index(space='cosine', dim=64)
index.init_index(max_elements=1_000_000, ef_construction=200, M=32)
index.add_items(item_vecs, ids=np.arange(n))
index.set_ef(64)                        # 查询精度旋钮

labels, distances = index.knn_query(user_vec, k=100)

def measure_recall(ann_index, exact_index, queries, k=100):
    """ANN 找出的 top-k 里，有多少在暴力检索的 top-k 里"""
    _, ann_ids   = ann_index.search(queries, k)
    _, exact_ids = exact_index.search(queries, k)

    recalls = [len(set(a) & set(e)) / k for a, e in zip(ann_ids, exact_ids)]
    return np.mean(recalls)

# 典型目标：Recall@100 ≥ 0.95，同时 P99 延迟 < 10ms

   Recall@100
    1.0 ┤                    ╭────────
    0.95┤              ╭─────╯   ← 通常这里性价比最高
    0.9 ┤        ╭─────╯
    0.8 ┤   ╭────╯
    0.6 ┤╭──╯
        └┬────┬────┬────┬────┬────► 延迟(ms)
         1    2    5    10   20

  1 亿向量 × 64 维 × 4 字节 (float32) = 25.6 GB   ← 光向量
  HNSW 的图结构还要额外 ~M×8 字节/向量 ≈ +25 GB
  ────────────────────────────────────────
  总计 ~50 GB → 需要大内存机器或分片

  用 PQ 压缩后：1 亿 × 8 字节 = 0.8 GB  ✅ 单机轻松