Zurück zu Bigger Picture

BIGGER PICTURE Wissenschaft & Entdeckung

Ein Befehl weniger, immer wieder beim Sortieren

Drei Zahlen zu ordnen klingt längst gelöst. AlphaDev fand neue Befehlsfolgen für winzige Sortierroutinen. Entwickler überführten die Entdeckungen in eine weit verbreitete Softwarebibliothek.

KI-generierte Illustration: Ein kürzerer Rechenweg ordnet eine Folge von Blöcken.
Ein kürzerer Rechenweg ordnet eine Folge von Blöcken. Konzeptionelle Illustration; kein Foto und keine exakte Darstellung des realen Projekts.KI-generierte Illustration der Idee, keine Aufnahme der tatsächlichen Personen, Geräte oder Ereignisse.
Entdeckung
Neue maschinennahe Sortierroutinen
Gemessene Spanne
Bis zu 70 % schneller bei kurzen Folgen
Praktische Anwendung
In LLVM libc++ integriert

So funktioniert die Idee

  1. Sortierroutine zusammensetzen

    Der Agent fügt maschinennahe Prozessorbefehle hinzu.

  2. Korrekte, schnelle Ausführung belohnen

    Tests vergleichen Reihenfolge und Laufzeit.

  3. Entdeckung übertragen und prüfen

    Entwickler integrieren geeignete Routinen in libc++.

Unterhalb der Programmiersprache suchen

AlphaDev suchte in Prozessorbefehlen, statt den übergeordneten Programmcode eines Menschen zu bearbeiten. Schritt für Schritt sollte eine korrekte Sortierroutine entstehen. Unter den veröffentlichten Beispielen befindet sich ein Sortierer für drei Elemente mit 17 Befehlen. Solche kleinen Routinen zählen, weil größere Sortierverfahren kleine Bausteine wiederholt aufrufen.

Belege: [3]

Ein Spiel mit strenger Korrektheitsregel

Bestärkendes Lernen belohnte Programme, die schnell die richtige Reihenfolge lieferten. Eine Abkürzung, die Werte verlor oder falsch anordnete, war unbrauchbar. Das System fand Anordnungen, bei denen ein Befehl entfallen konnte und das Ergebnis korrekt blieb. Das ist ein reizvoller Suchraum: Eine überraschende Lösung lässt sich ausführen und prüfen.

Belege: [1][3]

Der Änderungsvorschlag musste menschliche Prüfung bestehen

Der LLVM-Verlauf zeigt die praktische Arbeit: Prüfer hinterfragten Datentypen, Compilerverhalten, Tests und Fälle, in denen das neue Verfahren langsamer sein könnte. Die angenommenen Routinen wurden Teil von libc++. Diese öffentliche Prüfung ist für den Nutzen ebenso wichtig wie die Entdeckung. Ein Algorithmus hilft erst nach zuverlässiger Integration in echte Software.

Belege: [2]

Kleine Grundlagen können weit wirken

Die Forschenden berichteten in ihren Benchmarks bis zu 70 % schnelleres Sortieren kurzer Folgen und ungefähr 1,7 % bei mehr als 250.000 Elementen. Das bedeutet nicht, dass ganze Anwendungen entsprechend schneller laufen. Die übertragbare Idee: eine gemeinsam genutzte, häufig wiederholte Operation verbessern und den geprüften Fortschritt über eine bestehende Bibliothek verbreiten.

Belege: [1][2]

Die Originalquellen

  1. Google DeepMindAlphaDev discovers faster sorting algorithms
  2. LLVM code reviewD118029: Introduce branchless sorting functions for sort3, sort4 and sort5
  3. Google DeepMindAlphaDev repository: algorithms and correctness tests

Was Sie als Nächstes entdecken können

KI erfindet einen kürzeren Weg zum MultiplizierenEine kleine Routenänderung kann weniger Wolken hinterlassen
Alle 99 Anwendungen entdecken