Wie nennt man das, wenn man die Big O-Ausführungszeit einer Funktion ändert? [Closed]

19

Nehmen wir an, ich habe eine Funktion, die eine Datenbank O(n^2)rechtzeitig sortiert . Ich möchte es überarbeiten, damit es O(n log(n))rechtzeitig ausgeführt wird, und dabei die grundlegende Funktionsweise der Operation ändern, während die Rückgabewerte und Eingaben gleich bleiben.

Wie nenne ich diese Refactoring-Aktivität?

"Speeding-up-ifying" scheint nicht ganz richtig zu sein, da Sie einen Algorithmus beschleunigen können, ohne die große O-Geschwindigkeit zu ändern, mit der er ausgeführt wird.

"Vereinfachung" scheint auch nicht richtig.

Wie nenne ich diese Aktivität?

Aktualisieren

Die beste Antwort, die ich finden konnte, ist die Reduzierung der asympotischen Zeitkomplexität.

Code-Flüsterer
quelle
Erwarten Sie, dass die Algorithmen nach der Änderung in den meisten Anwendungsfällen schneller sind? Manchmal ist es hilfreich, auch bei einem erwarteten durchschnittlichen Leistungseinbruch zu einer Komplexitätsklasse mit besserer Skalierung zu wechseln, um ein konsistenteres Leistungsverhalten zu erzielen.
Nat
22
Dies ist kein Refactoring
theonlygusti
6
Genau genommen läuft eine Funktion, die in der O(log(n))Zeit läuft, auch in der O(n^2)Zeit. Die Bedeutung von O(n^2)ist "wächst nicht schneller als quadratisch." Sie meinten wahrscheinlich Theta (log (n)), was "wächst so schnell wie log(n)" bedeutet. en.wikipedia.org/wiki/…
Džuris
4
<pedantic> Sie haben die Ausführungszeit einer Funktion nicht geändert. Eine Funktion ist eine Beziehung zwischen einer Domäne und einer Codomäne und existiert unabhängig von Ihren mickrigen menschlichen Implementierungsversuchen. Stattdessen haben Sie einen leistungsfähigeren Algorithmus gefunden, der die Funktion </ pedantic> <human> good job </ human>
implementiert
5
@theonlygusti: Es kommt darauf an. Wenn die Funktion zuvor eine Garantie / Garantien für Komplexität abgegeben hat, erfolgt keine Umgestaltung. Wenn es nichts garantiert, ist es Refactoring. Wenn es sogar ausdrücklich darum ging, keine Garantien zu geben, handelt es sich insbesondere um ein Refactoring.
Phresnel

Antworten:

44

Es wird normalerweise als "Leistungsoptimierung" bezeichnet , aber ich würde es nicht als "Refactoring" bezeichnen, da sich dieser Begriff normalerweise auf Änderungen im Code bezieht, die das sichtbare Verhalten nicht ändern . Und eine Veränderung in Big-O ist definitiv etwas, was ich als sichtbare Veränderung bezeichnen würde.

Dabei werde ich die grundlegende Funktionsweise der Operation ändern

In diesem Fall ist Ihre Optimierung eine Umschreibung dieser Funktion. Nicht jede Optimierung, auch wenn sie "Big-O" ändert, ist notwendigerweise eine Umschreibung, manchmal sind nur kleine Änderungen erforderlich, um eine solche Verbesserung zu erzielen, aber selbst dann zögere ich, den Begriff "Refactoring" dafür zu verwenden, weil es neigt dazu, einen falschen Eindruck über die Art der Änderung zu vermitteln.

BEARBEITEN: Ich habe die Refactoring-Liste von Fowler überprüft und unter diesen ~ 100 benannten Refactorings wird die allerletzte als "Ersatzalgorithmus" bezeichnet . Wenn wir dies als kanonische Referenz nehmen, gibt es eine kleine, graue Fläche, in der eine Optimierung der beschriebenen Form eine besondere Art des Refactorings genannt werden könnte (aber IMHO keine typische). Beachten Sie auch, dass Fowler bei allen Überarbeitungen stets darauf abzielte, das Design zu verbessern, wobei der Schwerpunkt auf der Wartbarkeit und Weiterentwicklung des vorhandenen Codes lag, ohne ihn neu zu schreiben, und eindeutig nicht auf der Leistungsoptimierung.

Doc Brown
quelle
10
Ja wirklich? Ich würde Refactoring für richtig halten, wenn sich die Anforderungen nicht ändern. Also .. Nein, wenn die Funktion BubbleSort heißt, aber ja, wenn es nur Sortieren ist
Ewan
3
@Ewan Ja, legal kann ein Refactoring eine Leistungsoptimierung sein, aber das erstere ist viel zu allgemein und erfasst die Auswirkungen der Änderungen nicht angemessen.
Deduplikator
1
Der Typ, der Refactoring (Fowler?) Erfand und prägte, stellte mich früh vor und die ganze Idee war mit automatischer Programmierung und nachweislich überprüfbaren Verbesserungen des Codes verbunden, die keinen Einfluss auf Eingabe und Ausgabe hatten.
Sentinel
1
@Steve. Einverstanden. Ich habe lediglich zum Konsens beigetragen, dass die Verbesserungen von Big O eine Verbesserung des Algorithmus darstellen und nicht, wie diese Algorithmen dargestellt oder beibehalten werden. Mit anderen Worten, die Aktivität ist eine Umschreibung
Sentinel
1
@Steve: Ja, das wusste ich. Ich dachte darüber nach, meiner Antwort eine Notiz hinzuzufügen. Meine Bearbeitung war nur eine Notiz, um deutlich zu machen, dass es einen kleinen grauen Bereich gibt.
Doc Brown
13

Ich glaube nicht, dass es einen Standardbegriff gibt, ein häufig verwendeter Begriff ist Optimieren, obwohl Verbessern , oder Beschleunigen wäre auch richtig, wenn klargestellt würde, dass es sich um Codeänderungen und nicht um Hardwareänderungen handelt.

ichantz
quelle
7

Wie andere gesagt haben, ist "Optimieren" der allgemeine Begriff zur Verbesserung der Leistung eines Algorithmus. Optimieren bedeutet jedoch oft, konstante Faktoren zu verbessern. Wenn ich kurz, aber deutlich sagen wollte, dass ich die asymptotische (zeitliche) Komplexität reduziert habe, würde ich sagen, dass ich "die asymptotische Leistung verbessert habe". Manchmal wird dies als "Verbesserung der Skalierung" bezeichnet, was heutzutage jedoch besonders vieldeutig ist.

Warnung : Die Reduzierung der asymptotischen Zeitkomplexität ist nicht unbedingt dasselbe wie die Optimierung im praktischen Kontext. Oft werden asymptotisch nicht optimale Algorithmen verwendet, da das Programm in Bezug auf den Bereich der Eingaben tatsächlich den weniger optimalen Algorithmen ausgesetzt ist, die eine bessere Leistung erbringen.

Derek Elkins
quelle
5

Es wird kontextabhängig sein.

"Beheben eines quadratischen Laufzeitleistungsfehlers" sehe ich normalerweise so. Ob dies jedoch korrigiert werden muss (eine Codeänderung), ist kontextabhängig.

Denken Sie daran, dass Datenbanken viele Tools zur Verbesserung der Zeitkomplexität bieten. Um beispielsweise die besten N Ergebnisse aus einer Datenbank zu erhalten, sagen Sie es einfach. Wenn ineffizientes Kludge in einen integrierten optimierten Aufruf konvertiert wird, erscheint eine Erklärung überflüssig.

Der Grund, warum ich einen Algorithmus mit quadratischer Laufzeit für eine Codeüberprüfung (Diskussion) halte, ist nicht so sehr, dass er langsam ist (langsam ist relativ; quadratisch ist schnell im Vergleich zu exponentiell), sondern dass menschliche Intuition (wie Ihre Kunden oder Programmiererkollegen) fühlen sich mit einer Softwarefunktionalität, die aufgrund der Vermischung der Erwartungen aus dem Alltagsleben zu weit von der linearen Laufzeit abweicht, von Natur aus unwohl.

Viele Kundenbeschwerden über die Softwareleistung fallen in diese beiden Kategorien:

  • Das gesamte System (Software und Hardware) wurde basierend auf der geschätzten Nutzung spezifiziert. Letzte Woche läuft alles gut, eine bestimmte Funktionalität hat weniger als 5 Sekunden gedauert. Diese Woche nach der Installation eines Updates dauert die gleiche Funktionalität länger als 1 Minute.

    • Dies ist ein Vergleich mit einer zuvor gemessenen Leistung. Der Kunde hält die zukünftige Leistung für einen absoluten Maßstab menschlicher Zeitskala (von Sekunden bis Minuten).
  • Ich habe 100 Aufträge an das System übermittelt. Warum dauert die Bearbeitung 400-mal so lange wie ein einzelner Job?

    • Der Kunde erwartet eine lineare Bearbeitungszeit. In der Tat kann der Kunde nicht verstehen oder akzeptieren, dass es Aufgaben gibt, die langsamer als linear sind.

Aus diesem Grund wird ein Kunde die Ausführungszeit als Fehler betrachten, wenn beide zutreffen:

  • Langsamer als linear
  • Auffällig (dh fällt in den menschlichen Zeitbereich (länger als Sekunden oder Minuten) bei typischen Aufgabengrößen)

Berechtigte Argumente, die erklären, dass ein quadratischer Laufzeitalgorithmus kein Problem darstellt (dh keine Codeänderung verdient):

  • Die Größe der Aufgabe, die normalerweise von dieser quadratischen Laufzeitfunktion verarbeitet wird, ist etwas begrenzt
  • In Anbetracht des typischen Größenbereichs ist die tatsächliche (absolute) Ausführungszeit immer noch klein genug, um verworfen zu werden
  • Wenn ein Benutzer tatsächlich versucht, eine Aufgabe zu senden, die groß genug ist, um erkennbar zu sein, erhält der Benutzer eine Warnmeldung über die lange Laufzeit
  • Die Benutzer des Systems sind alle Experten und wissen daher, was sie tun. Beispielsweise sollten Benutzer einer API das Kleingedruckte in der API-Dokumentation gelesen haben.

Viele Algorithmen, die für die typische Anwendungsentwicklung nützlich sind, sind tatsächlich langsamer als linear (meistens O (N log N), wie beim Sortieren). Daher wird eine umfangreiche Software tatsächlich versuchen, dies zu umgehen, indem nur der relevante Teil des Dokuments sortiert wird Daten oder Histogramm (statistische) Filtertechniken verwenden, die einen ähnlichen Effekt erzielen.

Dies gilt für Softwarekunden. Wenn Sie jedoch die Benutzer einer Softwarebibliothek oder einer API-Funktion ebenfalls als "Kunden" betrachten, gilt die Antwort weiterhin.

rwong
quelle
2

Wenn der ursprüngliche Algorithmus korrekt implementiert wurde (oder Fehler, die irrelevant waren), dann "Algorithmus ändern" oder "Algorithmusersetzung" , da solche Änderungen bedeuten, dass Sie genau das tun. Ersetzen eines Algorithmus mit einer anderen zeitlichen Komplexität als der zuvor verwendeten.

Wenn die Komplexität der vorherigen Zeit auf einen Fehler in der Implementierung zurückzuführen war (z. B. dass Sie versehentlich den Startpunkt einer inneren Schleife in einer Sequenz zurückgesetzt haben, sodass O (n) zu O (n 2 ) wurde), dann "Reparieren" ein quadratischer Kostenfehler " oder ähnlich.

Es gibt eine Überlappung, in diesem Fall ist die Auswirkung auf den Code dieselbe, wenn Sie von Anfang an wissen, dass die Arbeit in O (n) Zeit ausgeführt werden konnte und die O (n 2 ) Zeit ein Fehler war, oder wenn Sie haben es zuerst absichtlich in O (n 2 ) implementiert und dann festgestellt, dass es ohne Zurücksetzen des Startpunkts immer noch korrekt funktioniert, und haben daher einen O (n) -Algorithmus durch einen O (n 2 ) -Algorithmus ersetzt.

Jon Hanna
quelle
1

Geschwindigkeitsoptimierung um eine Größenordnung. Obwohl dies eine mathematisch inkorrekte Sprache ist, vermittelt sie am besten die Vorstellung, dass der Orden geändert wird.

Verbesserte die Skalierbarkeit. gehört auch.

Joop Eggen
quelle