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

481–490 of 772 posts

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

#481

Post by zasdffaa »

ignoramous wrote: post #440

> Good use-case: routing. Say you have a list of 1 million IPs that are [deny listed]. Apparently, bloom filters make for lousy IP membership checks, read: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ CritBit Trie [0] and possibly Allotment Routing Table (ART) are better suited for IPs [1]. [0] https://github.com/agl/critbit [1] https://web.archive.org/web/20210720162224/https://www.harig...

That over-simplifies what the linked article says, plus there are things like blocked bloom filters and other tricks to speed things up.

Plus if he's allocating 128MB, well, just do it as a direct array 1 bit per IP4 address (which can be optimised to remove a few special blocks I guess) and skip any hashing.

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

#482

Post by winReInstall »

Input, Output Unionnions. basically a input struct into a algorith, layed out in such a way, that the algorithms output, always only overwrites input no longer needed. If done well, this allows for hot-loops that basically go over one array for read & write-backs. After all, its all just memory and to use what you got in situ is the fastet way one can go.

No pointers to dereference and wait, just the input, computated, stored back into the same cacheline- to be used for the next part of the hot loop. If the hot-loop is multi staged and the output continously decreases in size, one can even "compress" the data, by packing an array of orgMaxisze/outputSize subunits into the unit.

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

#483

Post by nullc »

How about a pinsketch:

A pinsketch is a set that takes a specified amount of memory and into which you can insert and remove set members or even add whole sets in time O(memory size). You can insert an unbounded number of entries, and at any time that it has equal or fewer entries than the size you can decode the list of members.

For an example usage, say I have a list of ten million IP addresses of people who have DOS attacked my systems recently. I want to send my list to you over an expensive pay as you go iridium connection, so I don't want to just send the 40MiB list since that would cost about $700. (Or 12.7 MiB if you use an optimal set encoding, or somewhat in between if you use the Golomb coded set mentioned in the OP).

Fortunately you've been making your own observations (and maybe have stale data from me), and we don't expect our lists to differ by more than 1000 entries. So I make and maintain a pinsketch with size 1000 which takes 4000 bytes (1000 * 4bytes because IP addresses are 32-bits). Then to send you an update I just send it over. You maintain your own pinsketch of addresses, you subtract yours from the one I sent and then you decode it. If the number of entries in the resulting set (the number different between us) is 1000 or fewer you're guaranteed to learn the difference (otherwise the decode will fail, or give a false decode with odds ~= 1/2^(1000)).

Bonus: We don't need to know in advance how different our sets are-- I can send the sketch in units as small as one word at a time (32-bits in this case) and stop sending once you've got enough to decode. Implemented that way I could send you exactly the amount of data you're missing without even knowing which entries you're missing.

The sketch itself is simple: To insert an element you raise it to a sequence of odd powers (1,3,5,7...) in a finite field and add it to an accumulator for each power. The tricky part is decoding it. :P

Here is an implementation I contributed to: https://github.com/sipa/minisketch/

There is a application related data-structure called an inverted bloom lookup table (IBLT) that accomplishes the same task. Its encoding and especially decoding is much faster, and it has asymptotically the same communications efficiency. However, the constant factors on the communications efficiency are poor so for 'small' in set difference (like the 1000 above) it has a rather high overhead factor, and it can't guarantee decoding. I think that makes it much less magical, though it may be the right tool for some applications.

IBLT also has the benefit that it the decoder is a fun bit of code golf to implement.

The encoding for IBLT is simple: take your entries, append a checkvalue (can't be a plain CRC). Then hash them with three hash-functions to obtain three locations in a hash table and xor them into those locations (removal works the same way, due to xor's self-inverse property). Decoding an IBLT works by finding entries whos check value passes (which will be true when they are the only entry in their position) and subtracting them from the table (hash them to get their other two positions, and xor them in all three). Decoding is successful when the data structure is all zeros. When the tables are big enough and have a modest amount of slack space the decoding algorithm will be successful (for it to fail there has to be an overlapping cycle, which becomes rare in sufficiently large random graphs). (this description is probably enough for a reader to make a working IBLT implementation though it omits some improvements)

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

#484

Post by dmix »

mromnia wrote: post #441
unsupp0rted wrote: post #434

Earlier quoted context omitted.

Partly off-topic, but in JS I tend to avoid iterating over promises with maps because it's always confusing what will/won't work, so I use a basic FOR loop because async/await works in there. How bad is this? Should I switch to Promise.all instead?

Iterating with async/await means you wait for every result before making another call. You basically execute the async calls one by one. Promise.all runs them all simultaneously and waits until they are all complete. It returns an array of results in the same order as the calls, so it's usually pretty straightforward to use. Both approaches have a purpose, so it's not like you "should" strictly use one. But you shoul…

