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

621–630 of 772 posts

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

#621

Post by okennedy »

H8crilA wrote: post #23
okennedy wrote: post #13

Linked Hash/Tree Maps, simple, but elegant. A Map with its nodes connected in a linked list so you can traverse them in insertion order (and O(n) time). Very useful for window queries over sequential data and other cases where you want FIFO access, but also quick access by a field of the data.

You forgot the most important feature over normal hash maps: they offer a deterministic iteration order without incurring the cost of a tree-based ordered map. (If you don't know why this is important then maybe you haven't worked on large systems that undergo rigorous evaluation)

Modulo the snark, you're completely right. Iteration order = insertion order is super valuable for a bunch of reasons (this one included).

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

#622

Post by hn_throwaway_99 »

Shorel wrote: post #345
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…

I know this as memoization with lazy evaluation, nothing new, but at the same time very useful, and I would argue, it is very CS.

not really quite lazy evaluation, thought, at least in Javascript. Promises begin execution as soon as they are created and there is no way to delay that.

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

#623

Post by kevinforrestcon »

lolinder wrote: post #535
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…

This is a great solution to the thundering herd problem, but isn't OP explicitly trying to cache the results for later? In that case, the promise map is a clever way to make sure the cachable value is fetched at most once, and you want the keys to build up in the map, so GC'ing them is counterproductive.

If the result of the async function is not necessarily the same value every time you call it, you may want to recompute it

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

#624

Post by okennedy »

andyferris wrote: post #126
ztorkelson wrote: post #57

Earlier quoted context omitted.

Is (non-)determinism really the right concern here? I’m aware that most hash tables do not have generally predictable iteration orders, but I nevertheless understood them to be deterministic.

Well, hard/impossible to predict perhaps. Iteration order can depend on the order things were inserted and deleted and may differ from computer to computer (for example in Julia the hash-based dictionary ordering differs between 32 and 64 bit systems, and might change between versions of Julia, etc - you’d see the same thing with C++ unordered maps, etc, etc).

The same thing was a huge issue in Python until somewhere around 3.6, until they canonicalized the sort order.

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

#625

Post by Sesse__ »

sicp-enjoyer wrote: post #549
Sesse__ wrote: post #406

Earlier quoted context omitted.

> Ironically, due to caches, sorting and then using algorithms that rely on order tend to be superior than most hashing implementations This doesn't match my experience at all. C++ trees are not cache-friendly; they're pointer-chasing (and there's no arena implementation in the STL). Second, any sort of ordering structure (be it through a tree or through sorting + binary search) is notoriously prone to branch mispred…

> C++ trees are not cache-friendly Agreed, they should use a B-tree to get cache locality and easy generics, but there is legacy code there. I was referring to the performance of algorithms. For example `std::unique`, `std::lower_bounds`, etc. Many of these use sorted lists, whereas most other languages' standard libraries utilize hashing for these. > is also comfortably ahead of something like std::lower_bound on a…

B-trees don't work well for CPU caches; 64b lines are typically too small to gain much. (OK, the M1 has 128b lines, but still.) And you still get the branch mispredicts, and a significant increase in code complexity, so hashing is still significantly better. (I've seen C++ projects where the main structure was a B+-tree because the lower levels could be residing on disk, but where they maintained a separate hash table in memory to skip the top first few B-tree levels!)

> I would be interested to learn more about when that's the case. But, it's also not very flexible. You can put an `int` in it, great. Can you put `std::pair` in it? Does it work as well?

