Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

491–500 of 772 posts

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

#491

Post by chmod775 »

skrebbel wrote: post #480
wingspan wrote: post #443

Earlier quoted context omitted.

I love this approach and have used it many times in JavaScript. I often end up adding an additional map in front with the resolved values to check first, because awaiting or then'ing a Promise always means you will wait until the next microtask for the value, instead of getting it immediately. With a framework like React, this means you'll have a flash of missing content even when it is already cached.

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?

The event loop shouldn't continue the circle until the microtask queue is empty, from what I remember.

Browsers probably used to squeeze layouting and such things in when the event loop completed an iteration or became idle. However nowadays it's entirely possible that have, or will have, browsers that do even work in parallel while the javascript event loop is still running, possibly even beginning to paint while javascript is still running synchronously (haven't seen that yet).

I've seen instances where browsers seem to be like "nah, I'll render this part later" and only would render some parts of the page, but certain layers (scrolling containers) would not be filled on the first paint - despite everything being changed in one synchronous operation!* And I've seen them do that at least 5 years ago.

It seems to me the situation is complicated.

* There was a loading overlay and a list being filled with data (possibly thousands of elements). The loading overlay would be removed after the list was filled, revealing it. What often happened was that the overlay would disappear, but the list still looking empty for a frame or two.

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

#492

Post by zachrose »

mastermedo wrote: post #209
chriswarbo wrote: post #181

The Zipper acts like a linked-list with a cursor, or "focused element"; it's implemented as a pair of lists in opposite orders; or, equivalently but more symmetric, as triple of (List[A], A, List[A]) Say we have a zipper containing [0, 1, 2, 3, 4, 5], and we're focusing on the 3. In code this will look like: ([2, 1, 0], 3, [4, 5]) Where [a, b, c] denotes a singly-linked list, with O(1) head (returning a) and tail (re…

I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1]. What is the benefit here?

A list and an index creates the possibility that the index is out of bounds, and then your code probably has to check for that scenario and figure out how to handle it.

With a zipper such a scenario isn’t possible.

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

#493

Post by FridgeSeal »

zbobet2012 wrote: post #262
loxias wrote: post #64

(Fantastic post idea OP. One of the best I've ever seen :D) Related to bloom filters, xor filters are faster and more memory efficient, but immutable. HyperLogLog is an efficient way to estimate cardinality. Coolest thing I've learned recently was Y-fast trie. If your dataset M is bounded integers (say, the set of all 128 bit numbers), you get membership, predecessor, or successor queries in log log time, not log, li…

Y-fast tries are some of my favorites. I think they are heavily under utilized in modern terms. They sat by the the wayside for a long term because datasets where relatively small, at the time they where created ram didn't exist, and bitwise operations where inefficient along with many other constant factors. Today; however, a lot of people have datasets on the order of 2^16 or 2^32 keys they need to maintain. And ef…

> Also because they divide _space_ not the _data_ they are very amenable to multi-threaded and distributed algorithms.

Ha, I was thinking about this idea the other day and couldn’t figure out a good way to search for anything already written on the topic. I suspect there’s quite a lot of ground to be gained in the area.

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

#494

Post by fb03 »

remorses wrote: post #485

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.

Entity-Component Systems do exactly this for better cache locality

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

#495

Post by m12k »

The Bag. Also known as a Multiset. I can't believe it took me so many years to learn the name of the most basic data structure imaginable - it basically makes no promises whatsoever about the structure. Think of it like a Set that allows duplicates - you can put stuff in and take stuff out, just like a bag - what more could you want?

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

#496

Post by dicroce »

I 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 then has zero space overhead. Is this something known or did I actually invent something here? If this is my invention I'm open to hearing suggestions for a cool name!

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

#498

Post by mmorse1217 »

physicsguy wrote: post #256
jiggawatts wrote: post #25

Cache-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.

This implementation and associated paper improve the cache locality to make the algorithm more competitive https://github.com/dmalhotra/pvfmm

They compare solving toy problems with different methods here https://arxiv.org/pdf/1408.6497.pdf

But as you mention, this is just fiddling with constants, and it still may be too costly for your problem

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

#499

Post by chirau »

m12k wrote: post #495

The Bag. Also known as a Multiset. I can't believe it took me so many years to learn the name of the most basic data structure imaginable - it basically makes no promises whatsoever about the structure. Think of it like a Set that allows duplicates - you can put stuff in and take stuff out, just like a bag - what more could you want?

How is that any different from a list?

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

#500

Post by superjan »

MichaelMoser123 wrote: post #478
jtolmar wrote: post #171

The 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?

One example is connected component analyis on images. In one linear scan of an image (2d or 3d) you can find all connected blobs in an image.
Post reply on HN