Scala：按照最有效的第三個值對（Int，Int，Int）的ListBuffer進行排序

我期望按最有效的第三個值排序ListBuffer(Int, Int, Int)。這是我目前擁有的。我正在使用sortBy。備註y和z都是ListBuffer[(Int, Int, Int)]，這是我首先考慮的區別。我的目標是優化這一點，並最有效地執行此操作（取兩個列表之間的區別並按第三個元素排序）。我假設diff部分不能優化，但sortBy可以，所以我正在尋找一種有效的方法來做排序部分。我發現在排序數組上的帖子，但我正在使用ListBuffer和轉換爲數組添加開銷，所以我寧願不轉換我的ListBuffer。Scala：按照最有效的第三個值對（Int，Int，Int）的ListBuffer進行排序

val x = (y diff z).sortBy(i => i._3)

來源

2016-11-20 Teodorico Levoff

1）如果你想使用Scala的庫，那麼你不能做的比這好得多。斯卡拉已經試圖以最有效的方式對你的收藏進行分類。 SeqLike定義def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f)調用該實施：

def sorted[B >: A](implicit ord: Ordering[B]): Repr = { 
    val len = this.length 
    val arr = new ArraySeq[A](len) 
    var i = 0 
    for (x <- this.seq) { 
     arr(i) = x 
     i += 1 
    } 
    java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]]) 
    val b = newBuilder 
    b.sizeHint(len) 
    for (x <- arr) b += x 
    b.result 
    }

這是你的代碼將被調用。正如你所看到的，它已經使用數組對數據進行排序。根據public static void sort(Object[] a)的javadoc：

實現注意事項：此實現了穩定的，自適應的，迭代歸併需要遠小於n LG更少（n）的比較當輸入陣列部分地排序，同時還提供了當輸入數組是隨機排列的時，表現傳統的合併排序。如果輸入數組幾乎排序，那麼執行大約需要n次比較。

2）如果試圖通過直接插入你的差異的結果到像一個二叉樹的有序結構，您可以通過元素產生這些要素進行優化，您仍需要支付相同的價格：平均成本的插入是log(n)次n元素= n log(n) - 與任何快速排序算法一樣，如合併排序。

3）因此，除非您針對特定用例進行優化，否則不能優化此情況。

3A）例如，ListBuffer可能與一個Set和diff更換要快很多。事實上，它的實現爲：

def diff(that: GenSet[A]): This = this -- that

它採用-這反過來應該是其必須首先建立一個地圖上Seq比diff快：

def diff[B >: A](that: GenSeq[B]): Repr = { 
    val occ = occCounts(that.seq) 
    val b = newBuilder 
    for (x <- this) 
     if (occ(x) == 0) b += x 
     else occ(x) -= 1 
    b.result 
    }

3B）您還可以避免排序通過使用_3作爲數組中的索引。如果使用該索引插入，則數組將被排序。這隻有在你的數據足夠密集或者你很樂意處理稀疏數組後纔有效。一個索引也可能有多個映射到它的值，你也必須處理它。有效地，你正在建立一個有序的地圖。您也可以使用Map，但不會對HashMap進行排序，並且TreeMap將需要log(n)再次進行添加操作。

諮詢Scala Collections Performance Characteristics瞭解您可以根據您的情況獲得什麼。

4）無論如何，在現代計算機上排序真的很快。做一些基準測試，以確保你不會過早地優化它。

總結複雜性不同的場景......

您當前的情況：

DIFF爲SeqLike：n創建從that + n地圖遍歷this（地圖查找是有效常數時間（C））= 2n或O(n)
sort - O(n log(n))
總= O(n) + O(n log(n)) = O(n log(n))，更準確的說：2n + nlog(n)

如果使用Set，而不是SeqLike：

DIFF爲Set：n迭代（查找是C）= O(n)
排序 - 相同
總計 - 相同：O(n) + O(n log(n)) = O(n log(n))，更確切地說：n + nlog(n)

如果使用Set和陣列插入：

差異 - 相同設置
排序 - 0 - 陣列由建設排序
總：O(n) + O(0) = O(n)，更準確的說： n。對於稀疏數據可能不太實際。

看起來像事物的宏偉計劃它並不重要，除非你有一個獨特的案例，從最後一個選項（數組）中受益。

如果你有一個ListBuffer[Int]而不是ListBuffer[(Int, Int, Int)]我會建議先對兩個集合進行排序，然後通過同時對它們進行一次遍歷來進行差異化。這將是O(nlog(n))。在你的情況下，按_3排序並不足以保證兩個系列中的確切順序。您可以按元組的所有三個字段進行排序，但會改變原始排序。如果你對此感到滿意並編寫自己的差異，那麼它可能是最快的選擇。

來源

2016-11-21 06:47:54

Scala：按照最有效的第三個值對（Int，Int，Int）的ListBuffer進行排序

回答

相關問題