Als Neueinsteiger einer Programmiersprache sollte man sich bekannte Probleme suchen, die man schon in früheren Sprachen gelöst hat und diese umsetzen. Bei allen meinen früheren Schwenks zu den diversesten Sprachen war hier das große Wehklagen vorprogrammiert. Nicht so bei Ruby.

Die Freiheit in der Syntax half sehr zu einem schnellen Ergebnis zu kommen und das bewegte mich dazu zu recherchieren, wie denn andere Entwickler mit deren Background an die Sache rangehen. Resultat waren einige interessante Konstrukte deren Performance ganz unterschiedlich ist.

Vorab möchte ich den/die Leser/in bitten, sich nicht auf den Schlips getreten zu fühlen, falls er/sie sich in Syntax oder Semantik der ausgegrabenen Beispiele wiedererkennen sollte. Die Klassifizierung der Beispiele in “Entwicklertypen” ist lediglich humorvoll gemeint. Im Prinzip kann jeder auf jede der Lösungen kommen, bis auf eine vielleicht und ich meine nicht meine.

Das Problem, dass ich am liebsten in neue Sprachen umsetze sind Primzahlen. Die einfachste Möglichkeit hierbei ist es von 2 bis max zu interieren und dabei jede Zahl zu prüfen ob von 2 bis sqrt(max) die Modulooperation 0 ergibt. Das ist jedoch nicht die beste. Der griechische Mathematiker Eratosthenes von Kyrene hatte sich hierbei ein “Sieb” ausgedacht, was im Prinzip ein Array darstellt in dem alle Vielfachen einer Zahl gestrichen werden. Dieser Alorithmus stellt demnach auch die Standardimplementierung im Schulungsbereich dar, da man sie einfach visualisieren kann.

Doch wie stellen sich die Umsetzung nun Entwickler vor? Da hätten wir als erstes mal den

C-Programmierer

Er denkt kompakt und liebt kurze Variablennamen. Sein einziger Gedanke gilt der optimalen Speicherauslastung bei maximaler Effizienz. So könnte seine Lösung aussehen:

1
2
3
4
5
6
7
8

def prim_cway(max)
  i=l=1
  while ((l*=i) && (i<max))
    if ((l%i+=1)>i-2) then
      printf("%d ",i);
    end 
  end
end

Natürlich hätte man sich hier auch an das Sieb halten können, aber die Primzahlen sollen ja möglichst schnell berechnet werden und ausserdem liegt Tosthi hier völlig falsch, da er ja noch nicht auf embedded Prozessoren hacken musste und Doppelschleifen sowieso saugen.

Aber wie funktioniert der Code nun in nur einer Schleife? l wird pro Durchlauf immer um i vervielfacht. In der if-Anweisung erfolgt die Erhöung von i um 1 allerdings noch bevor das Modulo ausgeführt wird, weil Zuweisungen in Operationen vorgezogen werden. Das Ergebnis ist also nicht größer als i-1. Handelt es sich bei i um eine Primzahl, so wird l % (i+1) = 0 werden und ist somit kleiner als i-2. Im Prinzip könnte man auch hier auf 0 vergleichen, jedoch würden dann die 1 und 2 mit ausgegeben, die eine Ausnahme bilden. Diese Lösung implementiert übrigens die sogenannte Lineare Rekursion basierend auf dem kleinen Satz des Fermat. Aber lasst uns die Franzosen bei Seite schieben und wieder zurück zu unserem Griechen kommen.

Der Java-Programmierer wird sich hier eher am Sieb orientieren und vorhandene Klassen und Methoden genauer betrachten und auch einsetzen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def prim_erat1(limit)
  return [] if limit < 2
 
  length = ((limit/2) - 1 + limit%2)
 
  sieve = [true] * (length+1)
 
  0.upto((Math.sqrt(limit).to_i >> 1) - 1) do |i|
    next if not sieve[i]
 
    (((i*(i+3) << 1) + 3)...length).step((i << 1) + 3) do |j|
      sieve[j] = false
    end
  end
 
  primes = [2]
 
  0.upto(length-1) do |i|
    primes << (i << 1)+3 if sieve[i]
  end
 
  primes
end

Die Vorgehensweise hier ist erst einmal ein Array mit “max” Keys mit true-Werten zu füllen. In der Schleife werden mit einer weiteren inneren Schleife durch die Benutzung von step die Vielfachen ausradiert und anschliessend befüllt man das Ergebnisarray mit den Zahlen für denen die true-Werte im Siebarray übrig geblieben sind. Diese Version ist wesentlich umfangreicher als die des C-Programmierers, jedoch versteht man die Logik eher.

Wobei wir auch schon beim PHP-Programmierer ankommen

