Frage Warum enthält Java nicht die Komplexität von Zeit und Raum für jede Funktion im Javadoc?


Hallo ich möchte wissen, was ist die Zeit Komplexität der "replaceAll" -Funktion der String-Klasse, aber ich kann keine Informationen darüber finden. (http://docs.oracle.com/javase/6/docs/api/java/lang/String.html)

Wäre es nicht besser für Java, die Komplexität in das Javadoc aufzunehmen? Ich glaube, es ist eine sehr wichtige Sache für jemanden zu wissen.


13
2018-04-10 15:36


Ursprung


Antworten:


Die meisten Funktionen haben ziemlich unkomplizierte Zeitkomplexität. AFAIK, replaceAlle ist O (n)

MEINER BESCHEIDENEN MEINUNG NACH. Es gibt nichts Besseres, als dies empirisch zu testen, z. mit einem Profiler, weil es sehr wahrscheinlich ist, dass 99% der Methoden, die Sie verwenden, wenig oder keine Auswirkungen auf die Leistung Ihrer Anwendung haben.


9
2018-04-10 15:40



Die Komplexität kann dokumentiert werden, wenn sie garantiert ist. Zum Beispiel dokumentieren einige der Collections-Klassen Komplexitätsgarantien. Zum Beispiel von HashMap:

Diese Implementierung bietet konstante Leistung für die grundlegenden Operationen (get and put) ...

Manchmal ist die Komplexität jedoch:

  • Nicht garantiert und kann mit Änderungen an der Implementierung geändert werden.
  • Offensichtlich O (1).

3
2018-04-10 15:40



Die Javadocs der Java-API spezifizieren einen allgemeinen Vertrag von Was muss mit jeder Methode gemacht werden, nicht Wie. Jeder Implementierer der API (z. B. OpenJDK, Oracle's JDK usw.) hat eine gewisse Freiheit bei der Implementierung jedes Vertrags, und diese Freiheit kann Optimierungen und sogar Leistungseinbußen beinhalten. Daher spezifizieren die Javadocs im Allgemeinen keine Details wie Zeit / Komplexität von Funktionen, außer es ist absolut notwendig, dass eine Methode bestimmte Leistungsanforderungen erfüllt.


1
2018-04-10 15:41



Wenn Sie die Raum-Zeit-Komplexität von Grundoperationen verwenden, um Designentscheidungen zu treffen, dann machen Sie fast sicher Fehler.

Erstellen Sie zuerst eine korrekte Anwendung und profilieren Sie sie. Dann optimieren Sie, was der Profilierungsprozess als Engpässe enthüllt.


0
2018-04-10 15:45



Die allgemeine Antwort lautet, dass die Komplexität typischerweise von Faktoren abhängt, die zu schwer zu analysieren sind. Dies gilt sicherlich für String.replaceAll, wo die effektive Komplexität entscheidend von der regex Zeichenfolge. (Eine schlecht entworfene Regex kann dazu führen, dass die übereinstimmende Veerryyy langsam wird.)


0
2018-04-10 15:58