8
$\begingroup$

Adams describes a divide-and-conquer algorithm for finding the union of two sets (represented as weight-balanced binary search trees). He then describes a then-new "hedge union" algorithm which he claims improves on the divide-and-conquer one. However, he does not offer a proof, or even a real explanation, of why it should be $O(m + n)$, let alone why it should be faster than divide-and-conquer.

Blelloch, Ferizovic, and Sun show that Adams's divide-and-conquer algorithm actually attains the theoretically optimal $\Theta (m \log (n/m + 1))$ where $m \le n$. They do not, however, address the hedge union algorithm.

Is hedge union, in fact, as efficient as divide-and-conquer? The least obvious part is the inner trim. It appears, at least superficially, to duplicate work between the left and right subtrees that the full split shares between them. Perhaps this is okay for some reason, but I don't know why.

A further inquiry: Haskell's Data.Set and Data.Map use hedge variants of intersection and difference, as well as union. I have not found any published discussion of those algorithms at all. Similar questions apply to these as well.

$\endgroup$
3
$\begingroup$

While I have yet to see, or produce, a theoretical analysis of the hedge algorithms, I do have some empirical evidence that they are worse than the divide-and-conquer algorithms for binary trees.

Starting with the code in the Haskell containers package, I optimized the hedge union algorithm by manually applying call-pattern specialization to reduce intermediate allocation. This improved its performance by about 10%, giving it a fair shot.

Starting with the divide-and-conquer code in Adams, I optimized the union algorithm by adding special cases when either of the inputs is a singleton (the hedge union code optimizes one side thus, and it's not clear if the other side can be optimized similarly).

I tested each implementation using a collection of set operation benchmarks packaged with containers. Divide-and-conquer was usually faster than hedge, sometimes twice as fast. When it was slower, it was only slightly so.

Similar benchmarks of other set operations gave similar results.


Speculation:

Hedge algorithms may be helpful when using trees with a large branching factors, which may be more expensive to split recursively. They may also be helpful for small subtrees, where they may save enough allocation to be worth the extra work.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Did you actually change the implementation in Data.Set based on these observations? $\endgroup$ – Joachim Breitner Jan 22 '18 at 1:56
  • $\begingroup$ @JoachimBreitner, yes, I did. I also used the same approach for the new safe merge utilities, although characterizing their precise performance characteristics is surely too difficult to bother with. $\endgroup$ – dfeuer Jan 22 '18 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.