lobsters score: 34 · tags: plt
Union finds can be implemented in different styles. An arena style or a refcell/pointer style.
What’s an “arena-style union find”? Is that where you use a separate dictionary that maps from node ID to the representative ID of its equivalence class? I guess that’s like an area in that you can control when that dictionary is freed.
score 2 · canonical
There are a couple different styles which amount to similar things. A common style is to have pointers or a refcell and you actually pointer chase up the union find. You call malloc or new to make a new union find variable. A different style is to use a vector and push on it when you want a new union find variable. The union find ids then reference an index inside this vector. A third style uses dictionaries, which can be nice if you don’t want to have uninterpretable ids. It also maybe makes more sense in a pure functional programming context. The latter two styles are easier to traverse, eagerly compress and serialize. The first style needs something like the magic abilities of a garbage collector to do that. I personally heavily prefer the second style
score 4 · canonical
phil zucker is a goldmine. sloppily presented and i don’t always agree, but anyone interested in compilers/optimisers/analysers/provers should take the time to understand everything he writes
score 7 · canonical