Java 算法

Arrow 的 Java 库为一些常用功能提供算法。这些算法位于 algorithm 模块的 org.apache.arrow.algorithm 包中。

比较向量元素

比较向量元素是许多算法的基础。向量元素可以通过以下两种方式之一进行比较：

1. 相等性比较：这种类型的比较有两种可能的结果：相等 和 不相等。目前，这种比较通过 org.apache.arrow.vector.compare.VectorValueEqualizer 接口支持。

2. 排序比较：这种类型的比较有三种可能的结果：小于、等于 和 大于。这种比较由抽象类 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 模块中。