D-Programming-Language/phobos — pull request #1798 by monarchdodra (2013-12-20 19:22:57+00:00)
Title: improve set intersection algorithm

https://github.com/D-Programming-Language/phobos/pull/1796

pinging @JakobOvrum : After merging your commit, I couldn't get the code out of my head. I just kept teling myself "it works, but isn't that inefficient?" Give it a review?

The first commit is trivial: It makes a "preemptive" call to `empty` in `adjustPosition`, and then check each range individually after every pop. `empty` is kind of expensive in the contex of `setIntersection`, especially if there are a lot of ranges being intersected, so it should be a net gain right there.

The second commit is more complicated. The existing algorithm had 2 flaws, which combined, lead to a performance (if I'm not mistaken), of O(N²), where N is the ammount of ranges involved.
* First, the algorithm "restarts" after each operation. So if "range 5" needs to be popped 5 elements, we need to re-check ranges 1-4 first, 5 times :/
* Second, the algorithm has a "bubble sort" kind of problem with it: It is easy to propagate the min from "left to right", due to the iteration scheme, but "right to left" is much harder, as the "swaps" go left to right.

So the second commit solves both these issues with a "shaker sort" style algorithm: Instead of checking both directions when dealing with "i, i+1", it iterates left to right while propagating the low value to the right, and *then* does the other check, while iterating the other way. Instead of doing a "continue", we simply mark "done" as false, which means we can pop with a "while". AFAIK, the algo should be O(N) in terms of ranges involved.

Can the algorithm be further improved? Maybe, but I think this one is "good enough" for a fair amount of code (IMO).

For every day cases, I don't think it makes much difference, but if you want to intersect a fair bit of ranges, and with a "low concentration" of intersection, it makes quite a difference.