Więc jesteś. Ulżyło. Wyczerpany. W końcu wymyśliłeś podejście do rozwiązania trudnego pytania o kodowanie, o które pyta cię osoba przeprowadzająca wywiad. Być może nawet napisałeś to na tablicy, linia po linii. I dobrze się bawiłeś! Masz tylko 20 minut na spotkanie. Twój ankieter musi być pod wrażeniem.
Dobrze?
„To zadziała, ale są jakieś pomysły na to, jak zrobić to bardziej efektywnie?”
Twoje serce tonie. Myślałeś, że skończyłeś z trudną częścią projektowania algorytmów! Próbujesz wymyślić więcej sposobów rozwiązania problemu, ale wszystko, co możesz wymyślić, to jedyne podejście, które już wymyśliłeś.
Zdarza się to prawie wszystkim. I to nie dlatego, że są głupie. To dlatego, że większość ludzi nie ma metody na poprawę wydajności swoich algorytmów.
Ale prawda jest taka, że jest ich mnóstwo. Następnym razem, gdy będziesz zaskoczony, spróbuj zastosować te trzy typowe podejścia.
1. Użyj mapy skrótów
Zgadza się. Mapy skrótów / tablice asocjacyjne / słowniki (noszą wiele nazw, w zależności od używanego języka programowania) mają magiczną zdolność obniżania czasu działania algorytmów.
Załóżmy na przykład, że chodziło o znalezienie najczęściej powtarzanej liczby w tablicy liczb.
Twoją pierwszą myślą może być wskoczenie w jakieś pętle. Dla każdej z naszych liczb oblicz jej liczbę i sprawdź, czy jest to największy. Jak uzyskać liczbę dla każdej liczby? Pętlę przez tablicę, licząc, ile razy występuje! Mówimy więc o dwóch zagnieżdżonych pętlach. W pseudokodzie:
def get_mode (nums): max_count = 0 mode = null dla potencjał_mode w nums: count = 0 dla liczby w naszym_array: count + = 1 if count> = max_count: mode = potencjał_mode max_count = tryb powrotu licznika
W tej chwili przeglądamy całą naszą tablicę jeden raz dla każdego elementu w tablicy - ale możemy zrobić lepiej. W dużej notacji O jest to w sumie czas O (n 2 ).
Jeśli przechowujemy nasze liczby na mapie mieszającej (odwzorowując liczby na ich liczby), możemy rozwiązać problem w jednym przejściu przez tablicę (czas O (n)!):
def get_mode:
O wiele szybciej!
2. Użyj manipulacji bitami
To naprawdę odróżni cię od paczki. Nie dotyczy to każdego problemu, ale jeśli trzymasz to w tylnej kieszeni i wyjdziesz z niego we właściwym czasie, będziesz wyglądać jak gwiazda rocka.
Oto przykład: Załóżmy, że mieliśmy tablicę liczb, w której każda liczba pojawia się dwa razy, z wyjątkiem jednej liczby, która występuje tylko raz. Piszemy funkcję, aby znaleźć samotną, niepowtarzalną liczbę.
Twoim pierwszym instynktem może być użycie mapy skrótów, ponieważ właśnie o niej rozmawialiśmy. To dobry instynkt! I to zadziała w tym przypadku. Możemy stworzyć bardzo podobną mapę „zliczeń” i użyć jej, aby zobaczyć, która liczba kończy się liczbą 1.
Ale jest jeszcze lepszy sposób. Jeśli znasz manipulację bitami, możesz znać XOR. Jedną z wyjątkowych cech XOR jest to, że jeśli XOR jest liczbą samą z siebie, bity „anulują” do 0. W przypadku tego problemu, jeśli XOR razem każdą liczbę w tablicy, pozostanie nam jedna liczba, która nie nie anuluj:
def find_unrepeated (nums): unrepeated = 0 for num in nums: unrepeated = unrepeated XOR num return unrepeated
3. Przejdź od dołu do góry
Napisz funkcję, która wyprowadza „n-tą” liczbę Fibonacciego, podając liczbę n. Ten jest klasykiem i bardzo dobrze nadaje się do rekurencji:
def fib (n): jeśli n wynosi 0 lub 1: zwróć 1 return fib (n-1) + fib (n-2)
Ale prosta rekurencyjna odpowiedź nie jest jedyna! Zastanów się dokładnie, co robi ta funkcja. Załóżmy, że n wynosi 5. Aby uzyskać odpowiedź, rekurencyjnie wywołuje fib (4) i fib (3). Co robi to wezwanie do Fib (4)? Nazywa fib (3) i fib (2). Ale właśnie powiedzieliśmy, że już zadzwoniliśmy do Fib (3)! Ta urocza funkcja rekurencyjna wykonuje wiele powtórzeń. Całkowity koszt czasu okazuje się być O (2 n ). To źle - znacznie gorzej niż O (n 2 ).
Zamiast przechodzić od n rekurencyjnie w dół do 1, przejdźmy od dołu do góry od 1 do n. To pozwala nam pominąć rekurencję:
def fib (n): poprzedni = 0 poprzedni_poprzedni = 1 dla i w zakresie od 1 do n: bieżący = poprzedni + poprzedni_poprzedni poprzedni_poprzedni = poprzedni poprzedni = obecny prąd powrotny
Kod jest dłuższy, ale jest znacznie wydajniejszy! Do czasu O (n). Dodatkową zaletą rozwijanych algorytmów rekurencyjnych jest oszczędność miejsca. Wszystkie te rekurencyjne połączenia gromadzą się w stosie połączeń, który znajduje się w pamięci i jest wliczany do kosztu miejsca. Nasza funkcja rekurencyjna kosztowała O (n) miejsca, ale ta iteracyjna zajmuje O (1) miejsca.
Następnym razem, gdy Twój ankieter poprosi Cię o poprawę wydajności rozwiązania, spróbuj przejrzeć te strategie i sprawdzić, czy Ci pomogą. Przy wystarczającej praktyce prawdopodobnie skoczysz prosto do zoptymalizowanego rozwiązania, pomijając bardziej naiwne rozwiązanie. I to jest świetna rzecz. Nie oznacza to tylko, że stajesz się lepszym ankieciem - oznacza to, że stajesz się lepszym inżynierem.
