Wiele zadań programowania można wykonać na więcej niż jeden sposób, ale jeden sposób może być znacznie szybszy od drugiego. Projektowanie szybkich programów jest częścią sztuki i nauki programowania komputerowego. W tym ćwiczeniu przyjrzymy się kilku przykładom.
Część 1: Nie Zmieniaj Tego Samego Dwa Razy
Ciąg Fibonacciego jest fascynującym i prostym ciągiem liczb. Zaczynamy od dwóch liczb: 1 i 1. Aby uzyskać następną liczbę dodajemy poprzednie dwie. Dlatego następna liczba to 1 + 1 = 2. Daje to pierwsze trzy wyrazy,
1, 1, 2
i czwarty wyraz to 1+2=3, then we have 2+3=5 i wtedy mamy:
1, 1, 2, 3, 5, 8, 13, ...
Ciąg Fibonacciego został pierwotnie stworzony, na potrzeby obliczania populacji królików, ma fantastyczne powiązania z architekturą roślin. Oto część niesamowitej serii filmów o ciągu Fibonacciego:
Definicja ciągu Fibonacciego nadaje się w sposób naturalny do funkcji rekurencyjnej. Kolejne ćwiczenie definiuje funkcję Fibonacci(n) w celu otrzymania n-tej pozycji na powyższej liście (zaczynając od n=1).
Ta funkcja rekurencyjna staje się jednak zbyt wolna do obliczania kolejnych elementów ciągu. Naciśnij „Wprowadź polecenie testowe” i wpisz print(Fibonacci(80)). Podczas testowania otrzymasz komunikat "Limit czasu przekroczony".
Dlaczego tak powoli? Funkcja ta nie ma skomplikowanych instrukcji lub pętli, tylko dodawanie. Więc powolność okazuje się być związana z liczbą wszystkich odwołań do funkcji. Jeśli wywołujemy Fibonacci(3), funkcja rekurencyjna jest wywoływana łącznie trzy razy: początkowe wywołanie, a następnie dwa wywołania rekurencyjne. Jeśli wywołujemy Fibonacci(4), funkcja rekurencyjna jest wywoływana pięciokrotnie: początkowe wywołanie, trzy razy dla n=3 właśnie wspomniane i jedno wywołanie rekurencyjne dla n=2. Obliczanie Fibonacci(5) daje łącznie dziewięć wywołań, a Fibonacci(6) daje łącznie 9 + 5 + 1 = 15 wywołań. Liczba wywołań jest bardzo szybko bardzo duża, gdy n rośnie!
W przybliżonej ocenie, Fibonacci(n+2) wymaga co najmniej dwukrotnie większej liczby wywołań rekurencyjnych niż Fibonacci(n), ponieważ Fibonacci(n+2) bezpośrednio wywołuje Fibonacci(n) , a innym razem pośrednio przez rekurencyjne wywołanie Fibonacci(n+1). Więc czas obliczeniowy jest proporcjonalny do funkcji wykładniczej co najmniej tak dużej jak (√2)n. To jest zbyt powolne! Np. Fibonacci(80) wymaga więcej niż 240 = 1099511627776 wywołań rekurencyjnych.
Ten argument zawiera nawet dokładny problem konceptualny: dwukrotne wywołanieFibonacci(n) i ponowne obliczanie odpowiedzi od początku po raz drugi jest marnotrawstwem. Powinniśmy wymyślić jakieś podejście, w którym nie marnujemy czasu na ponowne obliczanie tej samej rzeczy w kółko.
Rozwiązanie
Spróbujmy w Pythonie zrobić coś bardziej podobnego do wprowadzenia. Zaczęliśmy od zapisu 1, 1. Następnie poszerzaliśmy sekwencję, dodając ostatnie dwa elementy razem. Oto jak wygląda kod; ponownie do ciebie należy odpowiednie posortowanie.
Nadal jest trochę miejsca na ulepszenia, ponieważ nie musimy ponownie obliczać całej tablicy w każdym nowym wywołaniu, ale jest to wystarczająco dobre, ponieważ działa szybko, nawet na dużych wartościach n!
Część2: Nie Obliczaj Niepotrzebnych Rzeczy, Nawet Raz
Nasz drugi przykład polega na sprawdzeniu, czy liczby są liczbami pierwszymi, co ma znaczenie w kryptografii i bezpieczeństwie komputerowym. Liczba jest pierwsza, jeśli ma dokładnie dwa dzielniki naturalne: 1 i samą siebie. Oto kilka kolejnych liczb pierwszych to 2, 3, 5, 7, 11, 13, 17, 19, 23. (Na przykład, 21 nie jest pierwsze, ponieważ ma następujące dzielniki 3 i 7, a także 1 i 21.)
W jaki sposób możemy sprawdzić, czy liczba jest pierwsza w Pythonie? Widzieliśmy wcześniej, jak sprawdzić podzielność:
N % D == 0 # will be True if D is a divisor of N, False otherwise
Poprzez sprawdzenie wszystkich możliwych dzielników, przystępujemy do następującego programu.
To działa! Ale dla dużych liczb też zbyt wolno. Naciśnij Wprowadź dane i wpisz isItPrime(324635459). Minął czas. Spróbuj dla innych wartości ... dla liczb pierwszych większych niż 10000000 kod przestaje działać, ponieważ nasz automatyczny tester może wykonać sprawdzanie podzielności tylko około 10 milionów razy na sekundę. Jeśli chcemy sprawdzić większe liczby, będziemy potrzebować bardziej wydajnego pomysłu. Napiszmy kod, który działa nawet dla liczb większych niż trylion (1000000000000)!
Czy naprawdę musimy sprawdzić wszystkie liczby między 2 a N-1, aby sprawdzić, czy N jest liczbą pierwszą?Wskazówka
Idea i Argument
Jeśli przeczytałeś wskazówkę i eksperymentowałeś, zauważyłeś, że jeśli N nie jest liczbą pierwszą, program zazwyczaj ma dość mały dzielnik w porównaniu z N. Na przykład iisItPrime(34827948723948723984729834) działa dość szybko, mimo że jego wejście jest gigantyczne, Znaleziony dzielnik to D=2.
Może nie musimy rzeczywiście sprawdzać wszystkich możliwych czynników. Czy istnieje niewielki limit liczby czynników, które musimy sprawdzić, zanim będziemy mogli być pewni, że N jest liczbą pierwszą? Na szczęście, tak! W rzeczywistości możemy argumentować to tak, że jeśli N nie jest liczbą pierwszą, to jeden z jej dzielników jest co najwyżej sqrt(N). Czemu? Cóż, jeśli N nie jest liczbą pierwszą, to ma dzielnik A. Bycie dzielnikiem oznacza, że jest jakaś inna liczba B taka, że
A*B == N
Kontynuujemy naszą argumentację. Jeśli A <= sqrt(N) lub B <= sqrt(N), to jesteśmy szczęśliwi: znaleźliśmy dzielnik N, który jest mały, tak jak chcieliśmy. Ale w rzeczywistości są to jedyne możliwości: w przeciwnym razie, dostajemy sprzeczność
N = A*B > sqrt(N)*sqrt(N) = N
Wspaniale! Więc teraz, należy wdrożyć ten nowy pomysł w Pythonie. Najłatwiejszym sposobem na zmianę starego podejścia jest dodanie testu do pętli for: once D > sqrt(N) (lub równoważnie, D*D > N), możemy właśnie z użyciem break wyjść z pętli i zatrzymać testowanie.
Program teraz działa na gigantycznych liczbach pierwszych!
Ćwiczenie Końcowe
W tym ćwiczeniu łączymy obliczanie liczb pierwszych z drugiej połowy lekcji z podejściem opartym na listach z pierwszej połowy. Twój kod powinien wypełnić tablicę o długości 1000001, tak że isPrime[N] jest równa True, jeśli N jest liczbą pierwszą, a False jeśli N jest liczbą złożoną, dla wszystkich N do jednego miliona. (isPrime[0] i isPrime[1] powinny być Fals.)
Kliknij tutaj, aby uzyskać podpowiedź. I to dużą!
 | To ostatnie ćwiczenie w witrynie CS Circles. Gratulacje dla tych, którzy próbowali wszystkich lekcji! Więcej informacji na temat tego, czego się dowiedziałeś, znajdziesz na stronie zasobów. Miłej zabawy, powodzenia w dobrym kodowaniu! |
