Java 算法#

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

比较向量元素#

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

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

2. 排序比较:这种类型的比较有三种可能的结果:less than, equal 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 个最小值。 org.apache.arrow.algorithm.sort.IndexSorter 支持索引排序,该排序在 O(nlog(n)) 时间内运行。 它适用于任何类型的向量。

其他算法#

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