Java 算法¶
Arrow 的 Java 库为一些常用功能提供了算法。这些算法位于 algorithm 模块的 org.apache.arrow.algorithm 包中。
向量元素比较¶
比较向量元素是许多算法的基础。向量元素可以通过以下两种方式之一进行比较：
1. 相等性比较：此类比较有两种可能的结果：相等 (equal) 和 不等 (unequal)。目前，此类比较通过 org.apache.arrow.vector.compare.VectorValueEqualizer 接口提供支持。
2. 顺序比较：此类比较有三种可能的结果：小于 (less than)、等于 (equal to) 和 大于 (greater than)。此比较由抽象类 org.apache.arrow.algorithm.sort.VectorValueComparator 提供支持。
我们提供了用于比较向量元素的默认实现。不过，用户也可以定义自定义的比较方式。
向量元素搜索¶
搜索算法旨在在向量中查找特定值。如果成功，则返回向量索引；否则返回 -1。目前提供以下搜索算法：
1. 线性搜索：该算法简单地从头开始遍历向量，直到找到匹配项或到达向量末尾。因此，它的时间复杂度为 O(n)，其中 n 是向量中的元素数量。该算法在 org.apache.arrow.algorithm.search.VectorSearcher#linearSearch 中实现。
2. 二分搜索：这代表了一种更高效的搜索算法，其运行时间为 O(log(n))。但是，它仅适用于已排序的向量。要获得已排序的向量，可以使用我们在下一节中讨论的排序算法。该算法在 org.apache.arrow.algorithm.search.VectorSearcher#binarySearch 中实现。
3. 并行搜索：当向量较大时，遍历元素以搜索值会耗费很长时间。为了加快此过程，可以将向量拆分为多个分区，并并行执行每个分区的搜索。这由 org.apache.arrow.algorithm.search.ParallelSearcher 支持。
4. 范围搜索：在许多场景中，向量中可能存在多个匹配值。如果向量已排序，则匹配值位于向量的连续区域内。范围搜索算法尝试在 O(log(n)) 时间内找到该区域的上限/下限。实现由 org.apache.arrow.algorithm.search.VectorRangeSearcher 提供。
向量排序¶
给定一个向量，排序算法将其转换为已排序的向量。排序标准必须由某种顺序比较操作指定。排序算法可分为以下几类：
1. 原地排序器 (In-place sorter)：原地排序器通过操作原始向量进行排序，而不创建任何新向量。因此，它在排序操作后仅返回原始向量。目前，我们有 org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter 用于以 O(nlog(n)) 的时间进行原地排序。顾名思义，它仅支持定宽向量。
2. 异地排序器 (Out-of-place sorter)：异地排序器不会更改原始向量。相反，它会将向量元素按排序顺序复制到新向量中，并返回新向量。我们分别针对定宽和变宽向量提供了 org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter.FixedWidthOutOfPlaceVectorSorter 和 org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter.VariableWidthOutOfPlaceVectorSorter。这两种算法的运行时间均为 O(nlog(n))。
3. 索引排序器 (Index sorter)：此排序器实际上并不对向量进行排序。相反，它返回一个整数向量，对应于已排序顺序的向量元素索引。有了索引向量，就可以轻松构造出排序后的向量。此外，还可以轻松实现其他任务，例如查找向量中第 k 小的值。索引排序由 org.apache.arrow.algorithm.sort.IndexSorter 支持，其运行时间为 O(nlog(n))。它适用于任何类型的向量。
其他算法¶
其他算法包括 algorithm 模块中的向量去重、字典编码等。