Java 算法#

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

比较向量元素#

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

1. 相等比较:此类比较有两种可能的结果:equalunequal。目前,此类比较通过 org.apache.arrow.vector.compare.VectorValueEqualizer 接口支持。

2. 排序比较:此类比较有三种可能的结果:less thanequal togreater than。此比较由抽象类 org.apache.arrow.algorithm.sort.VectorValueComparator 支持。

我们提供了比较向量元素的默认实现。但是,用户也可以定义自定义比较方式。

向量排序#

给定一个向量,排序算法将其转换为排序向量。排序标准必须由某些排序比较操作指定。排序算法可以分为以下类别:

1. 就地排序器:就地排序器通过操作原始向量来执行排序,而不会创建任何新向量。因此它在排序操作后只返回原始向量。目前,我们有 org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter 用于在 O(nlog(n)) 时间内就地排序。顾名思义,它只支持固定宽度向量。

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

3. 索引排序器:此排序器实际上不会对向量进行排序。相反,它返回一个整数向量,它对应于向量元素在排序顺序中的索引。使用索引向量,可以轻松构建排序向量。此外,一些其他任务也可以轻松实现,例如在向量中查找第 k``th smallest value in the vector. Index sorting is supported by ``org.apache.arrow.algorithm.sort.IndexSorter,它在 O(nlog(n)) 时间内运行。它适用于任何类型的向量。

其他算法#

其他算法包括向量去重、字典编码等,位于 algorithm 模块中。