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` 模块中。