Python Language
Python 프로그램 속도

표기법

기본 아이디어

파이썬 프로그램의 속도를 설명 할 때 사용되는 표기법을 Big-O 표기법이라고합니다. 함수가 있다고 가정 해 보겠습니다.

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

이것은 항목이 목록에 있는지 확인하는 간단한 기능입니다. 이 함수의 복잡성을 설명하기 위해 O (n)이라고 말할 것입니다. 즉, O 함수로서 "Order of n"을 Order 함수라고합니다.

O (n) - 일반적으로 n은 컨테이너에있는 항목의 수입니다.

O (k) - 일반적으로 k는 매개 변수의 값 또는 매개 변수의 요소 수입니다

목록 작업

작업 : 평균 사례 (매개 변수가 임의로 생성 된 것으로 가정)

추가 : O (1)

복사 : O (n)

Del 슬라이스 : O (n)

항목 삭제 : O (n)

삽입 : O (n)

아이템 가져 오기 : O (1)

설정 항목 : O (1)

반복 : O (n)

슬라이스 가져 오기 : O (k)

슬라이스 설정 : O (n + k)

확장 : O (k)

정렬 : O (n log n)

곱하기 : O (nk)

x in s : O (n)

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

길이 가져 오기 : O (1)

Deque 연산

양단 큐는 양 끝 큐입니다.

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)

작업 : 평균 사례 (매개 변수가 임의로 생성 된 것으로 가정)

추가 : O (1)

Appendleft : O (1)

복사 : O (n)

확장 : O (k)

Extendleft : O (k)

팝 : O (1)

Popleft : O (1)

제거 : O (n)

회전 : O (k)

조작 설정

연산 : 평균 사례 (무작위로 생성 된 매개 변수를 가정) : 최악의 경우

x in s : O (1)

차이 s - t : O (len (s))

교차점 s & t : O (min (len (s), len (t))) : O (len (s) * len (t)

l은 max (len (s1), ..., len (sn))이고, l은 max (len (s1), ..., len

sdifference_update (t) : O (len (t)) : O (len (t) * len (s))

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

대칭 차이 s ^ t : O (len (s)) : O (len (s) * len (t))

조합 s | t : O (len (s) + len (t))

알고리즘 표기법 ...

모든 컴퓨터 언어의 최적화에 적용되는 특정 원칙이 있으며 Python도 예외는 아닙니다. 최적의 상태에 상관없이 프로그램을 작성하고 코드가 깨끗하고 정확하며 이해할 수 있는지 확인하는 데 집중하십시오. 완료 한 후에 너무 크거나 너무 느린 경우 최적화를 고려할 수 있습니다.

80/20 규칙을 기억하십시오 : 많은 분야에서 20 %의 노력으로 결과의 80 %를 얻을 수 있습니다 (또한 90/10 규칙이라고도합니다 - 당신이 말하는 사람에 달려 있습니다). 코드를 최적화하려고 할 때마다 프로파일 링을 사용하여 실행 시간의 80 %가 어디인지 파악하므로 어디에서 노력을 집중해야하는지 알 수 있습니다.

항상 "이전"과 "이후"벤치 마크 를 실행하십시오. 최적화가 실제로 효과를 냈다는 사실을 어떻게 알게 될까요? 최적화 된 코드가 원래 버전보다 약간 빠르거나 작을 경우 변경 사항을 취소하고 원래의 코드를 지우십시오.

올바른 알고리즘 및 데이터 구조 사용 : O (n log n) 퀵 소트가있을 때 O (n2) 버블 정렬 알고리즘을 사용하여 천 가지 요소를 정렬하지 마십시오. 마찬가지로 O (log n) 2 진 트리 나 O (1) Python 해시 테이블을 사용할 수있을 때 O (n) 검색이 필요한 배열에 1000 개의 항목을 저장하지 마십시오.

아래의 링크를 방문하십시오 ... Python Speed ​​Up

다음 3 개의 점근 표기법은 대부분 알고리즘의 시간 복잡도를 나타 내기 위해 사용됩니다.

1. Θ 표기법 : theta 표기법은 함수를 위와 아래에서 경계 짓기 때문에 정확한 점근 행동을 정의합니다. 표현의 쎄타 표기법을 얻는 간단한 방법은 낮은 차수의 용어를 삭제하고 선행 상수를 무시하는 것입니다. 예를 들어, 다음 표현식을 고려하십시오. 관련된 상수와 관계없이 항상 Θ (n3)이 Θn2보다 높은 n0가 있기 때문에 더 낮은 차수의 항을 제거하는 것은 항상 문제가되지 않습니다. 3n3 + 6n2 + 6000 = Θ (n3) 주어진 함수 g (n)에 대해 우리는 Θ (g (n))가 함수 집합을 따르고 있음을 나타냅니다. 모든 n> n에 대해 0 <= c1 g (n) <= f (n) <= c2 g (n)이되도록 양의 상수 c1, c2 및 n0가 존재한다. = n0} 위의 정의는 f (n)이 g (n)의 세타 인 경우 n (n> n)의 큰 값에 대해 값 c (n)와 c2 g = n0). theta의 정의는 n이 n0보다 큰 경우 f (n)이 음이 아니어야 함을 요구합니다.

2. Big O 표기법 : Big O 표기법은 알고리즘의 상한선을 정의하며 위에서 만 함수를 묶습니다. 예를 들어, 삽입 정렬의 경우를 생각해보십시오. 최악의 경우 최상의 경우에는 선형 시간이 걸리고 최악의 경우에는 2 차 시간이 걸립니다. 삽입 정렬의 시간 복잡도가 O (n ^ 2)라고 안전하게 말할 수 있습니다. O (n ^ 2)는 선형 시간도 포함한다는 점에 유의하십시오. 삽입 정렬의 시간 복잡도를 나타 내기 위해 Θ 표기법을 사용하는 경우, 최악의 경우와 최악의 경우에 대해 다음 두 문장을 사용해야합니다.

1. 삽입 정렬의 최악의 시간 복잡도는 Θ (n ^ 2)입니다.
2. 삽입 정렬의 최상의 시간 복잡도는 Θ (n)입니다.

Big O 표기법은 알고리즘의 시간 복잡도에 대한 상한 만 가지고있을 때 유용합니다. 많은 경우 알고리즘을 간단히 살펴봄으로써 상한을 쉽게 찾을 수 있습니다. 모든 n> = n0에 대해 0 <= f (n) <= cg (n)이되도록 양의 상수 c와 n0가 존재한다.

3. Ω Notation : Big O 표기법이 함수에 점근 상한을 제공하는 것처럼, Ω 표기법은 점근 적 하한값을 제공합니다. Ω 표기법 <알고리즘의 시간 복잡도가 낮을 ​​때 유용합니다. 이전 게시물에서 논의했듯이 알고리즘의 최상의 경우 성능은 일반적으로 유용하지 않습니다. 오메가 표기법은 세 가지 모두에서 가장 적은 표기법입니다. 주어진 함수 g (n)에 대해 우리는 Ω (g (n))을 함수 집합으로 나타냅니다. 모든 n> = n0에 대해 0 <= cg (n) <= f (n)이되도록 양의 상수 c와 n0가 존재합니다. 여기에 같은 삽입 정렬 예제를 고려해 보겠습니다. 삽입 정렬의 시간 복잡도는 Ω (n)으로 작성할 수 있지만 일반적으로 최악의 경우와 때로는 평균적인 경우에 관심이 있으므로 삽입 정렬에 대한 유용한 정보는 아닙니다.