Frage Effektives Java-Element 17: Wie kann das Überschreiben von removeRange () die Leistung verbessern?


In dem Buch Effective Java von Joshua Bloch wird diskutiert, wie eine Klasse "vernünftig gewählte geschützte Methoden" als Haken in ihre internen Abläufe einbringen kann.
Der Autor zitiert dann die Dokumentation in AbstractList.removeRange():

Diese Methode wird von der clear Operation auf dieser Liste und ihre   Unterlisten. Überschreiben Sie diese Methode, um die Interna von   Die Listenimplementierung kann die Performance von. erheblich verbessern   das clear Operation auf dieser Liste und ihren Unterlisten.

Meine Frage ist, wie kann das Überschreiben dieser Methode die Leistung verbessern (mehr als einfach nicht überschreiben)? Kann jemand ein Beispiel dafür geben?


12
2018-03-12 02:50


Ursprung


Antworten:


Nehmen wir ein konkretes Beispiel: Angenommen, Ihre Implementierung wird von einem dynamischen Array unterstützt (so ArrayList funktioniert zum Beispiel). Angenommen, Sie möchten Elemente im Bereich [Start, Ende] entfernen. Die Standardimplementierung von removeRange funktioniert, indem Sie einen Iterator zur Positionierung bringen start, dann anruft remove() die entsprechende Anzahl von Malen.

Jedes Mal remove() heißt, die dynamische Array-Implementierung muss alle Elemente an der Position mischen start + 1 und einen Punkt vorrücken, um die im entfernten Element verbleibende Lücke zu füllen. Dies könnte möglicherweise Zeit O (n) dauern, da möglicherweise alle Array-Elemente gemischt werden müssen. Dies bedeutet, dass wenn Sie insgesamt entfernen k Elemente aus der Liste, der naive Ansatz braucht Zeit O (kn), da du O (n) kmal arbeitest.

Betrachten Sie nun einen viel besseren Ansatz: Kopieren Sie das Element an der Position end positionieren start, dann Element end + 1 positionieren start + 1usw., bis alle Elemente kopiert sind. Dies erfordert, dass Sie nur insgesamt O (n) arbeiten, weil jedes Element höchstens einmal verschoben wird. Verglichen mit dem O (KN) -Ansatz, der durch den naiven Algorithmus gegeben wird, ist dies eine enorme Leistungsverbesserung. Folglich überschreiben removeRange Dieser effizientere Algorithmus kann die Leistung erheblich steigern.

Hoffe das hilft!


19
2018-03-12 02:57



Wie in den Javadocs der Methode angegeben:

Diese Implementierung ruft einen Listeniterator ab fromIndex ab und ruft wiederholt ListIterator.next gefolgt von ListIterator.remove auf, bis der gesamte Bereich entfernt wurde.

Da diese abstrakte Klasse nichts über die Interna ihrer Unterklassen weiß, stützt sie sich auf diesen generischen Algorithmus, der zeitlich proportional zur Anzahl der zu entfernenden Objekte läuft.

Wenn Sie beispielsweise eine Unterklasse implementiert haben, die Elemente als verknüpfte Liste speichert. Dann könnten Sie diese Tatsache ausnutzen und diese Methode überschreiben, um einen verknüpften listspezifischen Algorithmus zu verwenden (Zeiger auf verschieben fromIndex deuten auf toIndex) die in konstanter Zeit läuft. Sie haben dadurch die Leistung verbessert, weil Sie die Interna genutzt haben.


11
2018-03-12 03:00



Indem Sie diese Methode überschreiben, können Sie diesen generischen Algorithmus gemäß Ihren Anforderungen als Indexierungsproblem verwenden. Da es sich um eine geschützte Methode in AbstractList und auch in ArrayList und seiner Implementierung handelt, arbeiten sie als iterative Aufrufe von remove (), die jedes Mal alle auf der rechten Seite des entfernten Elements verfügbaren Elemente um einen Index verschieben müssen. Offensichtlich ist es nicht effektiv, also können Sie es besser arbeiten lassen.


0
2018-03-12 05:49