文件 Heap.h

namespace faiss

实现了多种变体的 k-means 聚类。

此源代码根据 MIT 许可证获得许可，该许可证位于此源代码树的根目录下的 LICENSE 文件中。

IDSelector 旨在定义要处理的向量子集（用于删除或作为搜索的子集）

PQ4 SIMD 打包和累加函数

基本内核使用 bbs = nb * 2 * 16 向量累加 nq 查询向量，并为此生成一个输出矩阵。这对于 nq * nb <= 4 很有意义，否则寄存器溢出变得太大。

这些函数的实现分布在 3 个 cpp 文件中，以减少并行编译时间。模板被显式实例化。

此文件包含用于计算距离的内核的回调。

在整个库中，向量以 float * 指针的形式提供。当批量处理（添加/搜索）多个向量时，大多数算法都可以得到优化。在这种情况下，它们作为矩阵传入。当大小为 d 的 n 个向量作为 float * x 提供时，向量 i 的分量 j 为

x[ i * d + j ]

其中 0 <= i < n 且 0 <= j < d。换句话说，矩阵始终是紧凑的。在指定矩阵的大小时，我们称它为 n*d 矩阵，这意味着行优先存储。

I/O 函数可以读取/写入到文件名、文件句柄或抽象介质的对象。

读取函数返回应使用 delete 释放的对象。这些对象中的所有引用都归该对象所有。

倒排列表的定义 + 几个实现该接口的常用类。

由于 IVF（倒排文件）索引对于大规模用例非常有用，因此我们将与它们相关的一些函数分组到这个小库中。大多数函数都适用于 IndexIVF 和嵌入在 IndexPreTransform 中的 IndexIVF。

此文件中实现了 L2 和内积之外的额外指标

实现了一些神经网络层，主要用于支持 QINCo

定义了一些对向量集应用转换的对象。这些通常是预处理步骤。

Typedefs

typedef HeapArray<CMin<float, int64_t>> float_minheap_array_t

typedef HeapArray<CMin<int, int64_t>> int_minheap_array_t

typedef HeapArray<CMax<float, int64_t>> float_maxheap_array_t

typedef HeapArray<CMax<int, int64_t>> int_maxheap_array_t

函数

template<class C> inline void heap_pop(size_t k, typename C::T *bh_val, typename C::TI *bh_ids): 从由 bh_val[0..k-1] 和 bh_ids[0..k-1] 定义的堆中弹出顶部元素。输出时，k-1 处的元素是未定义的。

template<class C> inline void heap_push(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, typename C::T val, typename C::TI id): 将元素 (val, ids) 推入堆 bh_val[0..k-2] 和 bh_ids[0..k-2]。输出时，定义了 k-1 处的元素。

template<class C> inline void heap_replace_top(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, typename C::T val, typename C::TI id): 替换由 bh_val[0..k-1] 和 bh_ids[0..k-1] 定义的堆中的顶部元素，对于相同的 bh_val[] 值，也按 bh_ids[] 值排序。

template<typename T> inline void minheap_pop(size_t k, T *bh_val, int64_t *bh_ids)

