关于F#中可用的数据结构
是否有任何“官方”的实现不相交集数据结构,例如Union-Find的实现?
我在谷歌上找到的唯一信息是这些代码片段:
请注意,我是F#和编程的初学者。
有什么高效的替代方案吗?
关于F#中可用的数据结构
是否有任何“官方”的实现不相交集数据结构,例如Union-Find的实现?
我在谷歌上找到的唯一信息是这些代码片段:
请注意,我是F#和编程的初学者。
有什么高效的替代方案吗?
F# 数据结构
关于 F# 可用的数据结构,是否有“官方”的不相交集数据结构实现,例如 Union Find 的实现?
我不知道是否有官方版本。
F# 数据结构最著名的来源:
曾经有 F# PowerPack,它是一个包含大量有用代码的文件,但现在已被分解成部分。
请查看Jack Fox 的文章了解有关 F# 数据结构的重要信息。
对于特定领域的数据结构,请搜索F# 社区项目。
特别是对于 Union/Find:
在实用逻辑和自动推理手册中的lib.ml中,John Harrison定义了equate
和canonize
。
在lib.fs的F#翻译中,它们仍然是equate
和canonize
。
并且在翻译过程中的注释中提到:
请参见:不相交集合数据结构
请参见:自动推理中的主题 - 第5讲 - 第4页:并查集
union
被称为equate
。
find
被称为canonize
。
还有哪些高效的替代方法?
我不知道John Harrison的代码是否更高效,因为我没有运行过任何测试。我也不知道是否有其他实现,但我知道该版本可以很好地作为自动定理证明器核心的一部分。
// union find by rank with path compression
namespace UnionFind
// using array from 1..N
// don't use .[0]
type Node = { Parent:int ; Rank:int}
type Partition (N:int) =
let nodearray = [| for i in 0..N do yield {Parent = i; Rank = 0} |]
let length = (Array.length nodearray) - 1
member p.Item
with get(idx) = nodearray.[idx]
member p.find (i) =
let mutable tmp0 = i
let mutable tmp1 = p.[i].Parent
while (tmp0 <> tmp1) do tmp0 <- tmp1
tmp1 <- p.[tmp1].Parent
tmp0
member p.find_compress (i) :int =
let mutable tmp0 = i
let mutable tmp1 = p.[i].Parent
let rec one_step ok list =
match ok with
| false -> list
| true -> tmp0 <- tmp1
tmp1 <- p.[tmp1].Parent
one_step (tmp0<>tmp1) (tmp0::list)
let list = one_step (tmp0<>tmp1) [i]
// ranks stay the same with find_compress
list |> List.head |> (fun i -> let r = nodearray.[i].Rank
(nodearray.[i] <- {Parent = tmp0 ; Rank=r} ))
list |> List.tail |> List.iter ( fun i -> let r = nodearray.[i].Rank
(nodearray.[i] <- {Parent = tmp0 ; Rank=r} ))
tmp0
member p.union_by_rank (i,j) : bool = // returns false if i and j hav the same parent, true otherwise
if i=j then false else
let x = p.find_compress(i)
let y = p.find_compress(j)
let rx = p.[x].Rank
let ry = p.[y].Rank
if x=y then false else
if (rx<ry) then nodearray.[x] <- {Parent = y; Rank = rx}
if (ry<rx) then nodearray.[y] <- {Parent = x; Rank = ry}
if (rx=ry) then nodearray.[x] <- {Parent = y; Rank = ry}
nodearray.[y] <- {Parent = y; Rank = ry+1}
true
member p.print() =
printfn "%A" nodearray
member p.output() = [|for i in 0..length do yield (i,p.find_compress(i))|]