Er denkt ähnlich wie der Java-Programmierer, wobei er es nicht so mit komplexen Iteratoren hat. Da man ihn jedoch bei Ruby seiner geliebten C-ähnlichen for-Schleife beraubt hat, muss er sich wohl oder übel mit step auseinandersetzen, was er jedoch schnell intus hat.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def prim_erat2(max)
  sieve = []
 
  for i in 2 .. max
    sieve[i] = i
  end
 
  for i in 2 .. Math.sqrt(max)
    next unless sieve[i]       
 
    (i*i).step(max, i) do |j|
      sieve[j] = nil
    end
  end
  sieve.compact
end

Auch diese Lösung implementiert das Sieb wie es ursprünglich gedacht war. Nur wird hier direkt auf dem Array operiert, das alle Zahlen bis max enthält. Gestrichene Werte werden durch nil ausradiert und das Array wird anschliessend wieder komprimiert.

Objective-C

Der Homo Sapiens Cocoaensis, auch Objective C Mensch genannt, ist es gewöhnt C mit funktionalen Elementen zu mischen und dabei mehr drauf zu achten, dass man große Teile des Algorithmus möglichst singen kann. Die Performance wird erst nachträglich über Tools wie XCode Instruments angepasst.

1
2
3
4
5
6
7

def prim_asearch(max) 
  a=Array.new
  for i in 2..max do
    a << i unless (2..i-1).find {|j| i % j == 0}
  end
  a
end

Ganz brutal werden hier mittles der find Methode für jede Zahl i zwischen 2 und max die Werte über ein anonymes Array mit dem Blockiterator j gefunden, für die i modulo j gleich 0 zutrifft. Es funktioniert, jedoch ist die Performanz suboptimal.

Smalltalk

Der Smalltalk Typus liebt es untypisiert und objektorientiert und packt das ganze am liebsten in eine Zeile. Er steht in der Evolutionsstufe noch über dem Objective-C Menschen. Dabei ist es ihm sogar egal, ob er selbst den Code noch lesen kann und singen wird er ihn gleich zweimal nicht. Es stellt eher eine Art Gebet dar.

1
2
3

def prim_inject(max) 
  (2..max).inject((2..max).to_a) {|res, i| res.select{|n|n==i||n%i!=0} }
end

Hier muss man zweimal hinschauen um zu verstehen was passiert. Das inject erhält als Initialwert ein Array mit der gleichen Range. Im Block ist nun jeder Memowert gleich dem Array. Aus diesem werden alle Werte selektiert für die der Ausdruck im Bock false ergibt. Hier verwirren die vielen Pipes etwas. Das |n| ist schlicht der Blockiterator und die zwei Pipes in der Mitte stellen eine oder-Verküpfung dar. Das select liefert einen Wert zurück, wenn der Ausdruck true ergibt. Dies trifft zu, wenn der Iterator i gleich dem Iterator n oder n modulo i ungleich 0 ist also für die Fälle dass die “innere” Schleife durchlaufen ist oder der innere Schleifenwert modulo äusserer Schleifenwert über einen Teilerrest verfügen.

Sehr ineffizent in diesem Beispiel ist die Tatsache, dass hier der Initalwert des injects als Schleife missbraucht wird und dieser dann auch im memo-Teil des Blocks landet. Wie bei allen Lösungen mit Doppelschleifen steigert sich die Laufzeit proportional zu der Range. Bei dieser Funktion ist es jedoch noch schlimmer, da hier ganze Arrays als Parameter übergeben werden was auch sehr schnell zu einem Stackproblem führen wird.

Dass es noch kryptischer und lastreicher gehen kann soll uns das letzte Exempel zeigen.

Der Perl-Programmierer

Er ist der Meister der Skripte wenn es um das schnelle Verarbeiten von Listen, Texten geht, ganz gleich welchem Format sie auch ganz oder teilweise unterliegen mögen. Er kann das weil er das mächtigste Werkzeug aller sein Eigen nennt: den regulären Ausdruck. Diese Genies der Musterkennung bestehen den Turingtest mit Leichtigkeit und es gibt nichts was man damit nicht lösen kann. Nicht einmal das Finden von Primzahlen. Das glauben Sie nicht? Dann sehen und staunen Sie:

1
2
3
4
5
6
7

def prim_regex(max)
  a=Array.new
  2.upto(max) do |n| 
    a << n if (("1" * n) !~ /^1?$|^(11+?)\1+$/)
  end
  a  
end

