DeepMinds AlphaDev entdeckt schnelleren Sortieralgorithmus

• Da Verbesserungen auf C/C++-Ebene als schwierig eingeschätzt wurden, wurde versucht, Optimierungen auf Assembly-Ebene zu finden
• Wie in einem Spiel wurden fortlaufend Algorithmen gesucht, die zur vorgegebenen Lösung das passende Ergebnis liefern
• Gegenüber der LLVM-libc++-Sorting-Library zeigt sich bei kleinen Mengen eine um 70 % höhere Leistung, bei Sequenzen mit mehr als 250.000 Elementen eine um 1,7 % höhere Leistung
• Da die meisten Sortiervorgänge bei kurzen Sequenzen stattfinden, lag der Fokus besonders auf diesem Bereich
• Es ist nicht nur einfach schneller, sondern zeigt einen einfallsreichen Ansatz, der mit AlphaGos Zug 37 verglichen wird
• Auch der Hashing-Algorithmus wird derzeit verbessert

[kuroneko]

Es ist wirklich erstaunlich, dass man mit KI sogar bessere Algorithmen finden kann.

[dbs0829]

Sogar bei den in Deep Learning verwendeten Optimierern wird in letzter Zeit ziemlich häufig versucht, sie auf diese Weise zu finden. Die Leistung ist auch gut.

[spark]

Es geht nicht darum, dass sie sich „stärker darauf konzentriert haben, weil die meisten Sortiervorgänge in kurzen Sequenzen stattfinden“, sondern sie haben das Modell einfach darauf trainiert, einen Assembly-Algorithmus zum Sortieren einer fest vorgegebenen Anzahl von Zahlen zu finden – 3, 4, ... 8 Stück.

[disjukr]

Wenn man den Originaltext liest, scheint es so, dass die Forschenden hinter AlphaDev es mit genau dieser Absicht trainiert haben.

We focused on improving sorting algorithms for shorter sequences of three to five elements. These algorithms are among the most widely used because they are often called many times as a part of larger sorting functions. Improving these algorithms can lead to an overall speedup for sorting any number of items.