So as not to dox oneself with context, an unrelated example of how a large CPU saving happens is traversing a 3D point cloud as pairs and selecting nearby points. With a flat list it's O(n²) to check each against each other, but an initial pass to build an octree index makes nearby spatial lookup logarithmic (region size doubling/halving), giving O(n log n).
It's even better if there's a distance limit, that drops it to O(n) with a scale factor of the general cloud density.
SithEmpire 1 points 3 weeks ago
Well done!
So as not to dox oneself with context, an unrelated example of how a large CPU saving happens is traversing a 3D point cloud as pairs and selecting nearby points. With a flat list it's O(n²) to check each against each other, but an initial pass to build an octree index makes nearby spatial lookup logarithmic (region size doubling/halving), giving O(n log n).
It's even better if there's a distance limit, that drops it to O(n) with a scale factor of the general cloud density.