स्काला

Question

में सामान्य तत्वों को सेट करने वाले सेट्स का मर्ज सेट करें, मैं स्कैला में एक फ़ंक्शन को कार्यान्वित करना चाहता हूं, कि, इट्स के सेट्स सेट के सेट को किसी एक सेट वाले विलय में एक या अधिक सामान्य तत्व शामिल होंगे।

इसलिए उदाहरण के लिए, यह देखते हुए:

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = ??? 

val sets = Set(Set(1,2), Set(2,3), Set(3,7), Set(8,10)) 
val mergedSets = mergeSets(sets) 

mergedSets सेट शामिल होगा (सेट (1,2,3,7), सेट (8,10))

क्या एक अच्छा होगा, यदि संभव हो तो कुशल और कार्यात्मक, स्कैला में ऐसा करने का तरीका?

Answer 1

यह करने के लिए सबसे कारगर तरीका परिवर्तनशील संरचनाओं का उपयोग किया जाएगा, लेकिन आप एक कार्यात्मक रास्ते के लिए कहा, तो यहाँ जाता है:

sets.foldLeft(Set.empty[Set[Int]])((cum, cur) => { 
    val (hasCommon, rest) = cum.partition(_ & cur nonEmpty) 
    rest + (cur ++ hasCommon.flatten) 
}) 

Answer 2

यह (जांची नहीं, इस फोन का उपयोग कर लिखा था) शायद सिर्फ samthebest के जवाब का एक प्रकार है, लेकिन विविधता की खातिर:

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = { 
    def hasIntersect(set: Set[Int]): Boolean = 
     sets.count(set.intersect(_).nonEmpty) > 1 

    val (merged, rejected) = sets partition hasIntersect 
    Set(merged.flatten, rejected.flatten) 
    } 

Answer 3

एक संस्करण काफी हद तक samthebest के जवाब की भावना में है कि है, लेकिन (डिजाइन) के द्वारा कम गहरा मुहावरेदार। यह उन नए कार्यात्मक प्रोग्रामिंग के लिए अधिक पहुंच योग्य हो सकता है। (ऐसा लगता है हम सब कुछ हम इस तरह के एक अच्छा समस्या से बाहर कर सकते हैं निचोड़ चाहिए।)

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = { 
    if (sets.isEmpty) { 
    Set.empty[Set[Int]] 
    } else { 
    val cur = sets.head 
    val merged = mergeSets(sets.tail) 
    val (hasCommon, rest) = merged.partition(_ & cur nonEmpty) 
    rest + (cur ++ hasCommon.flatten) 
    } 
} 

हालांकि, निम्नलिखित विकल्प पूंछ पुनरावर्ती और शायद यह भी samthebest के जवाब को समझने के लिए एक चिकनी पथ उपलब्ध कराने के होने का लाभ दिया गया है:

def mergeSets(cum: Set[Set[Int]], sets: Set[Set[Int]]): Set[Set[Int]] = { 
    if (sets.isEmpty) { 
    cum 
    } else { 
    val cur = sets.head 
    val (hasCommon, rest) = cum.partition(_ & cur nonEmpty) 
    mergeSets(rest + (cur ++ hasCommon.flatten), sets.tail) 
    } 
} 

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = 
    mergeSets(Set.empty[Set[Int]], sets) 

मैं इनमें से किसी एक को बेहतर नहीं मानता: सीखने के उपकरण के रूप में बस उपयोगी।

Answer 4

समथबेस्ट का टेर्स समाधान इसकी सादगी और लालित्य में बहुत संतोषजनक है, लेकिन मैं बड़ी संख्या में सेट के साथ काम कर रहा हूं और एक और अधिक प्रदर्शन करने वाला समाधान की आवश्यकता है जो अभी भी अपरिवर्तनीय है और अच्छी कार्यात्मक शैली में लिखी गई है।

प्रत्येक 10 तत्वों के साथ 10,000 सेट (यादृच्छिक रूप से 0 से 750,000 तक चुने गए इट्स) के लिए, सैमथेस्ट के टर्से समाधान ने मेरे कंप्यूटर पर औसत ~ 30sec लिया, जबकि मेरा समाधान औसत ~ 400ms पर लिया गया।

(मामले किसी को भी सोच रहा था में, ऊपर सेट cardinalities के लिए परिणामी सेट 3600 सेट, शामिल हैं ~ प्रत्येक ~ 26 तत्वों की औसत के साथ)

किसी को भी किसी भी सुधार देख सकते हैं अगर मैं शैली के संबंध में कर सकता है या प्रदर्शन, कृपया मुझे बताएं!

val sets = Set(Set(1, 2), Set(2, 3), Set(4, 5)) 
Association.associate(sets) => Set(Set(1, 2, 3), Set(4, 5)) 


object Association { 

    // Keep track of all current associations, as well as every element in any current association 
    case class AssociationAcc[A](associations: Set[Set[A]] = Set.empty[Set[A]], all: Set[A] = Set.empty[A]) { 
    def +(s: Set[A]) = AssociationAcc(associations + s, all | s) 
    } 

    // Add the newSet to the set associated with key A 
    // (or simply insert if there is no such key). 
    def updateMap[A](map: Map[A, Set[A]], key: A, newSet: Set[A]) = { 
    map + (key -> (map.getOrElse(key, Set.empty) ++ newSet)) 
    } 

    // Turn a Set[Set[A]] into a map where each A points to a set of every other A 
    // it shared any set with. 
    // 
    // e.g. sets = Set(Set(1, 2), Set(2, 3), Set(4, 5)) 
    //  yields: Map(1 -> Set(2), 2 -> Set(1, 3), 3 -> Set(2), 
    //     4 -> Set(5), 5 -> Set(4)) 
    def createAssociationMap[A](sets: Set[Set[A]]): Map[A, Set[A]] = { 
    sets.foldLeft(Map.empty[A, Set[A]]) { case (associations, as) => 
     as.foldLeft(associations) { case (assoc, a) => updateMap(assoc, a, as - a) } 
    } 
    } 

    // Given a map where each A points to a set of every A it is associated with, 
    // and also given a key A starting point, return the total set of associated As. 
    // 
    // e.g. with map = Map(1 -> Set(2), 2 -> Set(1, 3), 3 -> Set(2), 
    //      4 -> Set(5), 5 -> Set(4)) 
    // and key = 1 (or 2 or 3) yields: Set(1, 2, 3). 
    // with key = 4 (or 5) yields: Set(4, 5) 
    def getAssociations[A](map: Map[A, Set[A]], key: A, hit: Set[A] = Set.empty[A]): Set[A] = { 
    val newAssociations = map(key) &~ hit 
    newAssociations.foldLeft(newAssociations | hit + key) { 
     case (all, a) => getAssociations(map, a, all) 
    } 
    } 

    // Given a set of sets that may contain common elements, associate all sets that 
    // contain common elements (i.e. take union) and return the set of associated sets. 
    // 
    // e.g. Set(Set(1, 2), Set(2, 3), Set(4, 5)) yields: Set(Set(1, 2, 3), Set(4, 5)) 
    def associate[A](sets: Set[Set[A]]): Set[Set[A]] = { 
    val associationMap = createAssociationMap(sets) 
    associationMap.keySet.foldLeft(AssociationAcc[A]()) { 
     case (acc, key) => 
     if (acc.all.contains(key)) acc 
     else      acc + getAssociations(associationMap, key) 
    }.associations 
    } 
}