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

[Jens Kubieziel]

Hallo,

ich habe mir kürzlich diverse Programmieraufgaben der Universidad da
Valladolid (http://acm.uva.es) angeschaut und u.a auch
http://acm.uva.es/p/v1/100.html.

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:

#v+
i = int(raw_input("Please enter the lower boundary: "))
j = int(raw_input("Please enter the upper boundary: "))

total_rounds = []

print i,j,
for number in range(i,j+1):
  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)
  total_rounds.sort()
print total_rounds[len(total_rounds)-1]
#v-

Wenn hier nun spasseshalber alle Zahlen von 1 bis zur in der Aufgabe
gegebenen Obergrenze von 1.000.000 berechnen lasse, dauert das auf
meinem Rechner (AMD Athlon 1 GHz) etwas über 20 Stunden. Das Äquivalent
in C hingegen:

#v+
#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000

int main(void)
{
   int i, max=0, imax;
   
   for (i=1; i <= MAX; ++i) {
      register long long z=i;
      register int cnt=1;
      while (z != 1) {
	 if (z % 2 == 0)
	   z /= 2;
	 else
	   z = 3*z+1;
	 
	 ++cnt;
      }
      
      if (cnt > max) {
	 max = cnt;
	 imax = i;
      }
   }
   
   printf("Max bei %d mit %d Schritten\n", imax, max);
   
   return EXIT_SUCCESS;
}
#v-

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

Bis auf die fehlenden Eingaberoutinen im C-Programm sind beide Programme
IMHO äquivalent (Meine ich zumindest). Wo könnte hier das Problem
liegen, dass die Python-Variante derart langsamer ist?
-- 
Jens Kubieziel                                  http://www.kubieziel.de