Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What are some cool but obscure data structures you know about?

news.ycombinator.com

Post reply on HN
Print view View original

751–760 of 772 posts

Re: Ask HN: What are some cool but obscure data structures you know about?

#751

Post by cl0rkster »

cl0rkster wrote: post #750
TristanBall wrote: post #644

Earlier quoted context omitted.

I think you managed too lose me about 3 times in there.. what point are you trying to make, and what do you think Linus should do?

I think if there's an intelligence gap between a guy who needs a tailor made retreat that costs more than my entire earnings potential for my lifetime to learn... DON'T BE AN ASSHOLE... SOMEONE WHO DOESN'T CARE WILL PUNCH YOU... I think humanity needs new heroes

Linus is a pussy nerd and he's brilliant... But that is not a reflection of society.

Re: Ask HN: What are some cool but obscure data structures you know about?

#752

Post by loxias »

lorenzhs wrote: post #698
loxias wrote: post #64

(Fantastic post idea OP. One of the best I've ever seen :D) Related to bloom filters, xor filters are faster and more memory efficient, but immutable. HyperLogLog is an efficient way to estimate cardinality. Coolest thing I've learned recently was Y-fast trie. If your dataset M is bounded integers (say, the set of all 128 bit numbers), you get membership, predecessor, or successor queries in log log time, not log, li…

If you enjoyed XOR filters, you might also like ribbon filters, something that I had the pleasure of working on last year. They share the basic idea of using a system of linear equations, but instead of considering 3 random positions per key, the positions to probe are narrowly concentrated along a ribbon with a typical width of 64. This makes them far more cache-efficient to construct and query. By purposefully over…

This made my day, thank you so much. :) Your explanation makes sense and it sounds brilliant/clever yet obvious. (like many good ideas are)

I'm reading the paper and looking at your github now, and look forward to "github/academia" stalking you in the future. Skimming your list of repositories and seeing a lot of stuff I understand and could possibly use. ;-)

(I find it to be a useful strategy to, when I find a clever concept in a paper, or in code on github, then look at all the other things done by the same person, or the works of people they co-author with. "collaborative filtering" for ideas.)

Re: Ask HN: What are some cool but obscure data structures you know about?

#753

Post by KETpXDDzR »

Locality-sensitive hashing[0] is similar to bloom filters. It's a hashing function that hashes values into buckets. One interesting application is neutral networks with sparse inputs.

[0] https://en.m.wikipedia.org/wiki/Locality-sensitive_hashing

Re: Ask HN: What are some cool but obscure data structures you know about?

#754

Post by nurettin »

skrebbel wrote: post #297

Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…

>> Not a very deep CS-y one

yes, in fact this is more like a pattern than an actual data structure, since you might as well replace it with a list of futures. And a comparison between future based concurrency and thread based parallelism is like apples to oranges.

But it isn't surprising that this pattern ended up at the top since it is what the users of this site would be most familiar with.

Re: Ask HN: What are some cool but obscure data structures you know about?

#755

Post by charleslmunger »

Fiahil wrote: post #606
charleslmunger wrote: post #567

Earlier quoted context omitted.

I think this can be done completely lock free with almost same number of memory barriers as a mutex when writing - read the tail pointer (acquire), append your node using CAS(release), then update the tail pointer with CAS (release). For reads, start with an acquire read of the tail pointer, which will make all preceding writes to the list visible to you. Then you can read the list all you want up until you hit the n…

> read the tail pointer (acquire) > append your node using CAS(release) > update the tail pointer with CAS (release). I thought as well, but, when I wrote that impl there was no way to shortcut the 2 releases into a single atomic operation. That ended up creating forks or loosing blocks. I tested that model and a few variations with loom ( https://docs.rs/loom/latest/loom/ ), so I'm confident that it didn't work. How…

Another option that makes appends cheaper would be to use a Treiber stack (one acquire, one release!), but maintain a separate path for readers. When pushing, do a read (acquire) of the tail, then set (relaxed) a back link on the second-from-top element pointing to the current top, then CAS (release) to push your node. Since the back link will always write the same value, it's ok for contending writers to submit racing writes.

Readers start by reading the tail(acquire) and storing a pointer to the node before it. They then traverse from head until they reach the node before the tail, then skip reading its back link pointer (as they already know it will point to the tail).

Re: Ask HN: What are some cool but obscure data structures you know about?

#757

Post by nunez »

patricia tries are cool. used them once while working on an infrastructure management tool; makes searching word dictionaries very efficient.

also love the Option struct with pattern matching that all of the hippie-dippie functional languages seem to like lol

Re: Ask HN: What are some cool but obscure data structures you know about?

#758

Post by kizer »

thaumasiotes wrote: post #193
kizer wrote: post #184

Earlier quoted context omitted.

If at some point you have a cycle, you can then reparent and remove the cycle, right? This structure in general then can encode transitive relations effectively? Something like “a and b …” “b and c …” “c and a …”.

> If at some point you have a cycle, you can then reparent and remove the cycle, right? You'd never have a cycle. The way a cycle would theoretically arise would have to be joining something to its own child. But you don't naively join the two objects you're given - you find their root objects, and join those. If - as would be necessary for a cycle to form - they have the same root, you can return without doing anyth…

Thanks!

Re: Ask HN: What are some cool but obscure data structures you know about?

#759

Post by icsa »

HelloNurse wrote: post #400
icsa wrote: post #352

[Ordered] Minimal Perfect Hash Functions with O(N) construction time. They have been around for 30 years and I don't see them used in practice.

Fixed key sets are uncommon.

Many assets associated with a program or system are fixed/readonly/constant data. Slowly changing key sets can also take advantage of Minimal Perfect Hashing.

Re: Ask HN: What are some cool but obscure data structures you know about?

#760

Post by ranman »

twic wrote: post #388
tresil wrote: post #275

Earlier quoted context omitted.

Big fan of HLL Apache foundation has a fantastic DataSketches library that includes HLL and many other powerful data analytics algorithms: https://datasketches.apache.org/ Lee Rhodes has done an excellent introduction to this library - explaining some of the use cases, advantages, and things to be aware of when using these techniques: https://www.youtube.com/watch?v=nO9pauS-mGQ

On sketches, there is a genre of structure for estimating histogram-like statistics (median, 99th centile, etc) in fixed space, which i really like. Two examples: t-digest https://github.com/tdunning/t-digest DDSketch https://github.com/DataDog/sketches-java

t-digest is used by AWS X-ray to render their charts
Post reply on HN