스칼라의 공통 요소를 포함하는 집합의 병합 집합

Question

하나 이상의 공통 요소를 포함하는 포함 집합을 병합하는 Set of Ints 집합이 주어지면 Scala에서 함수를 구현하고 싶습니다.

이 그래서 예를 들어, 주어진 :

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

Samthebest의 간결한 솔루션은 단순함과 우아함이 매우 만족 스럽지만 많은 수의 세트로 작업하고 있으며 여전히 기능이 부족한 스타일로 작성된 더 우수한 솔루션이 필요합니다.

각각 10 개 요소 (무작위로 선택된 0 ~ 750,000의 정수)가있는 10,000 세트의 경우 samthebest의 간결한 솔루션은 내 컴퓨터에서 평균 ~ 30 초가 걸렸지 만 아래 솔루션은 평균 ~ 400ms가 걸렸습니다.

사람이 어떤 개선을 볼 수 있다면

나는 스타일에 대한 만들 수 (사람이 궁금 경우, 위의 설정 카디널리티에 대한 결과 집합 ~ 26 개 요소의 평균 각각 ~ 3600 개 세트 포함) 또는 성능, 알려 주시기 바랍니다! (필터에 괄호에 _ 당신은 할 수 없습니다) 컴파일되지 않습니다

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 
    } 
}