#2211: gh::regrid contains code whose runtime is quadratic in number of components --------------------------+--------------------------------- Reporter: Roland Haas | Owner: (none) Type: defect | Status: new Priority: minor | Milestone: Component: Carpet | Version: development version Resolution: | Keywords: --------------------------+---------------------------------
Comment (by Erik Schnetter):
For obvious reasons, I am in the unique position to confirm that the person who wrote this wasn't thinking straight. There are several straightforward ways to improve this code.
1. There is no need to first calculate the intersection and then check whether it is empty. It is much more efficient to check whether {{{b}}} and {{{extent}}} are disjoint. 2. Instead of checking whether the bounding boxes are pairwise disjoint, one can calculate their union, and then compare the cardinality of the union with the sum of the cardinality of the individual boxes. This algorithm has complexity {{{n * log(n)}}}. 3. This check is most likely superfluous, as {{{dh::regrid}}}, which does the actual work, contains much more stringent checks. In fact, to my recollection, none of the {{{gh}}} consistency checks ever caught a bug. We could put all of them into an {{{#ifdef CARPET_DEBUG}}} clause.