News for hackers. Stuff that matters.

A comment on Ask HN: What are some cool but obscure data structures you know about?.

Re:Ask HN: What are some cool but obscure data structures yo... by kaymanb on Thursday July 21, 2022 @07:22PM (#32186495)
Disjoint-Sets have a very cool implementation whose amortized time complexity is extremely slow growing. It is not quite constant, but even for a disjoint-set with as many elements as there are particles in the universe, the amortized cost of an operation will be less than or equal to 4.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by andreareina on Friday July 22, 2022 @12:29AM (#32188543)
Use the idea[1] at work to make large NP-complete problems more tractable by breaking the problem up into disjoint subsets.

[1] doesn't implement the inverse-ackermann algorithm but still implemented as union/find.

[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by kragen on Friday July 22, 2022 @02:51AM (#32189280)
aka "union find" — some other comments in the thread call it that
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by EnderShadow8 on Thursday July 21, 2022 @08:46PM (#32187148)
I've been told to consider it constant for all practical purposes
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by pjscott on Thursday July 21, 2022 @11:41PM (#32188246)
The inverse Ackermann function is one of the slowest-growing functions that you’re ever likely to encounter in the wild. To say that it’s “constant for all practical purposes” is 100% true but doesn’t do justice to how amazingly slow this function is to grow.

https://en.m.wikipedia.org/wiki/Ackermann_function

[ Parent | on HN ]