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. 原地排序器：原地排序器通过操作原始向量来执行排序，而无需创建任何新向量。因此，它只是在排序操作后返回原始向量。目前，我们有 org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter 用于在 O(nlog(n)) 时间内进行原地排序。顾名思义，它仅支持固定宽度的向量。

2. 异地排序器：异地排序器不会改变原始向量。相反，它按排序顺序将向量元素复制到新向量，并返回新向量。我们有 org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter.FixedWidthOutOfPlaceVectorSorter 和 org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter.VariableWidthOutOfPlaceVectorSorter 分别用于固定宽度和可变宽度向量。两种算法都在 O(nlog(n)) 时间内运行。

3. 索引排序器：此排序器实际上并不对向量进行排序。相反，它返回一个整数向量，该向量对应于排序顺序中向量元素的索引。使用索引向量，可以轻松构建排序向量。此外，还可以轻松完成其他一些任务，例如查找向量中的第 k 个最小值。 org.apache.arrow.algorithm.sort.IndexSorter 支持索引排序，该排序在 O(nlog(n)) 时间内运行。它适用于任何类型的向量。

其他算法#

其他算法包括向量去重、字典编码等，都在 algorithm 模块中。