chrom   pos       ref  alt  gene
chr1    12345     A    G    GENE_A
chr1    67890     C    T    GENE_B
chr7    55211     G    A    GENE_C
...  (数百万～数十億行)

def find_linear(records, chrom, pos):
    hits = []
    for r in records:
        if r["chrom"] == chrom and r["pos"] == pos:
            hits.append(r)
    return hits

db = VariantIndex(records)  # インデックスを1回構築

db.get("chr1", 12345)  # 正確な検索 → 即時
db.range("chr1", 10000, 20000)  # 範囲検索 → 即時

=== 検索性能（変異50万件） ===
正確な検索（線形スキャン）：0.0180秒/件
正確な検索（ハッシュインデックス）：0.0000009秒/件 ← 約2万倍
範囲検索（線形スキャン）：0.0210秒/件
範囲検索（二分探索）：0.0000254秒/件 ← 約800倍
インデックス構築（1回）：0.32秒

バリアントインデックス（VariantIndex）
   ┌──────────────────────────────────────────────────────────────┐
   │  [入力] テーブル読み込み ────────── 部品：ファイル入出力     │  ← 完成品として提供（ツール）
   │              │                                               │
   │      ┌───────┴────────┐                                      │
   │      ▼                ▼                                      │
   │  [正確検索]       [範囲検索]                                 │
   │  ハッシュテーブル        ソート + 二分探索                   │
   │  部品：ハッシュテーブル   部品：二分探索                     │  ← どちらも自作 ★
   │      │                │                                      │
   │      └───────┬────────┘                                      │
   │              ▼                                               │
   │  [意味] これがまさにDBインデックス ── 部品：DBインデックス   │  ← 自作 ★
   └──────────────────────────────────────────────────────────────┘

import random

random.seed(1)
chroms = ["chr1", "chr2", "chr7"]

def make_records(n):
    recs = []
    for i in range(n):
        recs.append({
            "chrom": random.choice(chroms),
            "pos": random.randint(1, 1_000_000),
            "ref": random.choice("ACGT"),
            "alt": random.choice("ACGT"),
            "gene": f"GENE_{i % 500}",
        })
    return recs

records = make_records(50000)
assert len(records) == 50000
assert set(r["chrom"] for r in records) <= {"chr1", "chr2", "chr7"}

from collections import defaultdict

def build_hash_index(records):
    """(chrom, pos) → その位置の変異リスト。"""
    index = defaultdict(list)
    for r in records:
        index[(r["chrom"], r["pos"])].append(r)
    return index

hash_index = build_hash_index(records)

def get_exact(hash_index, chrom, pos):
    return hash_index.get((chrom, pos), [])

# 検証: ハッシュ検索の結果は、線形スキャン結果と完全に同じである必要がある
sample = records[12345]
linear = find_linear(records, sample["chrom"], sample["pos"])
hashed = get_exact(hash_index, sample["chrom"], sample["pos"])
assert hashed == linear
assert len(get_exact(hash_index, "chr1", -999)) == 0     # 存在しない位置は空のリスト

import bisect

def build_range_index(records):
    """chromごとに位置をソートする。(ソートされた pos 配列、それに対応するレコード配列)"""
    by_chrom = defaultdict(list)
    for r in records:
        by_chrom[r["chrom"]].append(r)
    index = {}
    for chrom, recs in by_chrom.items():
        recs.sort(key=lambda r: r["pos"])          # 位置順にソート (構築時に1回)
        positions = [r["pos"] for r in recs]
        index[chrom] = (positions, recs)
    return index

range_index = build_range_index(records)

def get_range(range_index, chrom, start, end):
    if chrom not in range_index:
        return []
    positions, recs = range_index[chrom]
    lo = bisect.bisect_left(positions, start)       # start が入る位置 (O(log n))
    hi = bisect.bisect_right(positions, end)        # end の次の位置
    return recs[lo:hi]                              # その間を一度に切り出す

# 検証: 二分探索の範囲の結果が、線形フィルタの結果と一致しなければならない (個数・内容)
def range_linear(records, chrom, start, end):
    return [r for r in records if r["chrom"] == chrom and start <= r["pos"] <= end]

bs = get_range(range_index, "chr1", 100000, 200000)
lin = range_linear(records, "chr1", 100000, 200000)
assert len(bs) == len(lin)
assert sorted(r["pos"] for r in bs) == sorted(r["pos"] for r in lin)
# 境界を含むかの確認: start と end 自体も含まれなければならない (bisect_left/right の組み合わせ)
assert all(100000 <= r["pos"] <= 200000 for r in bs)

class VariantIndex:
    def __init__(self, records):
        self.records = records
        self.hash_index = build_hash_index(records)  # 正確な検索用
        self.range_index = build_range_index(records)  # 範囲検索用

    def get(self, chrom, pos):
        return get_exact(self.hash_index, chrom, pos)

    def range(self, chrom, start, end):
        return get_range(self.range_index, chrom, start, end)

db = VariantIndex(records)

# 2つの検索は、どちらも線形スキャンと同じ結果になるはず
s = records[999]
assert db.get(s["chrom"], s["pos"]) == find_linear(records, s["chrom"], s["pos"])
assert len(db.range("chr2", 0, 1_000_000)) == len(range_linear(records, "chr2", 0, 1_000_000))

import time

records = make_records(200000)
db = VariantIndex(records)
targets = [(r["chrom"], r["pos"]) for r in random.sample(records, 200)]

# 完全一致検索：線形 vs ハッシュ
t0 = time.time()
for c, p in targets: find_linear(records, c, p)
linear_time = time.time() - t0

t0 = time.time()
for c, p in targets: db.get(c, p)
hash_time = time.time() - t0

print(f"完全一致検索 200件 — 線形：{linear_time:.4f} 秒")
print(f"完全一致検索 200件 — ハッシュ：{hash_time:.6f} 秒")
assert hash_time < linear_time