Scala或Java數據結構用於自定義「非嚴格」排序

我有一組具有不同等同性和排序語義的項目。例如。Scala或Java數據結構用於自定義「非嚴格」排序

class Item( 
    val uid: String, // equality 
    val score: Int // sorting 
)

我需要的是讓某些集合中的項目總是按分數排序。獎金有一個快速查找/成員資格檢查平等（如散列/樹）。

等項目可以有不同的分數，所以我不能在分數相等（即使用一種樹/散列圖）前加相等。

關於scala或java std集合組合的任何想法都可以通過最小編碼來實現？ :)

來源

2012-03-29 tuxSlayer

我最終的東西，如：SortedSet的用於整理的表示+地圖（ID - >項目）爲會員/平等。所以我可以首先找出哪些元素是新的/出現在「集合」中，然後添加新的元素來映射和設置。通過這種方式，我已經對視圖進行排序並嚴格平等然而，它看起來不是很好:( – tuxSlayer 2012-03-29 13:43:41

我不能只用於設置成員資格，因爲沒有辦法從集合中獲取實體，我只能擁有包含（）true爲false。 – tuxSlayer 2012-03-29 13:44:40

你是如何處理的情況下你添加一個已經在集合中但有不同分數的項目嗎？ – Nicolas 2012-03-29 13:54:24

我可能會使用SortedSet，因爲他們已經排序。正如Woot4Moo指出的，你可以創建自己的Comparable（儘管我會建議使用Scala的ordering）。如果您將該順序作爲參數傳遞給SortedSet，則Set將爲您排序所有內容 - SortedSets總是排序。

注：這是隱含參數，你會想，所以可能是這個樣子：

val ordering = Ordering[...] 
val set = SortedSet(1, 2, 3, ... n)(ordering)

注意給出的排序

來源

2012-03-29 12:47:55

+1至少在這個解決方案中，你不需要調整'equals'。 – Nicolas 2012-03-29 13:08:28

這裏有同樣的概率。 Scala中的SortedSet默認impl是TreeSet，它使用排序來實現相等...這就是爲什麼我問:) – tuxSlayer 2012-03-29 13:11:08

我不太確定你在問什麼。你正在尋找集合的另一個實現或多哈希問題的特定解決方案嗎？ – 2012-03-29 17:38:08

一種可能性是建立自己的項目Set最後一個參數，包裝既SortedMap[Int, Set[Item]]（訂貨）和HashSet[Item]（用於訪問性能：

class MyOrderedSet(items: Set[Item], byPrice: collection.SortedMap[Int, Set[Item]]) extends Set[Item] { 

    def contains(key: Item) = items contains key 

    def iterator = byPrice map {_._2.iterator} reduceOption {_ ++ _} getOrElse Iterator.empty 

    def +(elem: Item) = 
    new MyOrderedSet(items + elem, byPrice + (elem.score -> (byPrice.getOrElse(elem.score, Set.empty) + elem))) 

    def -(elem: Item) = 
    new MyOrderedSet(items - elem, byPrice + (elem.score -> (byPrice.getOrElse(elem.score, Set.empty) - elem))) 

    // override any other methods for your convenience 
} 

object MyOrderedSet { 
    def empty = new MyOrderedSet(Set.empty, collection.SortedMap.empty) 

    // add any other factory method 
}

莫迪集fication是痛苦的，因爲你同步的2個集，但你想要的所有功能都沒有（至少我希望如此）

一個簡單的例子：

scala> MyOrderedSet.empty + Item("a", 50) + Item("b", 20) + Item("c", 100) 
res44: MyOrderedSet = Set(Item(b,20), Item(a,50), Item(c,100))

也有一個小缺點，這實際上不涉及到擬議的結構：您可以檢查的項目是在集，但你不能得到它的價值：在API中

scala> res44 contains Item("a", 100) 
res45: Boolean = true

沒有什麼可以讓你獲得Item("a", 50)結果。如果你想這樣做，我建議Map[String, Item]而不是Set[Item]items（當然，要相應地更改代碼）。

編輯：對於更加好奇，這裏是項目來一發書面版本，我用：

case class Item(id: String, score: Int) { 
    override def equals(y: Any) = 
    y != null && { 
     PartialFunction.cond(y) { 
     case Item(`id`, _) => true 
     } 
    } 
}

來源

2012-03-29 13:41:23 Nicolas

Scala或Java數據結構用於自定義「非嚴格」排序

回答

相關問題