Medienkatalog der Schulbibliothek: Suche, Einfügen und Bereichsabfragen
Die Bibliothek eines Gymnasiums verwaltet 12.400 Medien in einer Java-Anwendung. Alle Datensätze liegen in einer nach Inventarnummer sortierten ArrayList. Pro Schultag werden im Mittel 850 Suchen ausgeführt, davon 600 über den Titel, 200 über die Inventarnummer und 50 über den Autor; hinzu kommen 20 Neueingänge und 8 Löschungen. Seit dem Umzug auf einen älteren Rechner dauert eine Titelsuche bei hoher Auslastung bis zu 3,2 Sekunden, und die Sachbearbeitung meldet Ruckeln beim Einfügen. Ein Praktikant schlägt vor, die ArrayList durch eine HashMap zu ersetzen. Die Bibliothekarin benötigt zusätzlich eine täglich etwa 15-mal genutzte Funktion „alle Medien eines Sachgebiets zwischen zwei Erscheinungsjahren“. Der Arbeitsspeicher ist mit 512 MB begrenzt; ein Medienobjekt belegt im Mittel 1,8 KB, ein Indexeintrag etwa 48 Byte. Die Anwendung ist einzelthreaded; Messungen mit einem Profiler liegen nicht vor.
1. Analysiere die Laufzeiten der aktuellen ArrayList-Lösung für Titelsuche, Neueingang und Löschung. Erkläre, warum die gemessenen 3,2 s nicht allein mit der Datenstruktur begründet werden können.
Read the worked answer
Die ArrayList ist nach Inventarnummer sortiert. Die Titelsuche kann diese Ordnung nicht nutzen: Sie muss im schlechtesten Fall alle 12.400 Elemente prüfen, im Mittel etwa 6.200. Das ist O(n). Die Suche über die Inventarnummer könnte binär suchen (O(log n) ≈ 14 Vergleiche), wird im Code aber offenbar ebenfalls linear oder über indexOf ausgeführt. Einfügen an der sortierten Position ist O(log n) für die Position plus O(n) für das Verschieben; bei 20 Neueingängen pro Tag ist das unkritisch. Löschen ist ebenfalls O(n).
3,2 s für 6.200 Stringvergleiche sind mit reiner Rechenzeit nicht erklärbar: Bei 1 µs pro Vergleich wären es 6,2 ms. Ursachen können langsame I/O, eine Datenbankanbindung, unnötige Kopien, Garbage Collection, Terminal-Rendering oder sehr teure Stringoperationen sein. Ohne Profiler ist die Datenstruktur nicht als alleinige Ursache belegt. Die Schlussfolgerung lautet daher: Die Komplexität erklärt die Größenordnung, nicht aber die konkrete Latenz.
2. Bewerte den HashMap-Vorschlag im Hinblick auf die Bereichsanfrage und den Speicherplatz. Schlage eine geeignete Kombination von Datenstrukturen vor und begründe sie.
Read the worked answer
Eine HashMap löst nur exakte Schlüssel. Für die Inventarnummer ist sie gut (O(1)), für die Titel-Substringsuche hilft sie nicht, weil diese weiterhin einen Scan braucht. Für die Bereichsanfrage „Sachgebiet zwischen zwei Jahren“ ist eine HashMap ungeeignet, da sie keine Ordnung kennt; man müsste alle 12.400 Einträge prüfen.
Besser ist eine Kombination: eine HashMap für die Inventarnummer, eine TreeMap oder ein TreeSet mit Schlüssel (Sachgebiet, Jahr, Inventarnummer) für Bereichsabfragen (O(log n + k)), optional ein invertierter Index für Titelwörter. Speicher: 12.400 × 1,8 KB ≈ 22,3 MB für die Objekte; ein Index mit 48 Byte pro Eintrag ≈ 0,6 MB, also unproblematisch gegenüber 512 MB. Die HashMap nur als Ersatz für alles wäre eine Verschlechterung für Bereichsabfragen. Empfehlung: Kombination, messen, erst dann optimieren.
3. Eine Schülerin behauptet, bei 12.400 Datensätzen sei der Unterschied zwischen O(n) und O(log n) praktisch irrelevant. Nimm mit einer Rechnung Stellung.
Read the worked answer
6.200 Vergleiche gegenüber log2(12.400) ≈ 14: Das ist ein Faktor von rund 440. Bei 850 Suchen pro Tag sind das ca. 5,3 Millionen Vergleiche täglich, bei 200 Schultagen über eine Milliarde im Jahr. Das ist relevant, wenn der Vergleich teuer ist oder die Datenmenge wächst; bei 100.000 Medien wären es 50.000 statt 17 Vergleiche.
Allerdings zeigt die 3,2-s-Messung, dass die Konstante pro Vergleich dominiert. Die Aussage „praktisch irrelevant“ ist daher nur für die aktuelle Größe und einen billigen Vergleich richtig; sie wird falsch, wenn die Titelsuche als Teilsuche implementiert ist oder die Bibliothek wächst. Sinnvoll ist eine Messung mit realen Daten und ein Index für die häufigsten Abfragen, nicht die pauschale Ablehnung.