Python bardzo powolny w porównaniu do Javy dla tego algorytmu

Question

Studiuję algorytmy i postanowiłem przenieść programy Java z podręcznika na język Python, ponieważ nie podoba mi się obciążenie Java, szczególnie w przypadku małych programów i jako ćwiczenie.

Algorytm sam w sobie jest bardzo prosty, po prostu pobiera wszystkie triplety z tablicy, w sposób brutalny, i policzy, ile z trioli sumuje się do zera (np .: [-2,7, -5])

public static int count(int[] a) { 
     int N = a.length; 
     int cnt = 0; 
     for (int i = 0; i < N; i++) { 
      for (int j = i+1; j < N; j++) { 
       for (int k = j+1; k < N; k++) { 
        if (a[i] + a[j] + a[k] == 0) { 
         cnt++; 
        } 
       } 
      } 
     } 
     return cnt; 
    } 

I przeniósł go do:

def count(a): 
    cnt = 0 
    ln = len(a) 
    for i in xrange(0,ln): 
     for j in xrange(i + 1,ln): 
      for k in xrange(j + 1,ln): 
       if a[i] + a[j] + a[k] == 0: 
        cnt+=1 
    return cnt 

teraz pomiarowych tylko tych funkcji biorą:

java : array of 2000 elements --> 3 seconds 
python : array of 2000 elements --> 2 minutes, 19 seconds 

UPDATE 
python (pypy) : array of 2000 elements --> 4 seconds (:-)) 

Oczywiście nie jest to dobry algorytm, po prostu pokazuje, zarówno tutaj, jak iw podręczniku. Zrobiłem już trochę programowania zarówno w Javie, jak iw Pythonie, ale nie zdawałem sobie sprawy z tej ogromnej różnicy.

Pytanie sprowadza się do: jak przezwyciężyć to? Dokładniej:

1. Czy ten kod jest dobrym portem, czy też brakuje mi czegoś trywialnego?
2. Czy przejście na inny Jython środowiska wykonawczego, na przykład rozwiązanie? Czy łatwo jest utrzymać mój kod w czasie zaćmienia i po prostu dodać interpreter (kompilator?)? Czy przejście na inny interpreter/kompilator tylko trochę poprawi?

Teraz używam Python 2.7.3 i Java 1.7 32ibts na windows 7.

wiem, że istnieją podobne pytania tam na SO o wydajności Java/Python, ale odpowiedzi jak istnieją różne środowiska uruchomieniowe dla Pythona nie są obecnie dla mnie pomocne.

Co chcę wiedzieć, czy niektóre z tych środowisk wykonawczych mogą zamknąć tę ogromną lukę i są warte epoklacji?

UPDATE:

zainstalowałem pypy i teraz różnice są ogromne ...

UPDATE 2:

kilka bardzo ciekawych rzeczy zauważyłem: metoda islice w odpowiedzi tutaj jest szybsze na "regularny" python, ale dużo wolniejszy na pypie. Mimo to, pypy nadal działa o wiele szybciej, bez względu na to, że używa regularnych pętli lub islices w tym algorytmie

Jak zauważa Bakuriu w środowisku wykonawczym, środowiska mogą mieć duże znaczenie, ale środowisko runtime szybciej dla tego algorytmu niekoniecznie musi być szybciej dla każdego algorytmu ...

Answer 1

Spróbuj uruchomić go z PyPy zamiast CPython. Prawdopodobnie pójdzie o wiele szybciej.

Answer 2

Jak już wspomniano w komentarzach do twojego postu startowego, nie ma dobrego sposobu, aby zrobić to znacznie szybciej (poza PyPy). Możesz wypróbować islice, które będzie iterować po "a" i nie tworzyć nowych list lub zakresów, to powinno być krótsze.

from itertools import islice 

def count(a): 
    cnt = 0 
    for x, i in enumerate(islice(a,0, None)): 
     for y, j in enumerate(islice(a, x + 1, None)): 
      for k in islice(a, y + x + 2, None): 
       if i + j + k == 0: 
        cnt+=1 
    return cnt 

Answer 3

Zaimplementowałem również funkcję w C i PHP.Oto wynik:

PHP: +23,977946043015 s
Python: 19.31 sek

C: 0,4 sek
Java: 0,42 sek

Szukamy w języku z innym systemem typów. PHP i Python są wpisywane dynamicznie, a C i Java są statycznie pisane.

Tłumacz PHP i Python spędzają dużo czasu na odgadywaniu typu używanych zmiennych i dlatego działają bardzo wolno. Podczas gdy w języku C i Java typ zmiennych (i elementów tablicy) jest statyczny, tzn. Jest liczbą całkowitą, a zatem zapisywany jest czas zgadywania. I najwyraźniej czas zgadywania jest zbyt wysoki, jak widać z powyższych liczb.

Z PyPY czas odgadywania jest znacznie zmniejszony, ponieważ PyPY używa kompilacji Just In Time (JIT). Ta metoda jest bardzo dobra w odgadywaniu rodzaju używanej zmiennej, a zatem pojawia się uderzenie wydajności.