Datum
2014-09Metadata
Zur Langanzeige
Preprint
Heapsort for Equal Keys
(Sortierung mittels Heapsort bei Vorliegen gleicher Schlüssel)
Zusammenfassung
Das effiziente Entfernen von Duplikaten in Datenbeständen ist eine algorithmische Herausforderung in theoretischer und praktischer Hinsicht. Tabellen mit Duplikaten entstehen in Datenbanken nach einer Projektion, beim Verfolgen von Seiten im Web, bei Messreihen und in der Stochastik. Ein häufige Methode, diese sog. Multisets in echte Mengen zu wandeln, ist die Sortierung mit folgender Entfernung aller gleichen Sätze bis auf einen. Idealerweise kann dies bereits bei der Sortierung in situ erfolgen, so dass vorne die sortierten Sätze stehen und hinten deren Duplikate. Noch wichtiger ist die Reduzierung der Laufzeit für n Sätze mit k unterschiedlichen Schlüsseln auf die untere Schranke von O(n log k) Schritte. Dies galt für das klassische Heapsort-Verfahren als nicht erreichbar ohne eine grundsätzliche Umstrukturierung im Stil von Dijkstras Smoothsort. Wir zeigen mit unserem Algorithmus DDHeapsort, dass diese Annahme irreführend ist und dass DDHeapsort in der Praxis die gewünschte Beschleunigung beim Vorliegen von Duplikaten aufweist, ohne dass eine erhebliche Verlangsamung bei duplikatfreien Datensätzen eintritt.
Efficient duplicate detection and deletion is an algorithmic challenge both in practical terms and from a theoretical stand point. Duplicates may occur in database tables after a projection, in tracking web traffic, experimentation and statistics. To reduce these multisets to proper sets, the most common approach is o sort the file first and then – in an additional sweep – take one instance, say the first, from each multiplicity of keys. If done in place, ideally the front of the file contains afterwards the sorted subset of unique keys and the duplicates are in the back. Sorting methods which can be engineered to do early duplicate deletion may reduce the effort spent to O(n log k), where k is the number of distinct keys. General wisdom had it that this smooth behaviour wasn’t achievable with heapsort unless the sort was totally redesigned in the style of Dijkstra’s Smoothsort. Here we show that this is a misperception and present DDHeapsortas a duplicate elimination method which achieves the lower bound of O (n log k) steps – both on the averageand in the worst case – and requires O(1) extra space. Empirical evidence suggests that DDHeapsort comes with very little penalty in the case of no duplicates when compared to a fast heapsort with subsequent duplicate detection sweep.
Zitieren
@article{doi:10.17170/kobra-202203165893,
author={Schweinsberg, Kai and Teuhola, Jukka and Wegner, Lutz},
title={Heapsort for Equal Keys},
year={2014}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2014$n2014 1500 1/eng 2050 ##0##http://hdl.handle.net/123456789/13707 3000 Schweinsberg, Kai 3010 Teuhola, Jukka 3010 Wegner, Lutz 4000 Heapsort for Equal Keys :Sortierung mittels Heapsort bei Vorliegen gleicher Schlüssel / Schweinsberg, Kai 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/http://hdl.handle.net/123456789/13707=x R 4204 \$dPreprint 4170 5550 {{Daten}} 5550 {{Sortieren}} 5550 {{Multimenge}} 5550 {{Dublette}} 5550 {{Datenstruktur}} 5550 {{Algorithmus}} 7136 ##0##http://hdl.handle.net/123456789/13707
2022-03-18T13:58:03Z 2022-03-18T13:58:03Z 2014-09 doi:10.17170/kobra-202203165893 http://hdl.handle.net/123456789/13707 eng Attribution-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nd/4.0/ Sortieren Multimengen Duplikatsentfernung Heapsort 004 Heapsort for Equal Keys Preprint Das effiziente Entfernen von Duplikaten in Datenbeständen ist eine algorithmische Herausforderung in theoretischer und praktischer Hinsicht. Tabellen mit Duplikaten entstehen in Datenbanken nach einer Projektion, beim Verfolgen von Seiten im Web, bei Messreihen und in der Stochastik. Ein häufige Methode, diese sog. Multisets in echte Mengen zu wandeln, ist die Sortierung mit folgender Entfernung aller gleichen Sätze bis auf einen. Idealerweise kann dies bereits bei der Sortierung in situ erfolgen, so dass vorne die sortierten Sätze stehen und hinten deren Duplikate. Noch wichtiger ist die Reduzierung der Laufzeit für n Sätze mit k unterschiedlichen Schlüsseln auf die untere Schranke von O(n log k) Schritte. Dies galt für das klassische Heapsort-Verfahren als nicht erreichbar ohne eine grundsätzliche Umstrukturierung im Stil von Dijkstras Smoothsort. Wir zeigen mit unserem Algorithmus DDHeapsort, dass diese Annahme irreführend ist und dass DDHeapsort in der Praxis die gewünschte Beschleunigung beim Vorliegen von Duplikaten aufweist, ohne dass eine erhebliche Verlangsamung bei duplikatfreien Datensätzen eintritt. Efficient duplicate detection and deletion is an algorithmic challenge both in practical terms and from a theoretical stand point. Duplicates may occur in database tables after a projection, in tracking web traffic, experimentation and statistics. To reduce these multisets to proper sets, the most common approach is o sort the file first and then – in an additional sweep – take one instance, say the first, from each multiplicity of keys. If done in place, ideally the front of the file contains afterwards the sorted subset of unique keys and the duplicates are in the back. Sorting methods which can be engineered to do early duplicate deletion may reduce the effort spent to O(n log k), where k is the number of distinct keys. General wisdom had it that this smooth behaviour wasn’t achievable with heapsort unless the sort was totally redesigned in the style of Dijkstra’s Smoothsort. Here we show that this is a misperception and present DDHeapsortas a duplicate elimination method which achieves the lower bound of O (n log k) steps – both on the averageand in the worst case – and requires O(1) extra space. Empirical evidence suggests that DDHeapsort comes with very little penalty in the case of no duplicates when compared to a fast heapsort with subsequent duplicate detection sweep. open access Sortierung mittels Heapsort bei Vorliegen gleicher Schlüssel Schweinsberg, Kai Teuhola, Jukka Wegner, Lutz Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik Daten Sortieren Multimenge Dublette Datenstruktur Algorithmus draft false
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden: