Struct faiss::HeapArray

template<typename C>
struct HeapArray

a template structure for a set of [min|max]-heaps it is tailored so that the actual data of the heaps can just live in compact arrays.

Public Types

typedef C::TI TI
typedef C::T T

Public Functions

inline T *get_val(size_t key)

Return the list of values for a heap.

inline TI *get_ids(size_t key)

Correspponding identifiers.

void heapify()

prepare all the heaps before adding

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

add nj elements to heaps i0:i0+ni, with sequential ids

Parameters:

  • nj – nb of elements to add to each heap

  • vin – elements to add, size ni * nj

  • j0 – add this to the ids that are added

  • i0 – first heap to update

  • ni – nb of elements to update (-1 = use 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)

same as addn

Parameters:

  • id_in – ids of the elements to add, size ni * nj

  • id_stride – stride for 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)

same as addn_with_ids, but for just a subset of queries

Parameters:

  • nsubset – number of query entries to update

  • subset – indexes of queries to update, in 0..nh-1, size nsubset

void reorder()

reorder all the heaps

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

this is not really a heap function. It just finds the per-line extrema of each line of array D

Parameters:

  • vals_out – extreme value of each line (size nh, or NULL)

  • idx_out – index of extreme value (size nh or NULL)

Public Members

size_t nh

number of heaps

size_t k

allocated size per heap

TI *ids

identifiers (size nh * k)

T *val

values (distances or similarities), size nh * k