gpt4 book ai didi

scala - Scala 中的 Union-Find(或 Disjoint Set)数据结构

转载 作者:行者123 更新时间:2023-12-01 07:33:34 25 4
gpt4 key购买 nike

在我尝试推出自己的优化之前,我正在寻找 Scala 中联合查找或不相交集数据结构的现有实现,因为优化看起来有些复杂。

我是说 this类似的东西 - unionfind 这两个操作被优化了。

有人知道任何现存的东西吗?我显然尝试过谷歌搜索。

最佳答案

前段时间我为自己写了一个我认为表现不错的。与其他实现不同,findO(1)unionO(log(n))。如果您有比 find 更多的 union 操作,那么这可能不是很有用。我希望你觉得它有用:

package week2

import scala.collection.immutable.HashSet
import scala.collection.immutable.HashMap

/**
* Union Find implementaion.
* Find is O(1)
* Union is O(log(n))
* Implementation is using a HashTable. Each wrap has a set which maintains the elements in that wrap.
* When 2 wraps are union, then both the set's are clubbed. O(log(n)) operation
* A HashMap is also maintained to find the Wrap associated with each node. O(log(n)) operation in mainitaining it.
*
* If the input array is null at any index, it is ignored
*/
class UnionFind[T](all: Array[T]) {
private var dataStruc = new HashMap[T, Wrap]
for (a <- all if (a != null))
dataStruc = dataStruc + (a -> new Wrap(a))

var timeU = 0L
var timeF = 0L

/**
* The number of Unions
*/
private var size = dataStruc.size

/**
* Unions the set containing a and b
*/
def union(a: T, b: T): Wrap = {
val st = System.currentTimeMillis()
val first: Wrap = dataStruc.get(a).get
val second: Wrap = dataStruc.get(b).get
if (first.contains(b) || second.contains(a))
first
else {
// below is to merge smaller with bigger rather than other way around
val firstIsBig = (first.set.size > second.set.size)
val ans = if (firstIsBig) {
first.set = first.set ++ second.set
second.set.foreach(a => {
dataStruc = dataStruc - a
dataStruc = dataStruc + (a -> first)
})
first
} else {
second.set = second.set ++ first.set
first.set.foreach(a => {
dataStruc = dataStruc - a
dataStruc = dataStruc + (a -> second)
})
second
}
timeU = timeU + (System.currentTimeMillis() - st)
size = size - 1
ans
}
}

/**
* true if they are in same set. false if not
*/
def find(a: T, b: T): Boolean = {
val st = System.currentTimeMillis()
val ans = dataStruc.get(a).get.contains(b)
timeF = timeF + (System.currentTimeMillis() - st)
ans
}

def sizeUnion: Int = size

class Wrap(e: T) {
var set = new HashSet[T]
set = set + e

def add(elem: T) {
set = set + elem
}

def contains(elem: T): Boolean = set.contains(elem)
}
}

关于scala - Scala 中的 Union-Find(或 Disjoint Set)数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17409641/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com