© Romolo Tavani, 123RF

Aus einem Algorithmus kann schnell ein Benchmark werden. Im vorliegenden Fall dient ein Rezept zum Sortieren zwei Programmiermodellen als Messlatte: Objektorientiert versus funktional.

Pünktlich zu Weihnachten 2020 erschien die lang erwartete Ruby-Version 3.0. Sie soll drei Mal so schnell sein wie die vorherige 2er-Version – der perfekte Zeitpunkt, um sie in einen Vergleich mit Elixir zu schicken.

Der Algorithmus

Über den bekannten Sortierklassiker Bubblesort scherzte schon Barak Obama im Gespräch mit Google-Boss Eric Schmidt [1]. Außer für Bewerbungsgespräche kommt er in der IT-Praxis aber kaum vor, weil andere Algorithmen ein besseres Laufzeitverhalten bieten. Nur in der Lehre hat er weiterhin eine feste Position, um Sortierverfahren und Optimierungen zu erklären.

Der Sortierprozess erfolgt bei Bubblesort in mehreren Durchgängen. Wir starten mit dem unsortierten Array [23,**3,**73,**19] und vergleichen in jedem Durchgang zwei nebeneinander liegende Elemente. Ist das erste Element größer als das zweite, tauschen wir beide gegeneinander aus. 23 ist größer als 3, also werden beide Elemente getauscht. Dann wird 23 mit 73 verglichen; beide Elemente bleiben in der bestehenden Reihenfolge, da 23 kleiner als 73 ist. Im nächsten Durchgang ist 73 größer als 19, sodass der Algorithmus diese beiden Elemente wieder vertauscht.

Nach dem ersten Durchgang liegen die Elemente im Array in der Reihenfolge [3,**23,**19,**73] vor. Solange in einem Optimierungsdurchgang mindestens ein Austausch anfällt, ist die Sortierung noch nicht abgeschlossen. Der Algorithmus geht dann das neue Array noch einmal durch. Abbildung 1 zeigt den Ablauf der kompletten Sortierung. Beim vierten Durchgang kommt es zu keiner Vertauschung mehr, die Sortierung ist abgeschlossen.

Abbildung 1: Der schematische Ablauf einer Bubblesort-Sortierung.

Ruby

Bei Ruby handelt es sich um eine objektorientierte Programmiersprache. Deshalb definieren wir eine neue Methode »bubble_sort(array)«, die die Sortierung realisieren soll (Listing 1). Mit dieser Schleife lassen wir die Sortierung so lange laufen, bis kein Austausch mehr erfolgt. Am Anfang der Schleife wird die Variable »swapped« auf »false« gesetzt und bei jedem Austausch auf »true«.

def bubble_sort(array)
  begin
    swapped = false
    array[0..-2].each_with_index do |element, i|
      if element > array[i + 1]
        array[i], array[i + 1] = array[i + 1], element
        swapped = true
      end
    end
  end while swapped
  array
end

Der Ausdruck »array[0..-2]« gibt das zu sortierende Array ohne das letzte Element aus und verschluckt sich dabei nicht an einem leeren Array. Da wir immer zwei Elemente zum Vergleich benötigen, brauchen wir das letzte Element nicht – ein Array mit nur einem Element ergibt ein leeres Array. Der Ausdruck »each_with_index do |element, i|« iteriert Element für Element durch das Array und setzt die Variable »i« auf die aktuelle Index-Position. Bei einem leeren Array wird die komplette Schleife übersprungen. Der Ausdruck nach »if« prüft, ob das nächste Element kleiner ist als das aktuelle; falls ja, werden beide Element im Array vertauscht.

Das Listing macht einen großen Vorteil von Ruby sichtbar: Der Code lässt sich leicht lesen und relativ schnell schreiben.

Elixir

In der funktionalen Programmiersprache Elixir gehen wir das Problem rekursiv an. Dabei kommt eine Liste von Elementen zum Einsatz, kein Array wie in Ruby (Listing 2).

defmodule Sort do
  def bubble_sort(list) when is_list(list) do
    sorted_list = bubble_sort_sub(list)
    case sorted_list == list do
      true -> sorted_list
      _ -> bubble_sort(sorted_list)
    end
  end
  defp bubble_sort_sub([x, y | tail]) do
    case x > y do
      true -> [y | bubble_sort_sub([x | tail])]
      _ -> [x | bubble_sort_sub([y | tail])]
    end
  end
  defp bubble_sort_sub(list) do
    list
  end
end

Die Funktion »Sort.bubble_sort/1« landet einen Treffer, sobald man sie mit einer Liste als einzigem Parameter aufruft, was der Guard »when is_list(list)« sicherstellt (siehe Kasten “Besonderheiten in Elixir”).

