411–420 of 772 posts
See https://en.wikipedia.org/wiki/Palindrome_tree and the original paper
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…
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…
Won’t JS garbage collect orphaned references? Why is this necessary?
Some ones I've used recently: The "golden section search" to find a the minimum (or maximum) of a unimodal function. An actual real-world use case for the golden ratio. Exponentially Weighted Moving Average filters. Or how to have a moving average without saving any data points.. Some of my classic favorites: Skiplists: they are sorted trees, but the algorithms are low complexity which is nice. Boyer-Moore string sea…
I provided the time complexity of each operation as part of the README.
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.
Of course you have the option to just not do that in your code, but it's nice to have a hard guarantee that this can never happen, even by accident. I could have used a deque as a backend and wrapped it in the class, though.
- Dominator tree (https://en.wikipedia.org/wiki/Dominator_(graph_theory))
- Single-Connected-Components-Graph
- Deterministic data structures (eg. a set that acts deterministic to the fact that addresses might be somehow randomly assigned, very useful for ensuring reproducibility)
Already cited, but it's clearly among the most elegant:
- union-find (!!!!)
and as a bonus one that is easily overlooked:
-std::deque, that when restricted to push_back() or push_front() guarantees not to ever move objects around.
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…
Another interesting approach to copy-on-write for immutable collections (for example arrays) is where you actively mutate the array in place, but leave the original as a lazy description/view of how to get back to the before state. From the outside the effect is the same, but the performance is optimized for accessing the updated collection and only possibly using the old value. Great for cases where you want the imm…
Directed acyclic word graphs (DAWGs)! They’re like tries, but with identical subtrees glued together. They’re capable of encoding real-world dictionaries of millions of words into ~1 byte per word, when stored cleverly (see [0]). They let you do things like efficiently finding a list of words in a dictionary whose Levenshtein’s distance to a given word is less than x. Their cousins, GADDAGs, are _the_ data structure…
I haven't done any Java in years, but I made a Java package in 2013 that supports: DAWGs, Levenshtein automata and perfect hash automata:
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…
Frugal streaming. For estimating a median or percentile in a stream, using constant memory. It's very simple: if the current value is higher than our estimate, then increase our estimate by one. Else decrease by one. It will converge over long enough time. This is called the Frugal-1U algorithm. The Frugal-2U is a slightly more advanced version that modifies the step size along the way, plus other optimizations, to c…