The third major strategy being Promise.any():

- as soon as any of them resolve (any)

- when all of them resolve (all)

- resolve each in order (for)

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

#485

Post by remorses »

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.

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

#486

Post by robalni »

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 was experimenting a while ago with something that I think is related to this.

If you have a quadratic algorithm where you need to compare each pair of objects in a large array of objects, you might use a loop in a loop like this:

    for (int i = 0; i
When this algorithm runs, it will access every cache line or memory page in the array for each item, because j goes through the whole array for each i.

I thought that a better algorithm might do all possible comparisons inside the first block of memory before accessing any other memory. I wanted this to work independently of the size of cache lines or pages, so the solution would be that for each power of 2, we access all items in a position lower than that power of 2 before moving to the second half of the next power of 2.

This means that we need to first compare indexes (0,0) and then (1,0),(1,1),(0,1) and then all pairs of {0,1,2,3} that haven't yet been compared and so on.

It turns out that the sequence (0,0),(1,0),(1,1),(0,1) that we went through (bottom-left, bottom-right, top-right, top-left in a coordinate system) can be recursively repeated by assuming that the whole sequence that we have done so far is the first item in the next iteration of the same sequence. So the next step is to do (0,0),(1,0),(1,1),(0,1) again (but backwards this time) starting on the (2,0) block so it becomes (2,1),(3,1),(3,0),(2,0) and then we do it again starting on the (2,2) block and then on the (0,2) block. Now we have done a new complete block that we can repeat again starting on the (4,0) block and then (4,4) and then (0,4). Then we continue like this through the whole array.

As you can see, every time we move, only one bit in one index number is changed. What we have here is actually two halves of a gray code that is counting up, half of it in the x coordinate and the other half in y. This means that we can iterate through the whole array in the described way by making only one loop that goes up to the square of the size and then we get the two indexes (x and y) by calculating the gray code of i and then de-interleaving the result so that bits 0,2,4... make the x coordinate and bits 1,3,5... make y. Then we compare indexes x and y:

    for (int i = 0; i
The result of all this was that the number of cache line/page switches went down by orders of magnitude but the algorithm didn't get faster. This is probably for two reasons: incremental linear memory access is very fast on modern hardware and calculating the gray code and all that added an overhead.

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

#487

Post by Gravityloss »

pacaro wrote: post #98
zarzavat wrote: post #55

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…

TBH even quadkeys are a fun answer to OPs question, many people aren't aware of them. Simple explanation: If you have data with x y coordinates and you know the bounds. To compute the quad key for a point: 1. The key starts as the empty string. (I've also seen it start with "Z" to handle points outside the bounds) 2. Divide the space into 4 quadrants 3. determine which quadrant the point falls in, append a letter (A-…

Hmm... the quad keys end up looking very much like coordinates. In the regular coordinates, the most significant bit divides the space in half, then the next bit divides those spaces in halves etc...

You could get a single "key" by just having a sequence of bits with most significant bit of x coordinate, most significant bit if of y coordinate, second most significant bit of x coordinate, second most significant bit of y coordinate, third....

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

#488

Post by O__________O »

Wikipedia’s list of algorithms and data structures is pretty extensive:

https://en.m.wikipedia.org/wiki/List_of_algorithms

https://en.m.wikipedia.org/wiki/List_of_data_structures

__________________

As for a specific algorithm, this paper covers analysis of HyperLogLog (HLL):

http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

TLDR: Calculating the exact cardinality of a multiset requires an amount of memory proportional to the cardinality, which is impractical for very large data sets. Probabilistic cardinality estimators, such as the HyperLogLog algorithm, use significantly less memory than this, at the cost of obtaining only an approximation of the cardinality. The HyperLogLog algorithm is able to estimate cardinalities of > 10^9 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory.

Source:

https://en.wikipedia.org/wiki/HyperLogLog

Recent HN coverage of HyperLogLog:

https://news.ycombinator.com/item?id=32138790

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

#489

Post by blue_pants »

ralusek wrote: post #312
skrebbel wrote: post #297

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…

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…

Please correct me if I'm wrong. But you'd better avoid creating extra promises for performance reasons

  const promiseMap> = new Map();

  async function keyedDebounce(key: string, fn: () => R) {
    const existingPromise = promiseMap.get(key);
    if (existingPromise) return existingPromise;
  
    const promise = fn().then(result => {
      promiseMap.delete(key);
  
      return result;
    });
  
    promiseMap.set(key, promise);
  
    return promise;
  }

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

#490

Post by samanator »

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.

Sounds like a primitive of columnar databases.
Post reply on HN