$ iex
Erlang/OTP 22 [erts-10.6.1] [source] [64-bit] [smp:4:4] [ds:4:4:10]  [async-threads:1] [hipe]
Interactive Elixir (1.11.2) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> [head | tail] = [1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
iex(2)> [head2 | tail2] = tail
[2, 3, 4, 5]
iex(3)> [head | head2]
[1 | 2]
iex(4)> [55 | tail]
[55, 2, 3, 4, 5]

Als Erstes übergibt man die Liste der privaten Funktion »bubble_sort_sub(list)« und ordnet das Ergebnis der Variablen »sorted_list« zu. Enthalten »list« und »sorted_list« alle Elemente in derselben Reihenfolge, dann gibt die Funktion »sorted_list« als Ergebnis aus.

Die private Funktion »bubble_sort_sub([x, y | tail])« matcht, wenn man sie mit einer Liste von mindestens zwei Elementen aufruft. Diese Liste wird dann in »x«, »y« und den Rest »tail« (auch wieder eine Liste) aufgesplittet. Beim Aufruf mit einer Liste von nur zwei Elementen ist »tail« eine leere Liste »[]«.

Der Ausdruck »case x > y do« prüft, ob das Element »x« größer ist als »y«. Falls ja, wird »[y | bubble_sort_sub([x | tail])]« aufgerufen, andernfalls »[x | bubble_sort_sub([y | tail])]«. Dabei kommt das Konstrukt »[head | tail]« umgekehrt zum Einsatz, um eine neue Liste zu erzeugen.

Besteht die Liste nur noch aus einem Element, greift die letzte private Funktion »bubble_sort_sub(list)« und gibt diese Liste aus.

Hat man noch nie mit einer funktionalen Programmiersprache gearbeitet, dann erscheint das Elixir-Programm auf den ersten Blick reichlich konfus. Der Sprung zwischen Ruby und Elixir ist wahrlich nicht einfach. Man darf sich nicht von der oft ähnlichen Syntax blenden lassen: Objektorientiert und funktional sind völlig verschiedene Welten. Der schnelle Wechsel zwischen den Programmiersprachen fällt selbst Profis nicht leicht.

Bemerkenswerterweise fällt es Programmieranfängern viel leichter, als Erstes eine funktionale Programmiersprache zu lernen, als alten Hasen, die vorher objektorientiert und davor vielleicht noch prozedural programmiert haben.

### Ruby:
irb> bubble_sort(["x","a","c","d"])
=> ["a", "c", "d", "x"]
### Elixir:
iex(1)> Sort.bubble_sort(["x","a","c","d"])
["a", "c", "d", "x"]

Geschwindigkeit

Nun stellt sich noch die Frage, ob die Geschwindigkeit von Ruby 3.0 an die von Elixir heranreicht. Beim ersten Testdurchlauf mit einem langen zu sortierenden Array beziehungsweise einer Liste war ich zunächst überrascht: Die Werte schienen ungefähr gleich zu sein. Schnell fiel mir dann aber auf, dass zwar die Zahlen vor dem Komma identisch waren, aber nicht die anschließende Zehnerpotenz, mit der es zu multiplizieren gilt. Bei meinem Vergleichstest war Elixir 1.11.2 in jeder Konstellation immer noch zehn Mal schneller als Ruby 3.0.

Auf der RubyConf 2015 in San Antonio gab Ruby-Erfinder Yukihiro Matsumoto das Ziel “Ruby 3×3” aus: Ruby 3 sollte 3 Mal schneller sein als Ruby 2. Fünf Jahre später war es dann soweit: Das Release 3.0 wurde zu Weihnachten 2020 veröffentlicht [2]. Der Optcarrot-Benchmark zeigt tatsächlich eine Beschleunigung um den Faktor 3, bei anderen Benchmarks fällt das Ergebnis nicht ganz so drastisch aus.

Im Großen und Ganzen ist dem Ruby-Core-Team mit dieser Version dennoch ein großer Wurf gelungen, vor allem, weil man die Ruby-Version in den meisten Projekten ohne Veränderung am Code von 2.7 auf 3.0 aktualisieren kann. In früheren Jahren löste ein derartiges Upgrade oft kleinere Katastrophen aus, etwa bei der Aktualisierung von Ruby 1.8 auf 1.9. Auch der MJIT (Method Based Just-in-Time Compiler) ist zwar immer noch nicht perfekt, aber erwachsener geworden. Gerade bei Ruby-on-Rails-Projekten sollte man dessen Einsatz ins Auge fassen. (jcb/jlu)