Werden Algorithmen (und die Effizienz im Allgemeinen) immer weniger wichtig?

29

Ist es weniger wichtig, Algorithmen zu kennen und effizient zu sein, da der Kauf von Rechenleistung viel günstiger ist als in der Vergangenheit? Es ist klar, dass Sie eine Endlosschleife vermeiden möchten, also geht nicht alles. Aber wenn Sie eine bessere Hardware haben, könnten Sie dann eine schlechtere Software haben?

efficiency Quora Feans
quelle

2

"sowohl ja als auch nein"!

VZN

4

Ist die Geschwindigkeit der Schifffahrt weniger wichtig, seit es Flugzeuge gibt und nicht mehr alle transatlantischen Güter auf Schiffen befördert werden müssen? FedEx- und DHL-Kunden glauben das nicht.

Peter Shor

2

Wenn die Größe der Eingabe groß genug ist, ist ein Unterschied in der Größenordnung zwischen den Algorithmen wichtig, egal wie schnell die Maschine ist. Aber gelegentlich werde ich getäuscht, Änderungen vorzunehmen, um einen konstanten Faktorunterschied zu "optimieren", nur um festzustellen, dass die Verwendung von Ausdrücken, die in den syntaktischen Zucker der Programmiersprache <cough> Python </ cough> integriert sind, erheblich schneller ist als meine "Optimierung".

Kojiro

siehe auch moores law

vzn 13.10.13

Eine interessante Fallstudie ist hier z. B. Windows, das selbst auf hochoptimierter Hardware in vielerlei Hinsicht weniger effizient läuft als früher ... Genau wie das Moores-Gesetz die Hardware verbessert, scheint es in Software ein entsprechendes Inflationsgesetz zu geben, in dem Moderne Software wird immer leistungsfähiger, neue Schichten werden hinzugefügt und multipliziert. Dies entspricht in etwa der Art und Weise, wie ein Gas das gesamte verfügbare Volumen ausfüllt. Oder in der ein Budget, egal wie groß oder größer es ist, immer aufgebraucht wird oder etwas überrannt ... siehe auch evolutionary race

vzn 13.10.13

31

Ich mag das Beispiel aus dem Buch Einführung in Algorithmen , das die Bedeutung der Algorithmeneffizienz veranschaulicht:

Vergleichen wir zwei Sortieralgorithmen: Einfügesortierung und Mischsortierung . Ihre Komplexität ist bzw. . In der Regel hat die Sortierung beim Zusammenführen einen größeren konstanten Faktor. Nehmen wir also . $O(n^2) = c_1n^2$ $O(n\log n) = c_2n \lg n$ $c_1 < c_2$

Zur Beantwortung Ihrer Frage wird die Ausführungszeit eines schnelleren Computers (A), auf dem der Einfügesortieralgorithmus ausgeführt wird, mit einem langsameren Computer (B), auf dem der Zusammenführungssortieralgorithmus ausgeführt wird, verglichen.

Wir nehmen an:

Die Größe des Eingabeproblems beträgt 10 Millionen Zahlen: ; $n=10^7$
Computer A führt Anweisungen pro Sekunde aus (~ GHz); $10^{10}$
Computer B führt nur Befehle pro Sekunde aus (~ 10MHz); $10^7$
Die konstanten Faktoren sind (was leicht überschätzt wird) und (in Wirklichkeit ist es kleiner). $c_1=2$ $c_2=50$

Also mit diesen Annahmen braucht es

\frac{2 \cdot (10^{7})^{2} Anleitung}{10^{10} Anleitung / zweite} = 2 \cdot 10^{4} Sekunden

$\frac{2 \cdot (10^7)^2 \text{ instructions}} {10^{10} \text{ instructions}/\text{second}} = 2 \cdot 10^4 \text{ seconds}$ für der Computer A zum Sortieren von Zahlen und

10^{7}

$10^7$