template<typename T> inline void minheap_push(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<typename T> inline void minheap_replace_top(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<typename T> inline void maxheap_pop(size_t k, T *bh_val, int64_t *bh_ids)

template<typename T> inline void maxheap_push(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<typename T> inline void maxheap_replace_top(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<class C> inline void heap_pop(size_t k, std::pair<typename C::T, typename C::TI> *bh): 从由 bh_val[0..k-1] 和 bh_ids[0..k-1] 定义的堆中弹出顶部元素。输出时，k-1 处的元素是未定义的。

template<class C> inline void heap_push(size_t k, std::pair<typename C::T, typename C::TI> *bh, typename C::T val, typename C::TI id): 将元素 (val, ids) 推入堆 bh_val[0..k-2] 和 bh_ids[0..k-2]。输出时，定义了 k-1 处的元素。

template<class C> inline void heap_replace_top(size_t k, std::pair<typename C::T, typename C::TI> *bh, typename C::T val, typename C::TI id): 替换由 bh_val[0..k-1] 和 bh_ids[0..k-1] 定义的堆中的顶部元素，对于相同的 bh_val[] 值，也按 bh_ids[] 值排序。

template<class C> inline void heap_heapify(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, const typename C::T *x = nullptr, const typename C::TI *ids = nullptr, size_t k0 = 0)

template<typename T> inline void minheap_heapify(size_t k, T *bh_val, int64_t *bh_ids, const T *x = nullptr, const int64_t *ids = nullptr, size_t k0 = 0)

template<typename T> inline void maxheap_heapify(size_t k, T *bh_val, int64_t *bh_ids, const T *x = nullptr, const int64_t *ids = nullptr, size_t k0 = 0)

template<class C> inline void heap_addn(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, const typename C::T *x, const typename C::TI *ids, size_t n)

template<typename T> inline void minheap_addn(size_t k, T *bh_val, int64_t *bh_ids, const T *x, const int64_t *ids, size_t n)

template<typename T> inline void maxheap_addn(size_t k, T *bh_val, int64_t *bh_ids, const T *x, const int64_t *ids, size_t n)

template<typename C> inline size_t heap_reorder(size_t k, typename C::T *bh_val, typename C::TI *bh_ids)

template<typename T> inline size_t minheap_reorder(size_t k, T *bh_val, int64_t *bh_ids)

template<typename T> inline size_t maxheap_reorder(size_t k, T *bh_val, int64_t *bh_ids)

template<class C> inline void indirect_heap_pop(size_t k, const typename C::T *bh_val, typename C::TI *bh_ids)

template<class C> inline void indirect_heap_push(size_t k, const typename C::T *bh_val, typename C::TI *bh_ids, typename C::TI id)

template<class idx_t, class C> void merge_knn_results(size_t n, size_t k, typename C::TI nshard, const typename C::T *all_distances, const idx_t *all_labels, typename C::T *distances, idx_t *labels)

合并来自多个分片的查询结果表。假设每个分片的查询结果已经排序。请注意，C 比较器与通常的 top-k 元素堆相反，因为我们希望最好的（即 L2 最低的）结果位于顶部，而不是最差的。此外，它需要保存分片 ID 的索引（即通常 int32 已经足够）。

参数：

all_distances – 大小 (nshard, n, k)
all_labels – 大小 (nshard, n, k)
distances – 输出距离, 大小 (n, k)
labels – 输出标签, 大小 (n, k)

template<typename C> struct HeapArray

#include <Heap.h>

用于一组 [最小|最大] 堆的模板结构。它经过定制，因此堆的实际数据可以直接存储在紧凑的数组中。

公共类型

typedef C::TI TI

typedef C::T T

公共函数

inline T *get_val(size_t key): 返回堆的值列表。

inline TI *get_ids(size_t key): 对应的标识符。

void heapify(): 在添加之前准备所有堆

void addn(size_t nj, const T *vin, TI j0 = 0, size_t i0 = 0, int64_t ni = -1)

将nj个元素添加到堆 i0:i0+ni，具有顺序ID

参数：

nj – 要添加到每个堆的元素数量
vin – 要添加的元素，大小为 ni * nj
j0 – 将此添加到要添加的 ID
i0 – 要更新的第一个堆
ni – 要更新的元素数量 (-1 = 使用 nh)

void addn_with_ids(size_t nj, const T *vin, const TI *id_in = nullptr, int64_t id_stride = 0, size_t i0 = 0, int64_t ni = -1)

与 addn 相同

参数：

id_in – 要添加的元素的 ID，大小为 ni * nj
id_stride – id_in 的步长

void addn_query_subset_with_ids(size_t nsubset, const TI *subset, size_t nj, const T *vin, const TI *id_in = nullptr, int64_t id_stride = 0)

与 addn_with_ids 相同，但仅适用于查询的子集

参数：

nsubset – 要更新的查询条目的数量
subset – 要更新的查询的索引，范围为 0..nh-1，大小为 nsubset

void reorder(): 重新排序所有堆

void per_line_extrema(T *vals_out, TI *idx_out) const

这实际上不是堆函数。它只是查找数组 D 的每一行的每行极值

参数：

vals_out – 每行的极值 (大小为 nh，或 NULL)
idx_out – 极值的索引 (大小为 nh 或 NULL)

公共成员

size_t nh: 堆的数量

size_t k: 每个堆的分配大小

TI *ids: 标识符 (大小为 nh * k)

T *val: 值 (距离或相似度)，大小为 nh * k