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