Live data from Hacker News

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

news.ycombinator.com

701–710 of 772 posts

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

#701
post #682

Earlier quoted context omitted.

Yes, I evaluated it. The complexity of knowing where to convert from/to plain JS, plus the extra library syntax to learn, plus the performance cost of toJS, made it a poor fit for my particular use case. Nearly as much of a hard sell at work as saying “let’s rebuild the UI in Clojurescript,” and without providing as much benefit. My use case is pretty atypical though, and it’s worth checking out if you have more reli…

Does immer have the same drawbacks as immutable? It uses proxies as opposed to hased array map tries.

The key design difference between the two is that immutable.js wants you to keep your stuff in its format (and operate on your stuff with its functions) until you hit some piece of code that needs a plain JS object. Whereas immer is scoped (mostly?) to update functions, and always returns plain JS. Immer seems to be designed to simplify the problem of only changing references to changed objects—and it looks like it does a good job of it.

So with immutable.js, you get more powerful data manipulation throughout the app, at the cost of having to know when and where to convert things back to plain JS. With immer, you get tightly-scoped immutable updates to objects, and inside the update function you can treat them as if they’re mutable, letting you write more idiomatic-looking JS. Instead of spreading 4 layers of objects to update one state flag, immer lets you say:

  const nextState = produce(state, draft) => {
    draft.view.marketing.annoyingSubscribePopup = false
  }
Every object reference in that path will be updated, but the rest of “state”, “state.view”, etc. will be unchanged.

If you can keep everything inside of immutable.js, it is the fastest thing out there. As soon as you have to drop back to plain JS, it gets slower. See this performance graph: https://immerjs.github.io/immer/performance/

Thanks for reminding me of this. We finally dropped IE11 support, so may be able to get some benefits from introducing immer either by itself or by bringing in Redux Toolkit.

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

#702
post #430

Earlier quoted context omitted.

Segment trees are objectively superior in all ways except implementation length

Another advantage to Fenwick Tree: while it shares asymptotic space complexity with Segment Tree, it has better constant factors, which can be useful in very restricted environments.

I used fenwick trees in a smart contract because space/time costs money.

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

#703
post #674

Earlier quoted context omitted.

> I did not in fact find a way to make it efficiently support incremental edge deletion, which is what I was looking for. I don't understand this goal. The interior connections aren't relevant to a union-find structure; ideally you have a bunch of trees of depth 2 (assuming the root is at depth 1), but the internal structure could be anything. That fact immediately means that the consequence of removing an edge is no…

Union find takes as input some undirected graph N , E > and internally constructs (and progressively mutates) a directed graph N , E '> which it uses to efficiently answer queries about whether two nodes n ₁, n ₂ ∈ N are in the same connected component of N , E >. It additionally supports incrementally adding edges to E . My quest was to find a way to incrementally delete edges from E , not E '. You're talking about…

I don't think there's a way to extend union-find to do what you want in the general case. You might have more luck starting with a minimum cut algorithm.

For the specific case where you can identify some of your edges are more or less likely to be deleted, though, you can run union-find on only the stable edges, cache that result, and then do the unstable edges. Whenever an unstable edge is deleted, reload the cache and redo all the unstable edges. This works for something like a maze with open/closable doors.

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

#704

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…

This is great. I'm actually running into this problem but across distributed clients. Is there a distributed way to achieve somthing like this with say Redis?

Technically yes, the promise can first do an RPC to a distributed key/value store, and only then do the expensive computation (which typically is itself an RPC to some other system, perhaps a traditional database). Promise libraries should make this pretty simple to express (though always uglier than blocking calls).

I say expensive because even in a data center, an RPC is going to take on the order of 1ms. The round-trip from a client like a browser is much greater especially where the client (if this is what you meant by "client") has a poor internet connection.

Therefore this pattern is usually done inside of an API server in the data-center. Additional benefits of the server side approach is that an API server can better control the cache keys (you could put the API server "build number" in the cache key so you can do rolling updates of your jobs), TTL, etc. Also, you don't want a rogue computer you don't control to directly talk to a shared cache since a rogue computer could put dangerous values into your cache, remove elements from the cache they shouldn't, etc.

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

#706

Earlier quoted context omitted.

This surprises me. I had expected the microtask to be executed right after the current one, ie before any layouting etc - isnt that the whole point the "micro" aspect?

I was able to reproduce this in a simple example [1]. If you refresh it a few times you will be able to see it flash (at least I did in Chrome on Mac). It is probably more noticeable if you set it up as an SPA with a page transition, but I wanted to keep the example simple. [1] https://codesandbox.io/s/recursing-glitter-h4c83u?file=/src/...

I am deeply disturbed and confused. Do you understand why this happens?

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

#707

Spatial hashing. Say that you have data that is identified with points in 2D or 3D space. The standard way that CS students learn in school to represent this is via a quadtree or octree. However, these tree data structures tend to have a lot of "fluff" (needless allocations and pointer chasing) and need a lot of work to be made efficient. Spatial hashing is the stupidly simple solution of just rounding coordinates to…

Are these similar to space-filling curves like z-order indices? https://en.wikipedia.org/wiki/Z-order

Some more such curves: https://web.archive.org/web/20220120151929/https://citeseerx...

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

#708
post #674

Earlier quoted context omitted.

Union find takes as input some undirected graph N , E > and internally constructs (and progressively mutates) a directed graph N , E '> which it uses to efficiently answer queries about whether two nodes n ₁, n ₂ ∈ N are in the same connected component of N , E >. It additionally supports incrementally adding edges to E . My quest was to find a way to incrementally delete edges from E , not E '. You're talking about…

I don't think there's a way to extend union-find to do what you want in the general case. You might have more luck starting with a minimum cut algorithm. For the specific case where you can identify some of your edges are more or less likely to be deleted, though, you can run union-find on only the stable edges, cache that result, and then do the unstable edges. Whenever an unstable edge is deleted, reload the cache…

Those are some interesting ideas, thanks! I hadn't thought about trying to apply minimum-cut to the problem!

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

#709
post #687

Earlier quoted context omitted.

If the Record & Tuple proposal advances to stage 3 we'll finally have native immutable data structures in JS [1]. [1] https://github.com/tc39/proposal-record-tuple

I have beeen waiting aeons for this, and suspect will need to continue waiting effectively forever :(

Yeah TC39 has a habit of letting proposals languish at stage 2 for years. I wouldn't give up hope though. The decorators proposal finally made it to stage 3 after spending an eternity at stage 2. According to the slides from the TC39 meeting this month [1][2], it looks like they'll be proposing an advancement to stage 3 in September.

[1]https://github.com/tc39/agendas/blob/main/2022/07.md [2]https://www.dropbox.com/s/g4enjgd4p2npv2s/record_tuple_updat...

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

#710

Struct of arrays (also called MultiArrayList in Zig), instead of storing big structs in an array you store each field in a separate array and if you need to fetch the full struct you reconstruct it from the arrays. The benefit is that the arrays items memory size is smaller and has no padding, it also increases cache locality.

this is a great way to store structured data in js since it saves the memory cost having repeated keys. e.g.: records = { time: [1000, 1001], price: [20, 25], volume: [50, 15] } records = [ { time: 1000, price: 20, volume: 50 }, { time: 1001, price: 25, volume: 15 } ] // not a big difference with 2 records, but for xxxx records...

Decent JS engines will use "hidden classes" to dedupe keys for you already, so this isn't necessary to save space; the technique is pretty old and dates to Self. Still, the arrangement may help with locality of reference.
Post reply on HN