Python Language
Szybkość programu w języku Python

Notacja

Podstawowy pomysł

Notacja używana przy opisywaniu prędkości programu w języku Python nazywa się notacją Big-O. Powiedzmy, że masz funkcję:

def list_check(to_check, the_list):
    for item in the_list:
        if to_check == item:
          return True
    return False

Jest to prosta funkcja do sprawdzenia, czy element znajduje się na liście. Aby opisać złożoność tej funkcji, powiesz O (n). Oznacza to „Rząd n”, ponieważ funkcja O jest znana jako funkcja Porządek.

O (n) - ogólnie n jest liczbą pozycji w pojemniku

O (k) - ogólnie k jest wartością parametru lub liczbą elementów w parametrze

Lista operacji

Operacje: Średnia wielkość liter (zakłada, że parametry są generowane losowo)

Dołącz: O (1)

Kopiuj: O (n)

Del slice: O (n)

Usuń element: O (n)

Wstaw: O (n)

Zdobądź przedmiot: O (1)

Ustaw element: O (1)

Iteracja: O (n)

Uzyskaj plasterek: O (k)

Ustaw plasterek: O (n + k)

Wydłuż: O (k)

Sortuj: O (n log n)

Pomnóż: O (nk)

x in s: O (n)

min (s), max (s): O (n)

Uzyskaj długość: O (1)

Operacje Deque

Deque to kolejka dwustronna.

class Deque:
def __init__(self):
    self.items = []

def isEmpty(self):
    return self.items == []

def addFront(self, item):
    self.items.append(item)

def addRear(self, item):
    self.items.insert(0,item)

def removeFront(self):
    return self.items.pop()

def removeRear(self):
    return self.items.pop(0)

def size(self):
    return len(self.items)

Operacje: Średnia wielkość liter (zakłada, że parametry są generowane losowo)

Dołącz: O (1)

Appendleft: O (1)

Kopiuj: O (n)

Wydłuż: O (k)

Extendleft: O (k)

Pop: O (1)

Popleft: O (1)

Usuń: O (n)

Obróć: O (k)

Ustaw operacje

Operacja: Średnia wielkość liter (zakłada parametry generowane losowo): Najgorsza wielkość

x in s: O (1)

Różnica s - t: O (długość (s))

