Java 算法#
Arrow 的 Java 库提供了某些常用功能的算法。这些算法在 org.apache.arrow.algorithm 包的 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 模块中。