If by “it” you're talking about std::unordered_map (as key); yes, you can, but you'd have to supply your own hash function, because std::pair does not have a std::hash specialization. (It's a bit sad, but the problem is highly specific to std::pair/std::tuple.) Likewise, you can use any arbitrary type you create yourself, as long as it has operator== and you've written a hash function for it.

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

#626

Post by kelseyfrog »

I am enamored by data structures in the sketch/summary/probabilistic family: t-digest[1], q-digest[2], count-min sketch[3], matrix-sketch[4], graph-sketch[5][6], Misra-Gries sketch[7], top-k/spacesaving sketch[8], &c.

What I like about them is that they give me a set of engineering tradeoffs that I typically don't have access to: accuracy-speed[9] or accuracy-space. There have been too many times that I've had to say, "I wish I could do this, but it would take too much time/space to compute." Most of these problems still work even if the accuracy is not 100%. And furthermore, many (if not all of these) can tune accuracy to by parameter adjustment anyways. They tend to have favorable combinatorial properties ie: they form monoids or semigroups under merge operations. In short, a property of data structures that gave me the ability to solve problems I couldn't before.

I hope they are as useful or intriguing to you as they are to me.

1. https://github.com/tdunning/t-digest

2. https://pdsa.readthedocs.io/en/latest/rank/qdigest.html

3. https://florian.github.io/count-min-sketch/

4. https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketc...

5. https://www.juanlopes.net/poly18/poly18-juan-lopes.pdf

6. https://courses.engr.illinois.edu/cs498abd/fa2020/slides/20-...

7. https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf

8. https://www.sciencedirect.com/science/article/abs/pii/S00200...

9. It may better be described as error-speed and error-space, but I've avoided the term error because the term for programming audiences typically evokes the idea of logic errors and what I mean is statistical error.

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

#627

Post by pjscott »

efortis wrote: post #204
pjscott wrote: post #199

Earlier quoted context omitted.

No hardware multipliers here: left shifts are handled by much cheaper hardware [1], and are almost part of the basic arithmetic logic unit taught in school -- it can do addition, subtraction, bitwise operations, shifts by one, and maybe shifts by any number less than their word size. [1] https://en.wikipedia.org/wiki/Barrel_shifter

Multiplexer (not multiplier)

My mistake! They look so similar.

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

#628

Post by TristanBall »

silverlake wrote: post #73

Most of the data structures posted here are taught in CS classes. Here’s an interesting list of more obscure ones: https://web.stanford.edu/class/cs166/handouts/090%20Suggeste...

Not all of us got (cough any) CS degrees though, and while technically the information is all out there for me to find, I wouldn't necessarily have a reason to look, or on those rare occasions where my sysadmin/DBA projects do throw up a problem that one of these algorithms/structures are suited for - I wouldn't know _to_ look, or even how.

That's possibly one of the better arguments for doing a CS degree actually, at least for me. But 20 years ago when I might have cared, CS was always advertised as "you'll learn data structures and algorithms" and that's it. ( 20 yr old me: "I know loops and recursion, linked lists, some basic trees and oh look this "perl" thing has hashes, meh I'll be fine" )

If they'd listed out the sort of descriptions I've seen here.. well, I might have had a very different life!

So I'm absolutely loving this thread!

And thankyou for your link too, added to my list.

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

#629

Post by nathas »

Hashed time wheels: https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-...

Great for short-lived values in a cache that are frequently accessed. If all of your values always have the same expiration period (i.e. expires at insert time + N period) then it's super efficient.

More or less you have an array with a head and tail. Every "tick" (usually each second but you can customize it) you move the read pointer ahead by 1 array slot. The tail is then evicted.

If you have a highly accessed part of your code, you can be lazy and avoid using an extra thread and just tick ahead the read pointer when the time changes.

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

#630

Post by dragonwriter »

epolanski wrote: post #513
JimDabell wrote: post #475

Earlier quoted context omitted.

You can put the promise into the cache immediately but you can only put the result from the promise into the cache once the promise resolves. So if an identical request comes in a second time before the promise has been resolved, then if you are caching the promise you have a cache hit but if you are caching the result then you have a cache miss and you end up doing the work twice.

I am still not understanding the purpose of this as I believe it is grounded on the wrong assumption. Pretty much every single asynchronous operation other than some `Promise.resolve(foo)` where foo is a static value can fail. Reading from the file system, calling an api, connecting to some database, etc. If the original promise fails you're gonna return a cached failure. Mind you, I'm not stating this might be compl…

> If the original promise fails you're gonna return a cached failure.

In many cases, another near-in-time request would also fail, so returning a cached failure rather than failing separately is probably a good idea (if you need retry logic, you do it within the promise, and you still need only a single instance.)

(If you are in a system with async and parallel computation both available, you can also use this for expensive to compute pure functions of the key.)

Post reply on HN