Przecięcie s & t: O (min (len (s), len (t))): O (len (s) * len (t)

Wielokrotne przecięcie s1 i s2 i s3 i ... & sn:: (n-1) * O (l) gdzie l jest max (len (s1), ..., len (sn))

s.difference_update (t): O (len (t)): O (len (t) * len (s))

s.symetric_difference_update (t): O (len (t))

Różnica symetryczna s ^ t: O (len (s)): O (len (s) * len (t))

Unia s | t: O (len (s) + len (t))

Notacje algorytmiczne ...

Istnieją pewne zasady dotyczące optymalizacji w dowolnym języku komputerowym, a Python nie jest wyjątkiem. Nie optymalizuj na bieżąco : pisz swój program bez względu na możliwe optymalizacje, koncentrując się zamiast tego na upewnieniu się, że kod jest czysty, poprawny i zrozumiały. Jeśli po zakończeniu jest za duży lub za wolny, możesz go zoptymalizować.

Zapamiętaj zasadę 80/20 : W wielu polach możesz uzyskać 80% wyniku przy 20% wysiłku (zwanym także zasadą 90/10 - zależy to od tego, z kim rozmawiasz). Za każdym razem, gdy masz zamiar zoptymalizować kod, skorzystaj z profilowania, aby dowiedzieć się, dokąd zmierza 80% czasu wykonania, abyś wiedział, gdzie skoncentrować wysiłek.

Zawsze uruchamiaj testy porównawcze „przed” i „po” : skąd jeszcze dowiesz się, że Twoje optymalizacje naprawdę coś zmieniły? Jeśli zoptymalizowany kod okaże się tylko nieco szybszy lub mniejszy niż oryginalna wersja, cofnij zmiany i wróć do pierwotnego, czystego kodu.

Użyj odpowiednich algorytmów i struktur danych: Nie używaj algorytmu sortowania bąbelkowego O (n2) do sortowania tysiąca elementów, gdy jest dostępny szybki sortowanie O (n log n). Podobnie, nie przechowuj tysiąca elementów w tablicy, która wymaga wyszukiwania O (n), gdy można użyć drzewa binarnego O (log n) lub tabeli skrótów O (1) Python.

Aby uzyskać więcej, odwiedź poniższy link ... Przyspieszenie Pythona

Poniższe 3 asymptotyczne notacje są najczęściej używane do reprezentowania złożoności czasowej algorytmów.

1. Θ Notacja : Notacja theta ogranicza funkcje od góry i od dołu, więc określa dokładne zachowanie asymptotyczne. Prostym sposobem na uzyskanie notacji Theta wyrażenia jest usunięcie pojęć niskiego rzędu i zignorowanie wiodących stałych. Weźmy na przykład następujące wyrażenie. 3n3 + 6n2 + 6000 = Θ (n3) Odrzucanie warunków niższego rzędu jest zawsze w porządku, ponieważ zawsze będzie n0, po którym Θ (n3) ma wyższe wartości niż Θn2) niezależnie od zaangażowanych stałych. Dla danej funkcji g (n) oznaczamy, że Θ (g (n)) jest następującym zestawem funkcji. Θ (g (n)) = {f (n): istnieją stałe dodatnie c1, c2 i n0 takie, że 0 <= c1 g (n) <= f (n) <= c2 g (n) dla wszystkich n> = n0} Powyższa definicja oznacza, że jeśli f (n) to theta g (n), to wartość f (n) zawsze zawiera się między c1 g (n) i c2 g (n) dla dużych wartości n (n> = n0). Definicja theta wymaga również, aby f (n) nie było ujemne dla wartości n większych niż n0.

2. Notacja Big O : Notacja Big O określa górną granicę algorytmu, ogranicza funkcję tylko z góry. Rozważmy na przykład przypadek sortowania wstawianego. W najlepszym przypadku zajmuje to czas liniowy, aw najgorszym - czas kwadratowy. Możemy śmiało powiedzieć, że złożoność czasowa sortowania przez wstawianie wynosi O (n ^ 2). Zauważ, że O (n ^ 2) obejmuje również czas liniowy. Jeśli używamy notacji to do reprezentowania złożoności czasowej sortowania wstawianego, musimy użyć dwóch instrukcji dla najlepszych i najgorszych przypadków:

1. W najgorszym przypadku złożoność sortowania wstawianego wynosi Θ (n ^ 2).
2. Najlepsza złożoność czasu wstawiania sortowania wstawianego to Θ (n).

Notacja Big O jest przydatna, gdy mamy górną granicę złożoności algorytmu. Wiele razy łatwo znajdujemy górną granicę, po prostu patrząc na algorytm. O (g (n)) = {f (n): istnieją stałe dodatnie c i n0 takie, że 0 <= f (n) <= cg (n) dla wszystkich n> = n0}

3. Notacja Ω : Tak jak notacja Big O zapewnia asymptotyczną górną granicę funkcji, notacja Ω zapewnia asymptotyczną dolną granicę. Notacja Ω <może być użyteczna, gdy mamy dolne ograniczenie złożoności czasowej algorytmu. Jak omówiono w poprzednim poście, najlepsza wydajność algorytmu na ogół nie jest przydatna, notacja Omega jest najmniej używaną notacją spośród wszystkich trzech. Dla danej funkcji g (n) oznaczamy przez Ω (g (n)) zestaw funkcji. Ω (g (n)) = {f (n): istnieją stałe dodatnie c i n0 takie, że 0 <= cg (n) <= f (n) dla wszystkich n> = n0}. Rozważmy ten sam przykład sortowania wstawiania tutaj. Złożoność czasowa sortowania wstawianego może być zapisana jako Ω (n), ale nie jest to bardzo przydatna informacja o sortowaniu wstawianym, ponieważ generalnie interesuje nas najgorszy przypadek, a czasem średni przypadek.