311–320 of 772 posts
I made https://github.com/mamcx/tree-flat as flattened stored tree in pre-order that allows for very fast iterations even for childs/parent queries. Is based on APL, so not that novel. I also like a lot the relational model, is not that much represented so I making a language on top of it: https://tablam.org .
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…
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 = await fn(); // ignore lack of error handling
// avoid memory leak by cleaning up
promiseMap.delete(key);
// this will call the .then or awaited promises everywhere
resolve(result);
});
promiseMap.set(key, promise);
return promise;
}
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 lot of fun to implement, especially if you aren't familiar with lock-free algorithms! I did learn a lot doing it myself [1]
[0] http://aleksandar-prokopec.com/resources/docs/ctries-snapsho...
Earlier quoted context omitted.
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)
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.
A massive one - there is a lot of code that implicitly depends on the order of iteration (think configurations/initialization). The issue might be invisible, and reproduce rarely in production only. The iteration order depends on the hash of the keys, plus the capacity of the underlying array.
In Java I advise to never use the standard HashMap in favor of LinkedHashMap. In cases where data density is important both are a terrible fit having nodes instead of a plain object array (and linear probe/search).
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…
Later on I switched to using react-query which has something like this built-in, it's been really good.
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.
Super effective way to store a searchable list of items, like a dictionary of words.
Monotonic stacks are neat. I made up a data structure once, consisting of a pyramid of deques. It lets you efficiently compute any associative function over a streaming window of data.
You may be interested in the work myself and some coauthors have done on data structures and algorithms for streaming aggregation. GitHub repo for the code, which high level descriptions of their properties and pointers to papers: https://github.com/IBM/sliding-window-aggregators
HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d comp…
So basically like HAMT but lock free.