[Python-de] [Python vs. C] 3n+1-Problem

[Karl Pflästerer]

On 10 Feb 2004, Jens Kubieziel <- python at kubieziel.de wrote:

> Hierbei wird das 3n+1-Problem (teile eine Zahl solange durch zwei, wenn
> sie gerade ist oder, falls nicht, multipliziere mit drei und addiere
> eins, bis man eins erreicht.) vorausgesetzt. Wenn z.B. 3 eingegeben
> wird, entsteht die Folge: 3 10 5 16 8 4 2 1. Aufgabe ist nun, in einem
> einzugebenden Intervall die Anzahl aller Folgenglieder (im obigen Bsp.
> 8) zu errechnen und auszugeben.

> Dies habe ich zunächst mit folgendem Brute-Force-Ansatz probiert:

[...]
> for number in range(i,j+1):

Besser xrange hier.

>   rounds = 1

>   while number>1:
>     if number % 2 == 0:
>       number = number/2
>       rounds = rounds+1
>     else:
>       number = 3*number+1
>       rounds = rounds+1
>   total_rounds.append(rounds)

Wieso füllst du eine Liste?

>   total_rounds.sort()

Und sortierst sie noch? Noch dazu in jedem Schleifenschritt! Also
1000000 mal.

> print total_rounds[len(total_rounds)-1]

Hier suchst du auf die wohl maximal ineffizienteste Art das letzte
Listenelement.

[...]
> meinem Rechner (AMD Athlon 1 GHz) etwas über 20 Stunden. Das Äquivalent

Kein Wunder.

> in C hingegen:

Das ist kein äquivalentes Programm.

[...]
>       if (cnt > max) {
> 	 max = cnt;
> 	 imax = i;

Hier speicherst du einfach die Anzahl der Runden und den zugehörigen
Startwert in 2 Variablen. Keine Liste, kein Sortieren ...

[...]
> benötigt für selbigen Durchlauf nur 2-3 Sekunden.

Auch dies ist kein Wunder.

> Bis auf die fehlenden Eingaberoutinen im C-Programm sind beide Programme
> IMHO äquivalent (Meine ich zumindest). Wo könnte hier das Problem

Das Python Programm ist nahezu maximal ineffizient und das C Programm
versucht sogar das letzte Quentchen über register Deklarationen
herauszuquetschen: das nennst du äquivalent?

> liegen, dass die Python-Variante derart langsamer ist?

Woran wohl?


   Karl
-- 
Roses are red,
  Violets are blue,
I'm schizophrenic...
  And I am too.