Ist Hedge Union immer so schnell wie Teilen und Erobern?

Adams beschreibt einen Divide-and-Conquer-Algorithmus zum Finden der Vereinigung zweier Mengen (dargestellt als gewichtsausgeglichene binäre Suchbäume). Anschließend beschreibt er einen damals neuen "Hedge Union" -Algorithmus, von dem er behauptet, dass er den Divide-and-Conquer-Algorithmus verbessert. Er bietet jedoch keinen Beweis oder gar eine echte Erklärung dafür, warum es , geschweige denn, warum es schneller sein sollte als Teilen und Erobern.$O(m + n)$

Blelloch, Ferizovic und Sun zeigen, dass Adams Divide-and-Conquer-Algorithmus tatsächlich das theoretisch optimale wobei . Sie befassen sich jedoch nicht mit dem Hedge-Union-Algorithmus.$\Theta (m \log (n/m + 1))$$m \le n$

Ist Hedge Union tatsächlich so effizient wie Divide-and-Conquer? Der am wenigsten offensichtliche Teil ist die Innenverkleidung. Zumindest oberflächlich betrachtet scheint es, die Arbeit zwischen dem linken und dem rechten Teilbaum zu duplizieren, die die vollständige Aufteilung zwischen ihnen teilt. Vielleicht ist das aus irgendeinem Grund in Ordnung, aber ich weiß nicht warum.

Eine weitere Anfrage: Haskell's Data.Setund Data.MapHedge-Varianten von Schnittmenge und Differenz sowie Union. Ich habe überhaupt keine veröffentlichte Diskussion über diese Algorithmen gefunden. Ähnliche Fragen gelten auch für diese.

Obwohl ich noch keine theoretische Analyse der Hedge-Algorithmen gesehen oder erstellt habe, habe ich einige empirische Beweise dafür, dass sie schlechter sind als die Divide-and-Conquer-Algorithmen für Binärbäume.

Beginnend mit dem Code im Haskell- containersPaket habe ich den Hedge-Union-Algorithmus optimiert, indem ich die Call-Pattern-Spezialisierung manuell angewendet habe, um die Zwischenzuweisung zu reduzieren. Dies verbesserte seine Leistung um etwa 10% und gab ihm einen fairen Schuss.

Beginnend mit dem Divide-and-Conquer-Code in Adams habe ich den Vereinigungsalgorithmus optimiert, indem ich Sonderfälle hinzugefügt habe, wenn eine der Eingaben ein Singleton ist (der Hedge-Vereinigungscode optimiert eine Seite auf diese Weise, und es ist nicht klar, ob die andere Seite optimiert werden kann ähnlich).

Ich habe jede Implementierung mit einer Sammlung von Benchmarks für festgelegte Operationen getestet, die mit verpackt sind containers. Divide-and-Conquer war normalerweise schneller als Hedge, manchmal doppelt so schnell. Wenn es langsamer war, war es nur geringfügig.

Ähnliche Benchmarks anderer festgelegter Operationen ergaben ähnliche Ergebnisse.

Spekulation:

Hedge-Algorithmen können hilfreich sein, wenn Bäume mit großen Verzweigungsfaktoren verwendet werden, deren rekursives Teilen möglicherweise teurer ist. Sie können auch für kleine Teilbäume hilfreich sein, in denen sie möglicherweise genügend Zuordnung sparen, um die zusätzliche Arbeit wert zu sein.