News for hackers. Stuff that matters.

A comment on Ask HN: What are some cool but obscure data structures you know about?. Parent comment

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 ]