It must be [CHAMP](https://blog.acolyer.org/2015/11/27/hamt/#:~:text=CHAMP%20st....). Acronym for Compressed Hash-Array Mapped Prefix-tree. It is a current state of the art persistent hashtable. I'm surprised that no one mentioned this before, because it is super useful!
Ask HN: What are some cool but obscure data structures you know about?
571–580 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#572Purely Functional Data Structures[1] by Chris Okasaki is worth reading. There's a book version if you prefer vs reading a thesis. Even though the domain application is functional programming, these datastructures can come in handy when you want to enable state sharing / keeping old versions around without having to copy data. [1] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf
I loved the "Numerical Representations" chapter, on deriving new data structures by analogy to number bases.
Re: Ask HN: What are some cool but obscure data structures you know about?
#573Not 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…
What do you mean by first class citizen, here? I’m pretty sure this works in all languages with promises, but I might be misunderstanding something.
Re: Ask HN: What are some cool but obscure data structures you know about?
#574Not 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…
Can someone explain to me why the second example is better. To me it seems to be the same thing. Replace result with int and I literally do not see a problem with the first one. Also why is a mutex or lock needed for Result in javascript? As far as I know... In a single threaded application, mutexes and locks are only needed for memory operations on two or more results. With a single value, say an int, within javascr…
Wait a minute.
Under Javascript, The behavior induced by this pattern is EXACTLY equivalent to that of CACHING the result directly and a BLOCKING call. The pattern is completely pointless if you view it from that angle. Might as well use blocking calls and a regular cache rather then async calls and cached promises.
So then the benefit of this pattern is essentially it's a way for you to turn your async functions into cached non-async functions.
Is this general intuition correct?
--edit: It's not correct. Different async functions will still be in parallel. It's only all blocking and serial under the multiple calls to the SAME function.
Re: Ask HN: What are some cool but obscure data structures you know about?
#575Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…
I spent a long time looking at an algorithm for long range force calculations called the Fast Multipole Method which is O(N) and found that practically it couldn't compete against an O(N log N) method we used that involved FFTs because the coefficient was so large that you'd need to simulate systems way bigger than is feasible in order for it to pay off because of cache locality, etc.
Honestly, that is not too uncommon. For top level algorithm choice analysis, "rounding" O(log(n)) to O(1), and O(n*log(n)) to O(n), is often pretty reasonable for algorithm comparison, even though it is strictly incorrect.
It is not uncommon for a simple O(n*log(n)) algorithm to beat out a more complex O(n) algorithm for realistic data sizes. If you "round" them to both O(n), then picking the simpler algorithm because the obvious choice, and can easily turn out to have better perf.
Re: Ask HN: What are some cool but obscure data structures you know about?
#576Earlier quoted context omitted.
A fantastic thing about HyperLogLog is that it can be merged, so you can split your data between multiple server, precompute HLL for all IPs every minute, and then ask "how many unique IPs was there yesterday". Discovered HLL because it's used in ClickHouse, which employ a ton of cool but obscure data structure.
Works well in analytics cubes since they can be combined. You can retain them across time too, such that you can ask questions like "how many unique users were there over the last N days?" without needing the source data. Great for privacy-aware analytics solutions.
Love DataSketches but I was wondering if there is a way to compute datasketches across time for e.g. I want to compute the users who did X and then Y in that order. Since intersection is commutative it doesnt give an answer for time ordering.
Nonetheless the best data structure I have read over last 10 years.
Re: Ask HN: What are some cool but obscure data structures you know about?
#577Earlier quoted context omitted.
Could you use a WeakMap for this instead?
If the key is a type that you expect to be GC'ed, yes, totally. If the key is a simple value type eg a string then it behaves the same as a regular Map or an object.
Ah yeah, good point.
I've mostly used this overall pattern with something like Dataloader, where you throw away the entire cache on every request, so the GC problem doesn't crop up.
Re: Ask HN: What are some cool but obscure data structures you know about?
#578Succinct data structures in general are interesting. They use close to the information theoretic bound for a given problem and still support fast operations -- a decent mental model is that they're able to jump to a roughly correct place and (de)compress the data locally.
A good example is a wavelet tree. Suppose you have a text of length N comprised of an alphabet with C characters and wish to execute full-text pattern searches for patterns of length P. Once the tree is created, you can do your full-text search in O(P log C) time, and you use less space than any constant multiplicative factor of the information theoretic lower bound. Note that the runtime is independent of the original string's length.
Re: Ask HN: What are some cool but obscure data structures you know about?
#579Earlier 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.
Ya it obviously depends on the intended goal, but caching items in a map indefinitely better be done on a set of values that is known to be limited to a certain size over the lifetime of the server or it'll lead to a memory leak.
Re: Ask HN: What are some cool but obscure data structures you know about?
#580Earlier quoted context omitted.
I was experimenting a while ago with something that I think is related to this. If you have a quadratic algorithm where you need to compare each pair of objects in a large array of objects, you might use a loop in a loop like this: for (int i = 0; i When this algorithm runs, it will access every cache line or memory page in the array for each item, because j goes through the whole array for each i. I thought that a b…
I decided to try implement get_gray_xy. I am wondering how you can generalise it to any number of loops and apply it to nested loops of varying sizes, that is if you have three sets and the sizes are 8, 12, 81. Wikipedia says graycodes can be found by num ^ (num >> 1) a = [1, 2, 3, 4] b = [2, 4, 8, 16] indexes = set() correct = set() print("graycode loop indexes") for index in range(0, len(a) * len(b)): code = index…
Here is the implementation of get_gray_xy that I used:
static uint64_t deinterleave(uint64_t x) {
x = x & 0x5555555555555555;
x = (x | (x >> 1)) & 0x3333333333333333;
x = (x | (x >> 2)) & 0x0f0f0f0f0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff0000ffff;
x = (x | (x >> 16)) & 0x00000000ffffffff;
return x;
}
static void get_gray_xy(uint64_t n, uint64_t *x, uint64_t *y) {
uint64_t gray = n ^ (n >> 1);
*x = deinterleave(gray);
*y = deinterleave(gray >> 1);
}
But it does work for different number of dimensions or different number of nested loops. For 3 dimensions each coordinate is constructed from every 3rd bit instead of 2nd.
So if you have index 14, then gray code is 9 (1001) which means in two dimensions x=1,y=2 and in three dimensions, x=3,y=0,z=0.