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

361–370 of 772 posts

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

#361

Post by manuelabeledo »

nly wrote: post #324
manuelabeledo wrote: post #313

Concurrent tries with non-blocking snapshots [0] Say that you have a dataset that needs to be ordered, easily searchable, but is also updated quite frequently. Fast accesses are a pain if you decide to use traditional read-write locks. Ctries are entirely lock-free, thus there is no waiting for your read operations when an update is happening, i.e. you run lookups on snapshots while updates happen. They are also a lo…

Sounds like if you want a version of this that doesn't leak memory you need a garbage collected language?

Yeah, either that or you implement your own. Doing so with reference counts might not be too hard, though.

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

#362

Post by nly »

slazaro wrote: post #328

I don't know whether it already exists or if it has a name, but internally I call it Virtual List. - Reasoning: It's used in cases where you'd ideally use an array because you want contiguous memory (because you'll usually iterate through them in order), but you don't know beforehand how many elements you'll insert. But you can't use a resizeable version like std::vector, because it invalidates any pointers to the el…

So like a std::deque? If the block size varies then lookup will be O(log B) where B is the number of blocks.

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

#363

Post by turkeywelder »

Might not be very obscure but it was new to me. Ended up being really useful for finding out whether dates intersect a particular period and ended up using it quite a bit at work.

Range Tree:

https://en.wikipedia.org/wiki/Range_tree

You give it a range of dates and it'll tell you if any intersect so if you're looking for "how many people are absent in this time period" you can really quickly find out by using a range tree.

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

#364

Post by compressedgas »

Dwedit wrote: post #232

Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is…

Ted Nelson named them Enfilades. Guy Steele called them Monoid Cached Trees.

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

#365

Post by benou »

Very good idea!

And I love bloom filter too (and their more modern successor cuckoo filter) but I'd challenge the usecase you mention though: 1 million IPv4 is 4MB, and 16MB for IPv6. That's tiny, you're better off using some kind of hashtable, unless you have a fast and small memory, and then a slow and big memory (say embedded processor with small CPU cache and some DRAM).

Bloom filters are useful when your working set cannot fit in your fast memory, to allow you to go to the slow memory only for a small number of requests.

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

#366

Post by nly »

manuelabeledo wrote: post #361
nly wrote: post #324

Earlier quoted context omitted.

Sounds like if you want a version of this that doesn't leak memory you need a garbage collected language?

Yeah, either that or you implement your own. Doing so with reference counts might not be too hard, though.

The reference count on each element would presumably require atomic operations that could race with those used to update the actual data structure, and therefore you'd lose all your concurrency guarantees?

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

#367

Post by aidos »

jdthedisciple wrote: post #338
ralusek wrote: post #312

Earlier quoted context omitted.

I have written many tools that do something like this, very useful. Just gotta be careful with memory leaks, so (for a TS example) you might want to do something like this: const promiseMap > = new Map(); async function keyedDebounce (key: string, fn: () => R) { const existingPromise = promiseMap.get(key); if (existingPromise) return existingPromise; const promise = new Promise(async (resolve) => { const result = awa…

You check for if(promiseMap.get(key)) and in the NO case you do promiseMap.delete(key)? Could you explain why that's necessary? (sorry probs a stupid question)

I’m the no case, the promise is created, and then deleted after the function is resolved.

I’m not entirely sure of the use of this pattern where your using a map and deleting the keys as you go - seems like you’d end up doing more work kinda randomly depending on how the keys were added. I’d just relive the whole map when I was done with it.

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

#368

Post by FullyFunctional »

xxs wrote: post #323
FullyFunctional wrote: post #286

My absolute favorite, Cuckoo hashing, has been mentioned already, but so far (239 comment in) nobody has mention this approach (called?) to store an array A[] of N-bit numbers, most of which are zero or small: use N set of numbers S[N], such that for each A[I] you store I in S[J] where J are the bit positions where A[I] have a set bit. In other words, S[J] are the indices of elements from A that has a set bit in posi…

In practice Cuckoo sucks, b/c the reading from an unknown index in an array is not a const cost operation. It has an upper bound of course, but its average cost is quite different, depending if you are to hit L1, or L2... or just go for the a cache miss. "Cache misses" is what dominates performance nowadays.

Where I go there are no cache misses (it’s in hardware)

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

#369

Post by once_inc »

kcbanner wrote: post #182

"This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improveme…

Requires numbers inserted to be unsigned, and to have a maximum value within reason, and doubles memory usage.

Very nifty trick though!

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

#370

Post by HelloNurse »

mentater wrote: post #243
jtolmar wrote: post #171

The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.) The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged wi…

Wouldn't that be extremely useful and a polynomial solution for 3-SAT, which is NP complete?

SAT complexity results from blowing up a reasonable number of variables/clauses (very rarely equivalent to others) in the formula to an enormous number of variable assignments (too many to store, and having only three classes, formula true or false or not evaluated so far, that are not useful equivalencies). What disjoint sets are you thinking of tracking?
Post reply on HN