2014-10-26 13 views
6

Jest to głównie ćwiczenie w uczeniu się Pythona. Napisałem tę funkcję sprawdzania, czy dana liczba jest pierwsza:Wydajność dowolnej()

def p1(n): 
    for d in xrange(2, int(math.sqrt(n)) + 1): 
     if n % d == 0: 
      return False 
    return True 

Wtedy zdałem sobie sprawę, mogę łatwo przerobić go za pomocą dowolnego():

def p2(n): 
    return not any((n % d == 0) for d in xrange(2, int(math.sqrt(n)) + 1)) 

Performance-mądry, spodziewałem p2 być szybciej niż, lub co najmniej tak szybko jak p1 ponieważ każda() jest wbudowany, ale za duży-owski prime, p2 jest trochę wolniej:

$ python -m timeit -n 100000 -s "import test" "test.p1(999983)" 
100000 loops, best of 3: 60.2 usec per loop 

$ python -m timeit -n 100000 -s "import test" "test.p2(999983)" 
100000 loops, best of 3: 88.1 usec per loop 

używam dowolny() niepoprawnie tutaj ? Czy istnieje sposób, aby napisać tę funkcję za pomocą dowolnej(), tak aby było aż iterating się?

Update: Liczby do jeszcze większej sile

$ python -m timeit -n 1000 -s "import test" "test.p1(9999999999971)" 
1000 loops, best of 3: 181 msec per loop 

$ python -m timeit -n 1000 -s "import test" "test.p2(9999999999971)" 
1000 loops, best of 3: 261 msec per loop 
+0

zobacz https://docs.python.org/2/library/functions.html#any wygląda całkiem podobnie do tego, co napisałeś. – njzk2

+1

@ rightføld Zwiększenie o 50% to niewielka różnica? – Barmar

+0

Nie, ale <1000 iteracji jest wystarczająco małą liczbą, że kilka dodatkowych ramek stosu (nie wspominając o rzeczach dziejących się gdzie indziej w twoim komputerze w tym czasie) wciąż jest znaczących w porównaniu do treści pętli. –

Odpowiedz

4

różnica wydajności jest minimalny, ale przyczyną tego, że istnieje to, że any ponosi budowania wyrażenia generatora, a dodatkowe wywołanie funkcji, w porównaniu do pętli for . Oba mają jednak identyczne zachowania (ocena skrótów).

Wraz ze wzrostem wielkości wejściowej różnica nie zmniejszy się (myliłem się), ponieważ używasz wyrażenia generatora, a iteracja po nim wymaga wywołania metody (.next()) i dodatkowej ramki stosu . any robi to pod maską, oczywiście.

Pętla for iteruje nad obiektem xrange. any jest iterowaniem po wyrażeniu generatora, które samo w sobie jest iterowane nad obiektem xrange.

W obu przypadkach użyj tego, który zapewnia najbardziej czytelny/możliwy do utrzymania kod. Wybór jednego z nich będzie miał niewielki wpływ na wydajność jakiegokolwiek programu, który piszesz.

+0

Dzięki. Rozumiem, że mają identyczne zachowania, tylko próbują nauczyć się właściwego korzystania z wbudowanych funkcji, ponieważ jestem nowy w Pythonie. Ale nie widzę, żeby różnica zmniejszyła się dla jeszcze większych liczb pierwszych (trochę zaktualizuję to pytanie). Nawet w przypadku 13-cyfrowego poziomu początkowego różnica nadal wynosi około 50% (~ 180 ms w porównaniu z ~ 270 ms). Dostaję twój punkt widzenia na czytelność, ale dla tego szczególnego ćwiczenia, jestem bardziej zainteresowany zrozumieniem użycia jakiegokolwiek(). – linus

+0

Dzięki. To ma sens. Nie zgadzam się z tym, że nie ma to wpływu na wydajność. Jedna implementacja wydaje się być konsekwentnie o 50% wolniejsza od drugiej, więc w zależności od tego, jak często ta funkcja jest wywoływana, może występować znacząca różnica w wydajności. Powiedział, że twój punkt widzenia na wyrażenie generatora ma dla mnie sens. Dzięki! – linus

+0

Cóż, jak zwykle, napisz działający, czytelny kod, * następnie * profil i zoptymalizuj. Zawsze w tej kolejności;) –