\frac{50 \cdot 10^{7} \lg 10^{7} Anleitung}{10^{7} Anleitung / zweite} \approx 1163 Sekunden

$\frac{50 \cdot 10^7 \lg 10^7 \text{ instructions}} {10^{7} \text{ instructions}/\text{second}} \approx 1163 \text{ seconds}$

für den Computer B.

Auf diese Weise kann der Computer, der 1000-mal langsamer ist, das Problem 17-mal schneller lösen. In der Realität wird der Vorteil der Zusammenführungssortierung noch bedeutender und nimmt mit der Größe des Problems zu. Ich hoffe, dieses Beispiel hilft Ihnen bei der Beantwortung Ihrer Frage.

Hierbei geht es jedoch nicht nur um die Komplexität von Algorithmen. Heutzutage ist es fast unmöglich, eine signifikante Beschleunigung nur durch die Verwendung des Computers mit höherer CPU-Frequenz zu erzielen. Die Menschen müssen Algorithmen für Multi-Core-Systeme entwerfen, die sich gut skalieren lassen. Dies ist auch eine knifflige Aufgabe, da mit der Zunahme der Kerne auch der Overhead (zum Beispiel für die Verwaltung der Speicherzugriffe) zunimmt. Es ist also fast unmöglich, eine lineare Beschleunigung zu erzielen.

Zusammenfassend ist das Design effizienter Algorithmen heute genauso wichtig wie früher, da weder Frequenzerhöhung noch zusätzliche Kerne die Geschwindigkeit erhöhen, die der effiziente Algorithmus mit sich bringt.

Pavel Zaichenkov
quelle

4

Es ist erwähnenswert, dass sich die Unmöglichkeit der linearen Beschleunigung aus Amdhals Gesetz ergibt .

Bartosz Przybylski

Amdhals Gesetz ist nicht immer anwendbar. In der Informatik gibt es zahlreiche Probleme, bei denen der Anteil nicht parallelisierbarer Arbeit mit zunehmender Problemgröße auf Null sinkt. Angenommen, die Berechnung von nimmt Arbeit in Anspruch, und Sie müssen für verschiedene berechnen . In der Serie ist der Zeitaufwand , während parallel zu Prozessoren die Arbeit .

f (x)

$f(x)$

n^{2}

$n^2$

\sum_{i = 1}^{n} f (x_{i})

$\sum_{i=1}^n f(x_i)$

n

$n$