Obiges ist zugegebenermassen die nerdigste Umsetzung des Siebs und auch die langsamste. Die Regular Expression macht sich hier die Möglichkeit des Backreferencing zu eigen. Erst wird ein String mit einer Anzahl von Einsen erzeugt, die dem momentanen Interatorwert n entspricht. Die RegEx matcht links wenn der String leer ist oder eine 1 enthält. In diesem Fall handelt es sich nicht um eine Primzahl (weil !~ den Match negiert). Jetzt kommt der zweite Teil. Der Teil in den Klammern prüft erst ob “11″+? matcht. Das ist der Fall und es wird “11″ in die Backrefvariable \1 geschrieben. Dort wird jetzt geschaut ob “11″+, also ein oder mehrere Vorkommnisse den String matchen. Ist das nicht der Fall. Dann wird nochmal der gesamte Rechte Teil geprüft, wobei jetzt der Klammernteil mit “111″+? matchen muss (was er immer tut, weil ganz oder gar nicht gegeben ist) und der hintere Teil mit “111″+. Dadurch erreicht man die Prüfung auf Vielfache und somit die Umsetzung des Siebs, wenn auch auf Kosten von sehr langen Ausführungszeiten.

Benchmarks

Führt man nun einen Bechmarktest aus und vergleicht die Laufzeiten, so kommt man sehr schnell zu einem Schluss. Alle Varianten, die zwei verschachtelte Schleifen benötigen sind der korrekten Umsetzung des Siebs, also der wirklichen Bereinigung eines Arrays weit unterlegen. Am stärksten schlägt hier die Injectionmethode zu buche. Sie wird nur noch von der RegEx-Variante getoppt, wobei man die nicht wirklich ernsthaft ins Rennen schicken darf, da die Ausführgeschwindigkeit stark von der Implementierungsart ihres Algorithmuses abhängt. Die “C-Variante” ist nur deshalb so schnell, weil sie nicht das Sieb implementiert wird aber wegen des exponentiellen Anstiegs des Dividenden schnell zum Überlauf führen. asrc und inj haben zusätzlich zu den vielen Arrayoperationen das Problem eines teueren Modulos auf das er1 und er2 gewinnbringend verzichten konnten.

1
2
3
4
5
6
7

           user     system      total        real
reg    3.070000   0.260000   3.330000 (  3.354881)
er1    0.000000   0.000000   0.000000 (  0.002403)
er2    0.000000   0.000000   0.000000 (  0.004381)
c      0.240000   0.000000   0.240000 (  0.244020)
asrc   0.910000   0.000000   0.910000 (  0.929468)
inj    2.320000   0.020000   2.340000 (  2.362957)

Meine Lösung

Wenn der/die Leser/in jetzt ein Glanzstück an Effizienz und Geschwindigkeit erwartet, so muss ich ihn/sie leider enttäuschen. Über das schon zu oft benannte weil synonymlose Sieb des Eratosthenes habe ich mir einfach zu oft den Kopf zerbrochen. Daher wird genommen was man geboten bekommt.

1
2
3
4
5
6
7
8
9

require 'mathn'
 
def prime_mine(max) 
  pa=Array.new
  pn=0;
  p=Prime.new
  pa << pn while ((pn=p.next()) < max)
  pa
end

Was den Benchmark angeht, der liegt irgendwo zwischen c und asrc. Der Alorithmus, der hier benutzt wird ist mir leider nicht bekannt. Wer jetzt Lust verspürt es herauszufinden und gegebenenfalls sogar zu optimieren, der möge bitte walten und darf auch gerne einen Kommentar hierzu hinterlassen.

Fazit

Welche Lösung gewinnt jetzt eigentlich? Natürlich jede, denn jede ist funktionierender Ruby Code. ) Scherz beiseite, hier geht es natürlich nicht um Gewinner und Verlierer. Es soll lediglich klar gemacht werden, dass die Lernkurve bei Ruby dank der Flexibilität in der Syntax sehr niedrig gehalten ist. Auch wird verdeutlicht, dass man mit Ruby sehr effizienten und schnellen Code liefern kann und das bei guter Lesbarkeit.

Schlagworte: Lernen, Ruby, Tutorial

Autor: Bernhard Fuchs, http://www.valiton.com Bernhard Fuchs arbeitet als Senior Software Developer bei der Valiton GmbH und ist ein relativer Newby on Rails. Daher macht es ihm Spass die Dinge aus Anfängersicht zu sehen und diesbezüglich auch etwas ausführlicher zu sein in den Erklärungen. Die 25-jährige Programmiererfahrung in fast allem was so an Sprache existiert hilft ihm da ungemein.

Both comments and pings are currently closed.

Artikel bewerten:

(5 Bewertung(en), durchschnittlich: 4.80 (max. 5)

 Loading ...

Ein Kommentar zu “Prim(a) Lösungen in Ruby”

1. Peter Schrammel schreibt:
   4. März 2009 um 08:52

   Köstlich!