"""Optional compiled kernels (Numba). Falls back to NumPy when Numba is unavailable.""" import numpy as np try: from numba import njit, prange @njit(parallel=True, fastmath=True, cache=True) def _cand_assign_nb(X, C, cn, G, prev, out_l, out_d): n, d = X.shape m = G.shape[1] for i in prange(n): p = prev[i] best = np.inf bl = -1 xx = 0.0 for t in range(d): xx += X[i, t] * X[i, t] for jj in range(m): c = G[p, jj] s = cn[c] for t in range(d): s -= 2.0 * X[i, t] * C[c, t] if s < best: best = s bl = c out_l[i] = bl out_d[i] = max(best + xx, 0.0) @njit(parallel=True, fastmath=False, cache=True) def _fused_stats_nb(X, order, starts, labs, C, U, sums, counts, b_axis, b_proj): """Per-cluster sums, counts, sum (e.u) e and sum (e.u)^2 over rows sorted by label.""" nseg = len(starts) - 1 d = X.shape[1] for g in prange(nseg): j = labs[g] acc = np.zeros(d, np.float64); ax = np.zeros(d, np.float64); e = np.empty(d, np.float64) pp = 0.0 for t in range(starts[g], starts[g + 1]): i = order[t] p = 0.0 for q in range(d): v = X[i, q] acc[q] += v e[q] = v - C[j, q] p += e[q] * U[j, q] for q in range(d): ax[q] += p * e[q] pp += p * p for q in range(d): sums[j, q] += acc[q] b_axis[j, q] += ax[q] counts[j] += starts[g + 1] - starts[g] b_proj[j] += pp HAVE_NUMBA = True except Exception: # pragma: no cover HAVE_NUMBA = False def cand_assign(X, C, G, prev): """Nearest centroid among G[prev[i]] for every row i. Returns (dist, label).""" X = np.ascontiguousarray(X, dtype=np.float32) C = np.ascontiguousarray(C, dtype=np.float32) cn = (C.astype(np.float64) ** 2).sum(1).astype(np.float32) L = np.empty(len(X), np.int64); D = np.empty(len(X), np.float32) if HAVE_NUMBA: _cand_assign_nb(X, C, cn, np.ascontiguousarray(G, dtype=np.int64), prev.astype(np.int64), L, D) return D, L for s0 in range(0, len(X), 4096): r = slice(s0, s0 + 4096); cand = G[prev[r]]; xr = X[r] dist = (xr * xr).sum(1)[:, None] - 2 * np.einsum("bd,bmd->bm", xr, C[cand]) + cn[cand] j = dist.argmin(1); L[r] = cand[np.arange(len(j)), j]; D[r] = np.maximum(dist[np.arange(len(j)), j], 0) return D, L def cell_batched_assign(X, C, coarse, nprobe, cell_of=None): """Approximate nearest-centroid search with exactly the IVF candidate sets (each row compares with the centroids of its `nprobe` nearest coarse cells), computed as one dense BLAS matrix product per cell instead of per-row scans. X: (n, d) rows; C: (k, d) centroids; coarse: (L, d) coarse cell centres; cell_of: optional (k,) coarse cell of every centroid. Returns (squared dist, label).""" import faiss X = np.ascontiguousarray(X, dtype=np.float32); C = np.ascontiguousarray(C, dtype=np.float32) coarse = np.ascontiguousarray(coarse, dtype=np.float32) L = len(coarse) if cell_of is None: cell_of = faiss.knn(C, coarse, 1)[1][:, 0] _, qcell = faiss.knn(X, coarse, nprobe) # (n, nprobe) probed cells cn = (C * C).sum(1) xn = (X * X).sum(1) best = np.full(len(X), np.inf, np.float32); lab = np.full(len(X), -1, np.int64) flat = qcell.ravel(); rows = np.repeat(np.arange(len(X)), nprobe) order = np.argsort(flat, kind="stable"); flat, rows = flat[order], rows[order] qstart = np.searchsorted(flat, np.arange(L + 1)) corder = np.argsort(cell_of, kind="stable"); cstart = np.searchsorted(cell_of[corder], np.arange(L + 1)) for j in range(L): q = rows[qstart[j]:qstart[j + 1]]; cj = corder[cstart[j]:cstart[j + 1]] if len(q) == 0 or len(cj) == 0: continue d = cn[cj][None, :] - 2.0 * (X[q] @ C[cj].T) # (|q|, |cj|) via BLAS a = d.argmin(1); v = d[np.arange(len(q)), a] better = v < best[q] best[q[better]] = v[better]; lab[q[better]] = cj[a[better]] miss = lab < 0 if miss.any(): # rows whose cells were empty d0, l0 = faiss.knn(X[miss], C, 1); best[miss] = d0[:, 0] - xn[miss]; lab[miss] = l0[:, 0] return np.maximum(best + xn, 0.0), lab def cell_centric_assign(X, C, coarse, nprobe, cell_of=None): """Approximate nearest-centroid search where all rows of a coarse cell share one candidate set: the centroids in the `nprobe` coarse cells nearest to that cell's centre. One large BLAS product per cell. Returns (squared dist, label).""" import faiss X = np.ascontiguousarray(X, dtype=np.float32); C = np.ascontiguousarray(C, dtype=np.float32) coarse = np.ascontiguousarray(coarse, dtype=np.float32) L = len(coarse) if cell_of is None: cell_of = faiss.knn(C, coarse, 1)[1][:, 0] _, near = faiss.knn(coarse, coarse, min(nprobe, L)) # cell -> nearby cells _, qc = faiss.knn(X, coarse, 1); qc = qc[:, 0] cn = (C * C).sum(1); xn = (X * X).sum(1) corder = np.argsort(cell_of, kind="stable"); cstart = np.searchsorted(cell_of[corder], np.arange(L + 1)) qorder = np.argsort(qc, kind="stable"); qstart = np.searchsorted(qc[qorder], np.arange(L + 1)) best = np.empty(len(X), np.float32); lab = np.empty(len(X), np.int64) for j in range(L): q = qorder[qstart[j]:qstart[j + 1]] if len(q) == 0: continue cand = np.concatenate([corder[cstart[c]:cstart[c + 1]] for c in near[j]]) d = (X[q] @ C[cand].T); d *= -2.0; d += cn[cand][None, :] a = d.argmin(1) best[q] = d[np.arange(len(q)), a]; lab[q] = cand[a] return np.maximum(best + xn, 0.0), lab def fused_stats(X, labels, C, U, sums, counts, b_axis, b_proj): """One pass over a batch: e-means' cluster sums and counts plus PISCES' axis statistics.""" order = np.argsort(labels, kind="stable") lab = labels[order] labs, starts = np.unique(lab, return_index=True) starts = np.append(starts, len(lab)).astype(np.int64) if HAVE_NUMBA: _fused_stats_nb(np.ascontiguousarray(X, dtype=np.float32), order.astype(np.int64), starts, labs.astype(np.int64), C, U, sums, counts, b_axis, b_proj) return e = X - C[labels]; p = np.einsum("ij,ij->i", e, U[labels]) np.add.at(sums, labels, X); counts += np.bincount(labels, minlength=len(C)) b_axis[labs] += np.add.reduceat((e * p[:, None])[order], starts[:-1], axis=0) b_proj += np.bincount(labels, weights=p.astype(np.float64) ** 2, minlength=len(C))