x_{i}^{'} s

$x_i's$

O (n \cdot n^{2} + n) = O (n^{3})

$O(n\cdot n^2 + n) = O(n^3)$

n

$n$

O (n^{2} + n) = O (n^{2})

$O(n^2 + n) = O(n^2)$

Nick Alger

"Der Computer, der 1000-mal langsamer ist, kann das Problem 17-mal schneller lösen." Dies ist eine falsche Aussage, da Sie Hardwaregeschwindigkeit und verschiedene Algorithmen gleichzeitig kombinieren. Vergleichen Sie lieber Computer A mit Computer B für jede Sorte separat. (Warum kann ich auf Computer A keine Zusammenführungssortierung oder auf Computer B keine Einfügungssortierung verwenden?)

AquaAlex

3

@AquaAlex, das Beispiel soll zeigen, dass der langsame Computer den schnellen nur mit Hilfe des ausgewählten Algorithmus übertreffen kann. Wir könnten die Ausführungszeit für jeden Typ von Sortierung separat vergleichen oder Merge-Sortierung für A und Insertions-Sortierung für B ausführen. Es ist jedoch nicht sinnvoll zu zeigen, dass ein schnellerer Computer in der Regel eine bessere Leistung als ein langsamer Computer erbringt.

Pavel Zaichenkov

OK, die Idee war zu zeigen, dass ein effizienterer Algorithmus auch bei schnellerer CPU-Auslastung und größerem Speicher noch am Tag Gewicht hat.

AquaAlex

36

Andererseits. Während die Hardware immer billiger wird, finden verschiedene andere Entwicklungen statt.

Erstens wächst die zu verarbeitende Datenmenge exponentiell. Dies führte zur Untersuchung quasilinearer Zeitalgorithmen und des Bereichs Big Data . Denken Sie beispielsweise an Suchmaschinen - sie müssen große Mengen an Abfragen bearbeiten, große Datenmengen verarbeiten und dies schnell erledigen. Algorithmen sind wichtiger denn je.

Zweitens wächst der Bereich des maschinellen Lernens stark und voller Algorithmen (wenn auch anders als das, was Sie in Ihrem BA lernen). Das Gebiet floriert, und von Zeit zu Zeit wird ein wirklich neuer Algorithmus erfunden, der die Leistung erheblich verbessert.

Drittens verteilte Algorithmen sind wichtiger geworden, da wir ein Hindernis bei der Steigerung CPU Verarbeitung schlagen Geschwindigkeit . Heutzutage wird die Rechenleistung durch Parallelisierung erhöht , und dazu sind spezielle Algorithmen erforderlich .

Viertens setzen moderne Programmierparadigmen Methoden für virtuelle Maschinen zur Bekämpfung von Sicherheitslücken ein, um der zunehmenden Leistung von CPUs entgegenzuwirken. Das verlangsamt diese Programme spürbar. Zusätzlich zum Rätsel investiert Ihr Betriebssystem mehr CPU-Zeit auf Knopfdruck und lässt weniger CPU-Zeit für Ihre eigentlichen Programme übrig, was CPU-intensive Algorithmen wie Videokomprimierung und -dekomprimierung beinhalten könnte. Hardware ist zwar schneller, wird aber nicht so effizient genutzt.

Zusammenfassende, effiziente Algorithmen sind erforderlich, um große Datenmengen verarbeiten zu können. Auf dem Gebiet der künstlichen Intelligenz tauchen neue Arten von Algorithmen auf . verteilte Algorithmen rücken in den Fokus; Die CPU-Leistung wird aus verschiedenen Gründen weniger effizient genutzt (vor allem aber, weil Computer leistungsfähiger werden). Algorithmen sind noch nicht tot.

Yuval Filmus
quelle

"Algorithmen sind noch nicht tot" ... im Gegenteil, wir werden wahrscheinlich ein "goldenes Zeitalter der Algorithmen"

durchleben

12

Das Wissen über Algorithmen ist viel mehr als das Schreiben schneller Algorithmen.

Außerdem erhalten Sie Problemlösungsmethoden (z. B. Teilen und Erobern, dynamisches Programmieren, Gier, Reduzieren, lineares Programmieren usw.), die Sie anwenden können, wenn Sie sich einem neuen und herausfordernden Problem nähern. Ein geeigneter Ansatz führt normalerweise zu Codes, die einfacher und viel schneller zu schreiben sind. Daher muss ich Kevins Antwort ablehnen, da nicht sorgfältig zusammengestellte Codes oft nicht nur langsam, sondern auch kompliziert sind. Ich mag dieses Zitat von David Parnas:

Ich höre Entwickler oft als "jemanden, der weiß, wie man schnell ein großes System erstellt". Es ist kein Trick, große Systeme schnell aufzubauen. je schneller du sie baust, desto größer werden sie!

(Natürlich müssen wir auch Algorithmen mit Software-Design-Methoden kombinieren, um gute Codes zu schreiben.)

Die Kenntnis der Algorithmen zeigt uns auch, wie Sie Ihre Daten so organisieren, dass Sie sie durch die Verwendung von Datenstrukturen einfacher und effizienter verarbeiten können .

Darüber hinaus gibt es uns , einen Weg zu schätzen die Effizienz Ihres Ansatz und die Kompromisse zwischen verschiedenen Ansätzen in der Bezeichnung der Zeitkomplexität, Platzkomplexität und die Komplexität der Codes zu verstehen. Das Wissen um diese Kompromisse ist der Schlüssel, um innerhalb Ihrer Ressourcenbeschränkungen die richtige Entscheidung zu treffen.

Zur Bedeutung der Softwareeffizienz möchte ich das Wirthsche Gesetz zitieren:

Software wird langsamer als Hardware schneller.

Larry Page hat kürzlich wiederholt, dass Software alle 18 Monate doppelt so langsam wird und damit Moores Gesetz übertrifft.

Dai
quelle

7

Ja , sie sind in der breiten Industrie "relativ" weniger wichtig. Der Texteditor ist möglicherweise "schnell genug" und erfordert möglicherweise keine großen Verbesserungen. Ein großer Teil des IT-Aufwands besteht darin, sicherzustellen, dass die in Java geschriebene Komponente A mit der in C geschriebenen Komponente B zusammenarbeitet, über die in Cobol (oder etwas anderem) geschriebene Nachrichtenwarteschlange korrekt kommuniziert oder das Produkt auf den Markt bringt.

Außerdem wurde die Architektur kompliziert. Wenn Sie einfache, einfache Prozessoren hatten, in denen Sie 1 Anweisung pro Zyklus hatten und in der Baugruppe schrieben, waren die Optimierungen "einfach" (Sie mussten nur die Anzahl der Anweisungen zählen). Derzeit verfügen Sie nicht über einen einfachen Prozessor, sondern über einen superskalaren Prozessor mit vollständiger Pipeline-Verarbeitung, der eine Umbenennung der Register und einen Cache mit mehreren Ebenen ermöglicht. Und Sie schreiben nicht in Assembly, sondern in C / Java / etc. Wo Code kompiliert / JITed ist (normalerweise, um den Code zu verbessern, den Sie oder ich in Assembly geschrieben haben), oder in Python / Ruby / ..., wo Code interpretiert wird und Sie durch mehrere Abstraktionsebenen von der Maschine getrennt sind. Mikrooptimierungen sind schwierig und die meisten Programmierer würden einen gegenteiligen Effekt erzielen.

Nein , sie sind in der Forschung nach wie vor wichtig und in absoluten Zahlen. Es gibt Bereiche, in denen Geschwindigkeit wichtig ist, da sie mit großen Datenmengen arbeiten. Auf dieser Skala kommt es auf die Komplexität an, wie das Beispiel von Pavel zeigt.

Es gibt jedoch noch weitere Fälle - wenn es auf die Geschwindigkeit ankommt (HPC, eingebettete Geräte usw.), ist es immer noch eine Option, sich von den Algorithmen abzuwenden. Sie finden an vielen Universitäten Gruppen, die sich auf Compiler und / oder Softwareoptimierung spezialisiert haben. Zum Beispiel kann ein einfacher Wechsel der Schleifenreihenfolge eine tausendfache Beschleunigung bringen, nur weil der Cache effizient genutzt wird - während dies ein Grenzbeispiel sein könnte, wächst die CPU-Speicherlücke in den letzten 30 Jahren um das 1000-fache. Auch die Computerarchitektur ist Teil von CS. Daher sind viele der Verbesserungen der Rechengeschwindigkeit tatsächlich Teil des allgemeinen CS-Bereichs.

Auf der industriellen Seite - wenn Sie über einen HPC-Cluster verfügen, spielt die Geschwindigkeit eine Rolle, da ein einzelnes Programm Tage, Monate oder Jahre lang ausgeführt werden kann. Nicht nur Sie müssen die Stromrechnung bezahlen, auch das Warten kann Geld kosten. Sie können doppelt so viel Hardware einwerfen, aber 700 Millionen US-Dollar können kaum als Taschengeld für alle angesehen werden, außer für die größten Unternehmen. In solchen Fällen sind die Programmierer die billigere Option Denke darüber nach.

Auch Geschwindigkeit könnte eine bessere UX bedeuten. In vielen Berichten über das Betriebssystem von Mobiltelefonen wird angegeben, welches "schnippischer" ist, und obwohl dies mit "Tricks" durchgeführt werden kann, handelt es sich mit Sicherheit um einen Studienbereich. Außerdem möchten Sie schneller auf Ihre Daten zugreifen und schnell das tun, was Sie benötigen. Manchmal bedeutet dies, dass Sie mehr tun können - in Spielen haben Sie 0,017 Sekunden Zeit, um alles zu tun, und je schneller Sie sind, desto mehr Süßigkeiten können Sie setzen.

Maciej Piechotka
quelle

2

Es ist eine interessante Diskussion. Und wir müssen uns hier ein paar Dinge ansehen.

Die theoretische Informatik - Dies ist eine sich entwickelnde Wissenschaft, die bedeutet, dass wir im Laufe der Zeit neue und bessere Wege finden werden, um Probleme zu lösen, was zum Beispiel verbesserte Algorithmen für das Suchen und Sortieren bedeutet.
Größere Communitys / größere Bibliotheken - Da bereits viel Arbeit von anderen Leuten geleistet wurde, können wir einfach auf deren Arbeit aufbauen und die Algorithmen verwenden, die sie bereits erstellt und sogar codiert haben. Und diese Bibliotheken werden mit der Zeit aktualisiert, sodass wir automatisch auf effizientere Programme / Algorithmen zugreifen können.
Entwicklung - Jetzt haben wir hier ein Problem, denke ich. Viele Programmierer sind keine Informatiker, also schreiben sie Code, um Geschäftsprobleme zu lösen, keine technischen / theoretischen Probleme, und würden eine Bubble-Sortierung genauso gerne verwenden wie eine schnelle Sortierung. Und hier erlaubt die Geschwindigkeit der Hardware schlechten Programmierern, mit schlechten Algorithmen und schlechten Codierungspraktiken davonzukommen. Arbeitsspeicher, CPU-Geschwindigkeit, Speicherplatz sind keine größeren Probleme mehr, und alle paar Monate werden die Dinge größer, schneller und billiger. Ich meine, schaut euch die neuen Handys an. Sie sind jetzt weiter fortgeschritten als die Großrechner / Server aus den 1970er / 80er Jahren. Mehr Speicher, mehr Rechenleistung, schnellerer Speicher.
Benutzeroberfläche und Daten - Benutzeroberfläche / Benutzererfahrung und Daten werden in den meisten Bereichen der Entwicklung als wichtiger angesehen als hocheffizienter Code. So wird Geschwindigkeit nur dann zum Problem, wenn ein Benutzer lange warten muss. Wenn wir dem Benutzer ein gutes Erscheinungsbild geben und er von der Anwendung eine gute Resonanz erhält, ist er glücklich. Und wenn Unternehmen wissen, dass alle Daten sicher gespeichert sind und sie jederzeit abgerufen und bearbeitet werden können, ist es ihnen egal, wie viel Speicherplatz sie benötigen.

Ich muss also sagen, es ist nicht so, dass effiziente Programmierer nicht mehr wichtig sind oder gebraucht werden, es ist nur so, dass nur sehr wenige Unternehmen / Benutzer Leute dafür belohnen, dass sie supereffiziente Programmierer sind, und weil die Hardware besser ist, kommen wir mit weniger davon effizient. Es gibt aber immerhin noch Leute, die auf Effizienz setzen und aufgrund des Gemeinschaftsgeistes davon alle profitieren, die mit der Zeit davon profitieren.

AquaAlex
quelle

1

Einige andere Blickwinkel auf diese interessante und tiefe Frage, die die interdisziplinären und übergreifenden Aspekte des Phänomens betonen . Dai zitiert Wirths Gesetz in seiner Antwort:

Software wird langsamer als Hardware schneller.

Es gibt interessante Parallelen dieser Idee zu Phänomenen, die in der Wirtschaft beobachtet werden. Beachten Sie, dass die Wirtschaft viele tiefe Verbindungen zur Informatik aufweist, z. B. bei der Planung, bei der knappe Ressourcen (z. B. Threads usw.) auf Anfrage durch "Lastausgleich" -Algorithmen zugewiesen werden. Ein weiteres Beispiel ist die sogenannte Producer-Consumer-Queue. Auch Auktionen.

Auch zB Liste der gleichnamigen Gesetze, Wikipedia :

Parkinson-Gesetz - "Die Arbeit wird erweitert, um die für ihre Fertigstellung zur Verfügung stehende Zeit auszufüllen." Geprägt von C. Northcote Parkinson (1909–1993), der auch dessen Folgerung prägte: "Die Ausgaben steigen, um das Einkommen zu decken." Auf Computern: Programme werden erweitert, um den gesamten verfügbaren Speicher zu füllen.

Es gibt auch eine starke Ähnlichkeit mit Jevons Paradoxon, das bei der Steigerung des Energieverbrauchs beobachtet wurde, nachdem die effizienteren Watt-Dampfmaschinen das Newcomen-Design zu ersetzen begannen, aber die Verwendung oder Verbreitung der Motoren zunahm:

In der Ökonomie ist das Jevons-Paradoxon (/ ˈdˈvʒɛnz /; manchmal Jevons-Effekt) die These, dass der technologische Fortschritt, der die Effizienz der Ressourcennutzung erhöht, dazu neigt, die Verbrauchsrate dieser Ressource zu erhöhen (anstatt zu verringern).

Die Analogie ist, dass Hardware die Ressource ist und Software dem Verbrauch der Ressource entspricht (auch bekannt als Angebot oder Nachfrage). So Software und Hardware (und Fortschritte in der jeweils) sind ein wenig in einer eng gekoppelten symbiotische Rückkopplungsschleife miteinander stehen, in einem gewissen Sinn coevolving . Es gibt viele komplexe und in Wechselbeziehung stehende Faktoren, die dieses Zusammenspiel beeinflussen, zB:

vzn
quelle

Warum die Gegenstimme? Ich finde die Erwähnung des Parkinson-Gesetzes und des Jevons-Paradoxons sehr aufschlussreich.

Yuval Filmus

@YuvalFilmus Meine Vermutung: Probleme mit der Grammatik. Ich fand es diesmal nicht störend, die Antwort zu gut zu lesen, aber ich habe versucht, sie zu verbessern.

Juho

1

Es sind keine "Grammatikprobleme", sondern ein anderer Stil. Es ist, als würde man sagen, dass ein Muttersprachler "Fehler" macht, wenn er seine eigene Sprache spricht, während sich entweder die Sprache ändert oder regionale Unterschiede bestehen. In diesem Fall ist es der idiomatische Stil von vzn.

Yuval Filmus

-3

Nein, hauptsächlich unter Berücksichtigung der Komplexität des Raums! Die Speicherkapazität eines normalen Computers wächst exponentiell.

Andy
quelle

Wäre nicht umgekehrt - wenn Sie über "unendlichen" Speicher verfügen, müssten Sie sich nicht um die Komplexität des Speicherplatzes kümmern. Das 'Problem' ist nicht, dass der Speicherplatz wächst, sondern dass die Daten, die synchron verarbeitet werden müssen, die Geschwindigkeit erhöhen, die durch die Erhöhung der Rechenleistung und des Arbeitsspeichers erreicht wird. Gut, wir möchten den Kosmos realistischer modellieren, mehr Protein falten usw. (PS. Ich habe nicht abgestimmt)

Maciej Piechotka

4

Es ist wahr, dass viele Entwickler von mobilen Apps unendliche Ressourcen annehmen , aber leider ist mein Gerät sehr begrenzt.

Raphael

Werden Algorithmen (und die Effizienz im Allgemeinen) immer weniger wichtig?

Antworten: