"hallo".reverse langsamer als tail recursion ?

D

dmike

Bekanntes Mitglied
Ich hab mal geschaut wieviel Zeit es braucht um einen String umzudrehen.

Dazu gibt es 3 Zeiten T0,T1 und T2 für den String "Madam, I'm Adam"

T0: String wird per Schleife umgedreht
T1: String wird per tail recursion umgedreht
T2: String wird mit API Methode revers umgedreht

Ergebnis in ns für je 3 Durchläufe

Code: 
T0: looping reverse
T1: tail recursive reverse
T2: build-in reverse
T0=54853733 T1=4626313 T2=9046413
T0/T2=6.0636 T1/T2=0.5114
reverseMe=Madam, I'm Adam: res0=<madA m'I ,madaM> res1=<madA m'I ,madaM> res2=<madA m'I ,madaM>

Zum Vergleich:

Schleife etwa 6 x langsamer als API Methode
Tail recursion etwa doppelt so schnell wie API Methode

Hätte das jetzt nicht gedacht!


Hier der code:


Java: 
var tic = System.nanoTime
var toc0 = System.nanoTime
var toc1 = toc0
var toc2 = toc0
var reverseMe = "Madam, I'm Adam"

var res0 = ""
var res1 = res0
var res2 = res0

// looping
def reverse0(str : String) = {
  var res = ""
  for ( i <- str.length -1 to 0 by -1 ) {
    res += str.charAt(i)
  }
  res
}

// tail recursive
def reverse1(str: String) = {
  def rev(src:String, i:Int, dest:String): String = {

   if (-1==i)
     dest
   else {
     rev(src,i-1,dest+src.charAt(i))
   }
  }
  rev(str,str.length-1,"")
}

// build-in
def reverse2(str: String) = {
    //val x = str.toList                                      

    //val v = for {i <- x.length-1 to 0 by -1} yield x(i)
    //val v = x.reverse

    //v.toList.foldLeft("")(_+_)                         
    str.reverse
}

println("T0: looping reverse")
tic = System.nanoTime
res0=reverse0(reverse0(reverse0(reverseMe)))
toc0 = System.nanoTime - tic

println("T1: tail recursive reverse")
tic = System.nanoTime
res1=reverse1(reverse1(reverse1(reverseMe)))
toc1 = System.nanoTime - tic

println("T2: build-in reverse")
tic = System.nanoTime
res2=reverse2(reverse2(reverse2(reverseMe)))
toc2 = System.nanoTime - tic

printf("T0=%d T1=%d T2=%d\nT0/T2=%.4f T1/T2=%.4f\n",toc0,toc1,toc2,1.0*toc0/toc2,1.0*toc1/toc2)


printf("reverseMe=%s: res0=<%s> res1=<%s> res2=<%s>\n", reverseMe, res0, res1, res2)
 
Zuletzt bearbeitet:
Landei

Landei

Top Contributor
Um "fair" zu sein, solltest du in reverse0 einen StringBuilder verwenden.

Und wie würde sich die Implementierung (new StringBuilder(s)).reverse.toString schlagen?
 
D

dmike

Bekanntes Mitglied
Landei hat gesagt.:
Um "fair" zu sein, solltest du in reverse0 einen StringBuilder verwenden.

Und wie würde sich die Implementierung (new StringBuilder(s)).reverse.toString schlagen?
Zum Vergrößern anklicken....

Ah guter Punkt Ich dachte dass der Compiler das optimiert.

Mit Stringbuilder

Code: 
T0: looping reverse
T1: tail recursive reverse
T2: build-in reverse
T0=59993531 T1=700588 T2=36747
T0/T2=1632.6103 T1/T2=19.0652
reverseMe=Madam, I'm Adam: res0=<madA m'I ,madaM> res1=<madA m'I ,madaM> res2=<madA m'I ,madaM>

Ok, die Zahlen sprechen ja jetzt für sich :)

Ich hatte teil recursion zunächst auch mit einem StringBuilder laufen lassen, aber weil es keinen Unterschied in der Laufzeit gab, bin ich davon ausgegangen dass der Compiler intern optimiert, bzw. selbst den StringBuilder benutzt. Warum das jetzt bei str.reverse nicht mehr ist, ist mekrwürdig!



Ich werde die anderen 2 Methoden auch umändern



So alle laufen jetzt mit StringBuilder...

Code: 
T0: looping reverse
T1: tail recursive reverse
T2: build-in reverse
T0=45893166 T1=44108 T2=26737
T0/T2=1716.4665 T1/T2=1.6497
reverseMe=Madam, I'm Adam: res0=<madA m'I ,madaM> res1=<madA m'I ,madaM> res2=<madA m'I ,madaM>

Also tail recursion ist auf jeden fall der loop Methode vorzuziehen. Ob das immer gilt ist eine andere Frage.
 
Zuletzt bearbeitet:
D

dmike

Bekanntes Mitglied
Statt for nun mit do - while für T0. Aber immer noch ein Gewalter Unterschied.


T0: looping reverse
T1: tail recursive reverse
T2: build-in reverse
T0=21493818 T1=36329 T2=27734


T0/T2=774.9988 T1/T2=1.3099
 
D

dmike

Bekanntes Mitglied
T0: looping reverse
T1: tail recursive reverse
T2: build-in reverse
Iteration#=100000000 T0=56582002772 T1=84630437153 T2=31802127477

T0/T2=1.7792 T1/T2=2.6612


so ich ruder mal wieder zurück nach

100 * 10 ^ 6 Iterationen ist die Welt wieder in. Ordn. tail recursion ist 2.5 x langsamer als der API call
 

Aktuelle Jobs

Neue Themen


Oben