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

Re:Ask HN: What are some cool but obscure data structures yo... by physicsguy on Friday July 22, 2022 @02:16AM (#32189098)

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.

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by jsmith45 on Friday July 22, 2022 @10:58AM (#32192588)

Honestly, that is not too uncommon. For top level algorithm choice analysis, "rounding" O(log(n)) to O(1), and O(n*log(n)) to O(n), is often pretty reasonable for algorithm comparison, even though it is strictly incorrect.

It is not uncommon for a simple O(n*log(n)) algorithm to beat out a more complex O(n) algorithm for realistic data sizes. If you "round" them to both O(n), then picking the simpler algorithm because the obvious choice, and can easily turn out to have better perf.

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by physicsguy on Friday July 22, 2022 @04:01PM (#32196463)

To be fair, in the general case (particles placed in arbitrary positions), it worked very well. The issue was that in the area of electromagnetics I worked on at the time, we make an assumption about things being placed on a regular grid, and that allows you to do the force calculation by convolving a kernel with the charges/dipole strength in Fourier space.

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by thisisnotatest on Thursday July 28, 2022 @10:02PM (#32272356)

A helpful little heuristic that always stuck with me from a Stanford lecture by Andrew Ng was, "log N is less than 30 for all N".

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by xigoi on Friday July 22, 2022 @04:24AM (#32189806)

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

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by mmorse1217 on Friday July 22, 2022 @08:56AM (#32191398)

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

[ Parent | on HN ]