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``th smallest value in the vector. Index sorting is supported by ``org.apache.arrow.algorithm.sort.IndexSorter
,它在 O(nlog(n))
时间内运行。它适用于任何类型的向量。
其他算法#
其他算法包括向量去重、字典编码等,位于 algorithm
模块中。