Java 演算法

Arrow 的 Java 程式庫為一些常用的功能提供演算法。這些演算法在 algorithm 模組的 org.apache.arrow.algorithm 套件中提供。

比較向量元素

比較向量元素是許多演算法的基礎。向量元素可以透過以下兩種方式之一進行比較

1. 相等性比較：這種類型的比較有兩種可能的結果：相等 和 不相等。目前，這種類型的比較透過 org.apache.arrow.vector.compare.VectorValueEqualizer 介面支援。

2. 排序比較：這種類型的比較有三種可能的結果：小於、等於 和 大於。這種比較由抽象類別 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 模組中。