Not a data structure, and not really obscure, but I am still amazed by the concept of solving DP (dynamic-programming) problems in O(log N) instead of O(N) time by writing the solution as a Fast Matrix Exponentiation equation: https://www.geeksforgeeks.org/matrix-exponentiation/
Ask HN: What are some cool but obscure data structures you know about?
641–650 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#642I came up with a clever one recently. So, I had a stream of records of fixed size where I will receive exactly one per second. I needed to keep approximately two weeks of this data. I would also need to be able to query the records by time. Anyway, the idea is: use modulus on the file creation time to calculate a write position. Use the location of the current write position to locate query starts and stops. The file…
Sounds like a ring buffer stored in a file.
Re: Ask HN: What are some cool but obscure data structures you know about?
#643The 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…
Can you give some examples where union-find is applied to great benefit?
I used it to find and track islands of connected polygons in 3D meshes.
Re: Ask HN: What are some cool but obscure data structures you know about?
#644How about the current DATE formats based on the EPOCH. Hell, they knew there was nothing to it, but some backstreet performances inspired my Y2K formative years where my normal, kind, religious mother became a hoarder that destroyed everything she touched. Why can Java still not do simple date processing when even M$$ nailed that formula generations ago? Not letting devs communicate cross platform without Linux level…
I think you managed too lose me about 3 times in there.. what point are you trying to make, and what do you think Linus should do?
Re: Ask HN: What are some cool but obscure data structures you know about?
#645HAMT: 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…
I imagine careless use of such a structure would be an easy way to create a memory leak. Is it possible to create persistent collections in js, that will free data no longer directly referenced?
The careless usage of shallow copies of objects (with JS spreading) presents the same issue. Properly scoping assigned constants and variables is still important.
Persistent collections are available today via immutable.js, so it can be done. The catch is that you have to use a library for it, and transform them back into plain JS when something expects an object or an array. The language itself could make this transparent and lower-cost by implementing it at the engine level.
Persistent collections are primarily useful in functional programming paradigms. JS is a multi-paradigmatic language, so it doesn’t make sense to use them as the default. It would sure be nice to be able to opt into using them in FP-aligned frameworks like the current React ecosystem though.
Re: Ask HN: What are some cool but obscure data structures you know about?
#646HNSW, or Hierarchical Navigable Small World is a graph data structure for approximate nearest neighbor search of vectors. https://arxiv.org/abs/1603.09320 The problem space of ANN is one of those really deep holes you can go down. It’s a game of balancing time and space, and it’s got plenty of fascinating algorithms and datastructures. Check out http://ann-benchmarks.com/ for a comparison. HNSW is not “the best” but…
I second this.. very useful for vector NLP and other ML tasks.
Re: Ask HN: What are some cool but obscure data structures you know about?
#647Earlier quoted context omitted.
This is only tangentially related to: > you avoid computing/fetching the same value twice But this problem comes up in reverse proxies too. In Nginx, you can set the `proxy_cache_lock`[0] directive to achieve the same effect (avoiding double requests). [0]: https://nginx.org/en/docs/http/ngx_http_proxy_module.html#pr...
That right there is Cache Stampede[0] prevention. [0]: https://en.wikipedia.org/wiki/Cache_stampede
Interesting! This is an issue I had with an external API which I intended to cache on my serverless workers infra.
I hit the API's rate limiter when the workers invalidated their cache, even though I staggered the lifetime of the cache keys for each replicated instance. This is how I found out how many Cloudflare workers run on a single edge instance. Hint: It's many.
Didn't know it had a name. I'm delighted, thanks!
Re: Ask HN: What are some cool but obscure data structures you know about?
#648Earlier quoted context omitted.
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.
Promises are an implementation of lazy evaluation for Javascript. This is exactly lazy evaluation.
By the way, lazy evaluation is the one that offers no guarantees about when your code will be executed. If you can delay the execution, it's not lazy.
Re: Ask HN: What are some cool but obscure data structures you know about?
#649FST: Finite State Transducer. Widely used inside search (Lucene), DB powering prefix, fuzzy search
Re: Ask HN: What are some cool but obscure data structures you know about?
#650Earlier quoted context omitted.
Sure it's possible, we need to await for the Task if it already exists on the dictionary, for example we could imagine writing something like this inside an actor to make it threadSafe. private var tasksDictionary: Dictionary > func getData(at urlString: String) async throws -> Data { if let currentTask = tasksDictionary[urlString] { return await currentTask.value } let currentTask = Task { return try await URLSessio…
Hmm, why set `taskDictionary[urlString] = nil` at the bottom there? If the whole point is to cache the result, isn't the point to leave the value there for other requests to pick it up?
Yup, nice catch, no need to reset it to nil if you wanna keep it in memory indefinitely.
I guess making it nil can be also used if you don't wanna make the same request when there is one already in flight, in case you have a 403 error and need to request a refresh token, you don't wanna make two simultaneous requests, but you also don't wanna catch it indefinitely either.