Wie schnell werden Algorithmen besser?

Das Problem vor dem die Wissenschaftler standen: Die vorhandenen Daten zu dieser Frage waren grösstenteils anekdotisch und bestanden aus Fallstudien zu bestimmten Algorithmen, von denen man annahm, dass sie repräsentativ für den breiteren Bereich waren. Angesichts des Mangels an Beweisen machte sich das Team daran, Daten aus 57 Lehrbüchern und mehr als 1.110 Forschungsarbeiten auszuwerten, um die Geschichte der Verbesserung von Algorithmen zu verfolgen. Einige der Forschungsarbeiten berichteten direkt darüber, wie gut neue Algorithmen waren, andere mussten von den Autoren anhand von "Pseudocode", Kurzversionen des Algorithmus, die die grundlegenden Details beschreiben, rekonstruiert werden.

Insgesamt untersuchte das Team 113 Algorithmenfamilien, das heisst Gruppen von Algorithmen, die dasselbe Problem lösen, das in Informatiklehrbüchern als besonders wichtig hervorgehoben wurde. Für jeden der 113 Algorithmen rekonstruierte das Team die Geschichte, indem es jedes Mal verfolgte, wenn ein neuer Algorithmus für das Problem vorgeschlagen wurde, und dabei besonders auf die effizienteren Algorithmen einging. Das Team fand durchschnittlich acht Algorithmen pro Familie, von denen einige die Effizienz verbesserten, und zwar in verschiedenen Leistungsbereichen und nach Jahrzehnten, von den 1940er Jahren bis heute. Um dieses gesammelte Wissen mit anderen zu teilen, hat das Team das Algorithm-Wiki.org eingerichtet.

Bei grossen Rechenproblemen gab es bei 43 Prozent der Algorithmenfamilien im Vergleich zum Vorjahr Verbesserungen, die gleich gross oder grösser waren als die viel gepriesenen Zuwächse durch das Mooresche Gesetz. Bei 14 Prozent der Probleme übertraf die Leistungsverbesserung durch Algorithmen bei weitem die durch verbesserte Hardware erzielten Verbesserungen. Die Gewinne durch Algorithmusverbesserungen waren bei Big-Data-Problemen besonders gross, so dass die Bedeutung dieser Fortschritte in den letzten Jahrzehnten zugenommen hat.

In diesem Artikel der MIT News berichten die Wissenschaftler über weitere Details ihrer Ergebnisse.