Ist es wichtig, dass eine Lösung effizient ist?

9

Ich löse viele Probleme, hauptsächlich von Top Coder. Ich werde für viele Antworten bekommen, aber meistens habe ich eine ineffiziente Lösung.

Ist es in realen Implementierungen wirklich wichtig, dass eine Lösung des Problems effizient ist? Wenn ja, wie kann ich es verbessern?

Ameisen
quelle
4
Fragen Sie vom Standpunkt eines Wettbewerbs oder vom Standpunkt der realen Implementierung aus?
rjzii
@RobZ: In realen Implementierungen
Ant's
1
"reale Welt" deckt viel Boden ab. Eingebettet? Serveranwendungen? Mobile Anwendungen? Einzelbenutzer-PC-Software? Wissenschaftliche Simulationen? Die Antworten sind für sie nicht unbedingt gleich.
David Thornley

Antworten:

34

Die beste Lösung ist die, die (in der Reihenfolge ihrer zunehmenden Bedeutung) effizient, wartbar und erledigt ist .

^^^ Das ist das einzige, was Sie wirklich aus dieser Antwort entnehmen müssen. ^^^

Effizienz ist wichtig . Vielleicht etwas weniger als früher aufgrund unserer Fülle an Hardware, aber Leistung ist ein Merkmal . In einem Wettbewerb ist Effizienz offensichtlich wichtig. Sie sollten wissen, wie man effizienten Code schreibt. Noch wichtiger ist, dass Sie die Best Practices kennen, die effizienten Code mit guter Leistung liefern, ohne die Aktualität oder Wartbarkeit einer Anwendung zu beeinträchtigen. Hier bringt die Erfahrungstiefe mit einer Plattform und Sprache viele Erträge.

Wichtiger (in 95% der Fälle) ist jedoch eine fertige, wartbare Lösung. Ohne ein fertiges Produkt spielt es keine Rolle, wie effizient oder wartbar die Lösung ist. Wenn Sie außerordentlich viel Zeit benötigen, um einen Fehler zu verfolgen und zu beheben oder eine neue Funktion hinzuzufügen, spielt es keine Rolle, wie effizient die Lösung ist. Aber Effizienz und Leistung sind zweifellos wichtig, egal was jemand sagen mag.

Mike Cellini
quelle
3
Jep. Und ein schrecklich ineffizientes Programm, das sowohl korrekt als auch erledigt ist, gibt Ihnen etwas, an dem Sie Ihre Verbesserungen testen können.
Mike Sherrill 'Cat Recall'
1
Der wichtigste Teil davon ist die Kenntnis der Best Practices für Effizienz, insbesondere bei der Datenbankentwicklung, bei der ich persönlich Effizienz über Wartbarkeit stellen würde. Benutzer legen großen Wert auf Leistung. Ich habe oft gesehen, dass effizienterer Code als schwieriger zu warten angesehen wird, aber nur, weil der Entwickler den effizienteren Code zunächst nicht verstanden hat. Sobald Sie sich mit den Techniken vertraut gemacht haben, gehen Sie zu diesen Techniken als erste Wahl und sie werden einfacher zu warten, weil Sie verstehen, warum sie funktionieren.
HLGEM
@HLGEM Wenn es einen Teil dieser Antwort gab, den ich als allgemeines Prinzip (neben der ersten Zeile) bekräftigen möchte, dann sind es die Best Practices für das Schreiben von effizientem Code. Und Sie haben Recht mit dem Kommentar, dass effizientes SQL wichtig ist.
Mike Cellini
8

Ich würde Mike Cellini zustimmen, das einzige, was ich hinzufügen würde, ist.

Ist etwas "effizient genug"? Zum Beispiel gibt es aus Anwendersicht keinen großen Unterschied zwischen einer Funktion, die in 0,00001 Sekunden abgeschlossen ist, oder einer Funktion, die in 0,1 Sekunden abgeschlossen ist, obwohl eine viel effizienter als die andere ist. Eine Funktion, die in 10 Minuten abgeschlossen ist, unterscheidet sich (für den Benutzer) nicht wesentlich von einer Funktion, die in 12 Minuten abgeschlossen ist. In beiden Fällen würde der Benutzer eine Tasse Kaffee bekommen oder mit einer anderen Aufgabe fortfahren.

Ich habe Effizienz als "effizienten Benutzer" und nicht als effizienten Algorithmus gesehen.

Jaydee
quelle
Als Faustregel habe ich gehört, dass ein Benutzer eine Verbesserung um 20% feststellen kann. Beide scheinen sich zu qualifizieren. Ich denke, ein Benutzer könnte tatsächlich einen Unterschied in der Reaktionsfähigkeit zwischen 0,1 und 0,00001 Sekunden spüren.
Chris Pitman
Chris, Sie haben vielleicht Recht, dass ein Benutzer den Unterschied zwischen den beiden Systemen nebeneinander bemerken könnte, aber würde ein System einen Benutzer bei seiner Arbeit spürbar effizienter machen? Meine Beobachtung (ich mache das seit über 25 Jahren) ist, dass die beiden Systeme es dem Benutzer ermöglichen würden, in einer bestimmten Zeit die gleiche Menge an Arbeit zu erledigen.
Jaydee
2

Im Allgemeinen ist die wichtigste Lösung für ein Problem diejenige, die tatsächlich existiert und für die Fälle gültig ist, wie sie für Ihr Problem existieren. Mit anderen Worten, vermeiden Sie vorzeitige Optimierung, bis Sie tatsächlich wissen, dass Sie ineffizienten Code haben oder effizienten Code, der schneller sein muss.

Vergessen Sie auch nicht, dass die beste Lösung für Ihre Anwendung möglicherweise nicht die allgemeine Falllösung ist. Fall und Punkt, vor ein paar Jahren gab ein Professor unserer Klasse ein Problem, bei dem wir die ersten 10 Zahlen eines bestimmten Typs drucken sollten (Entschuldigung, mein Gedächtnis versagt mir hinsichtlich des Typs, aber es war eine der ungewöhnlicheren Zahlen Klassen) und wir erhielten einen Test, um sicherzustellen, dass die Nummer vom angegebenen Typ war. Dies war das Ausmaß des Problems, das uns gegeben wurde, und es wurde uns mitgeteilt, dass es am nächsten Tag fällig sei und die effizienteste Lösung die volle Gutschrift erhalten würde. In der folgenden Vorlesung fasste der Professor die Ergebnisse zusammen:

  • Einige Schüler verwendeten eine einfache Schleife und die bereitgestellte Formel, um zu überprüfen, ob die Zahlen korrekt waren, und zeigten sie an, langsam, aber erledigten die Arbeit, O (n ^ 3).
  • Andere Studenten recherchierten und fanden eine Formel, mit der besser überprüft werden konnte, ob eine bestimmte Zahl gültig war. Diese Programme liefen viel schneller, O (n ^ 2).
  • Ein Schüler verwendete die langsame Formel, um die Werte zu generieren, kopierte sie dann in ein konstantes Array in seinem Code und zeigte den Inhalt von O (n) an.

Die endgültige Lösung wurde vom Professor als die effizienteste beurteilt. Es stellt sich heraus, dass das Problem tatsächlich eine Übung war, um das Problem vollständig zu verstehen und nicht nur auszugehen und die effizienteste Lösung zu finden.

Der Punkt des oben Gesagten ist, dass es im Allgemeinen besser ist, sich Zeit zu nehmen, um sicherzustellen, dass Sie das Problem wirklich verstehen, bevor Sie Code schreiben oder versuchen, Code zu optimieren, wenn Sie eine effiziente Lösung für ein Problem finden möchten. Wenn Sie eine Reihe von Referenzwerten in einem konstanten Array speichern können, ist es vom Standpunkt der Leistung aus besser, dies zu tun, als zu versuchen, einen ausgefallenen Algorithmus zu schreiben.

Vergessen Sie auch nicht, dass für die meisten Anwendungen die Entwickler selbst die einzigen Personen sind, die dazu neigen, ineffizienten Code zu sehen (wenn er nicht unnötig ineffizient ist!). Wenn Sie sauberen Code schreiben, der nur genau das tut, was er tun muss, besteht die Wahrscheinlichkeit, dass die Benutzer bei der Arbeit mit Ihrem Programm die meiste Zeit keine Leistungsprobleme bemerken und nur die Teile optimieren, die sie erwähnen Du.

rjzii
quelle
2

Das hängt von der Struktur des Wettbewerbs, aber in der Regel, ja: Leistung ist eine Überlegung der meistes Zeit, nach dessenderen Dokumentation . Manchmal, wie im späteren Link, muss man jagen, aber um zu zitieren:

Schreiben Sie sauberen, klaren und effizienten Code. Auch wenn es keine spezielle Überprüfungsposition dafür gibt, reagieren Prüfer wahrscheinlich besser auf Code, der für sie leicht zu lesen und zu verstehen ist. Mit effizientem Code erhalten Sie einen potenziellen Leistungsvorteil bei Stress- und Benchmark-Tests sowie wahrscheinliche Anerkennung (und einige zusätzliche Punkte) von den Prüfern.

Der beste Weg, dies zu verbessern, besteht darin, Code zu schreiben, der effizient ist, was Sie bereits tun. Selbst wenn Sie die Arbeit abgeschlossen haben, nehmen Sie sich Zeit, um die Effizienz zu verbessern - auch nach dem Wettbewerb - und das wird sich auszahlen.

Sie möchten wahrscheinlich auch in die Theorie investieren, beispielsweise in Bücher über Algorithmen , die Ihnen zwei Dinge bieten können: effizientere Werkzeuge zur Lösung eines bestimmten Problems und effizientere Mechanismen zur Identifizierung des zu lösenden Problems.

Schließlich sind Informatik - Kurse immer verfügbar Online , und decken den Hintergrund , den Sie verbessern müssen.

Daniel Pittman
quelle
Es gibt eine neuere Ausgabe des Algorithmus-Design-Handbuchs. (11 Jahre zwischen den beiden). Stimmt etwas mit dem neueren nicht? Zumal es billiger ist als das alte. Wenn ja, sollte dies vielleicht in Ihrer Antwort angesprochen werden.
Welt Ingenieur
Nein, ich habe gerade die erste aufgelistet, die ich bei Amazon gefunden habe, und habe nicht überprüft, ob es sich um die zweite Ausgabe handelt.
Daniel Pittman
1

Wie effizient eine Lösung sein muss, hängt von einer Reihe von Faktoren ab. Das Wichtigste ist zu wissen, was Ihr Benutzer will. Hier einige Beispiele.

  1. Wenn Sie der einzige Benutzer eines Codeblocks sind und dieser für Sie einwandfrei funktioniert, ist alles in Ordnung.
  2. Wenn Ihr Programm verkauft werden soll, müssen Sie eine Zielplattform im Auge haben. Testen Sie es mit dieser Plattform. Wenn das Programm außergewöhnlich langsam ist, müssen Sie daran arbeiten, es effizienter zu gestalten. Wenn es Ihnen in Ordnung erscheint, geben Sie es an andere Benutzer weiter und prüfen Sie, ob sie damit einverstanden sind.
  3. Vielleicht hat das Programm andere Überlegungen. Wenn Sie beispielsweise ein serverbasiertes Programm erstellen, müssen Sie möglicherweise sehr hart arbeiten, um das Programm so effizient wie möglich zu gestalten. Wenn es auf einem Mikroprozessor ausgeführt wird, stellen Sie sicher, dass es auch dort funktioniert.

So machen Sie Ihren Code effizienter:

  1. Der erste Schritt besteht darin, sich ein Bild davon zu machen, was am meisten Zeit in Anspruch nimmt. Der Trick besteht darin, einen sogenannten Profiling-Code auszuführen. Suchen Sie nach dem, was am meisten Zeit in Anspruch nimmt, und prüfen Sie, ob Sie einen Weg finden können, um den Betrieb zu beschleunigen.
  2. Vielleicht ist der wichtigste begrenzende Faktor das Gedächtnis. Wenn dies der Fall ist, suchen Sie nach dem Speicherplatz, der viel Speicherplatz beansprucht, und prüfen Sie, wie Sie ihn reduzieren können.

Die Optimierung hat ein ganzes Feld, aber die beiden obigen Tipps sollten Ihnen zumindest den Einstieg erleichtern.

PearsonArtPhoto
quelle
1

Für einen Wettbewerb müssen Sie verstehen, wer die Richter sind und worum es ihnen geht - wenn sie nach großartigen Programmierern suchen und nicht mehr, dann erhalten Sie ein Lob für effizienteren Code.

In der realen Welt spielt das in der Regel keine Rolle. Eine der Schlüsselideen der Softwareentwicklung lautet: "Optimieren Sie nicht, was Sie nicht wissen, muss optimiert werden", dann "Optimieren Sie nur, wenn nachgewiesen wurde, dass es erforderlich ist".

Viele Praktiker werden argumentieren, dass dies zu aufgeblähtem, ineffizientem Code führt, der nicht einfach repariert werden kann, und in einigen Randfällen (über die sie sich krähen, als ob die meisten Codierer dies jeden Tag den ganzen Tag tun) sind sie korrekt. Allerdings haben nicht viele Softwareentwicklungsprojekte die gemessenen Ergebnisse "Leistung: Schneller als nötig, Kosten: Wen interessiert das, Lieferzeit: Irgendwann in diesem Jahrzehnt". In der realen Welt ist es normalerweise "Ich will es billig, ich will es gestern, ich will." es funktioniert ".

mattnz
quelle