Python 사전 과 목록 성능 간 의 비교

Python 목록 과 사전
4.567917.앞에서 우 리 는'대 O 표현법'과 서로 다른 알고리즘 에 대한 평 가 를 알 게 되 었 다.다음은 Python 두 가지 내 장 된 데이터 형식 과 관련 된 각종 작업 의 대 O 수량 급:목록 list 와 사전 dict 를 토론 한다4.567917.이것 은 Python 에서 매우 중요 한 데이터 유형 으로 그 다음 에 각종 데이터 구 조 를 실현 하고 운행 시험 을 통 해 각종 조작 운행 시간 수량 급 을 평가 할 것 이다list 와 dict 를 비교 하 는 작업 은 다음 과 같 습 니 다.

List 목록 데이터 형식 상용 조작 성능:
가장 많이 사용 되 는 것 은 색인 에 따라 값 을 추출 하고 할당(v=a[i],a[i]=v)입 니 다.목록 의 무 작위 접근 특성 으로 인해 이 두 작업 의 실행 시간 은 목록 크기 와 상 관 없 이 모두 O(1)입 니 다.
다른 하 나 는 목록 이 늘 어 나 면 append()와'+'를 선택 할 수 있 습 니 다.lst.append(v),실행 시간 은 O(1)입 니 다.lst=lst+[v],실행 시간 은 O(n+k)입 니 다.그 중에서 k 는 추 가 된 목록 길이 입 니 다.어떤 방법 으로 목록 을 조작 하 는 지 선택 하 는 것 도 프로그램의 성능 을 결정 합 니 다.
n 개의 정수 목록 을 만 드 는 4 가지 방법 을 테스트 합 니 다:

Timer 대상 을 만 들 고 반복 적 으로 실행 해 야 할 문구 와 한 번 만 실행 해 야 할'설치 문'을 지정 합 니 다.
그리고 이 대상 의 timeit 방법 을 호출 하여 몇 번 반복 되 는 지 지정 합 니 다.

# Timer(stmt="pass", setup="pass")   #          
# stmt：statement   ，        ，      
# setup：        （  run   ，         ）              
time1 = Timer("test1()", "from __main__ import test1") 
print("concat：{} seconds".format(time1.timeit(1000)))
time2 = Timer("test2()", "from __main__ import test2")
print("append：{} seconds".format(time2.timeit(1000)))
time3 = Timer("test3()", "from __main__ import test3")
print("comprehension：{} seconds".format(time3.timeit(1000)))
time4 = Timer("test4()", "from __main__ import test4")
print("list range：{} seconds".format(time4.timeit(1000))

결 과 는 다음 과 같다.

이 를 통 해 알 수 있 듯 이 4 가지 방법 은 운행 시간 차이 가 매우 크 고 목록 연결(concat)이 가장 느 리 며 List range 가 가장 빠 르 고 속도 차이 가 100 배 에 가깝다.append 는 concat 보다 훨씬 빠르다.또한,우 리 는 목록 유도 식 속도 가 append 의 두 배 정도 되 는 것 을 알 게 되 었 다.
총 결 목록 기본 작업 의 대 O 수량 레벨:

pop 이 동작 을 알 게 되 었 습 니 다.pop()은 목록 끝 에서 요 소 를 제거 하고 시간 복잡 도 는 O(1)입 니 다.pop(i)은 목록 중부 에서 요 소 를 제거 하고 시간 복잡 도 는 O(n)입 니 다.
그 이 유 는 Python 이 선택 한 실현 방법 입 니 다.중부 에서 요 소 를 제거 하면 요소 뒤의 요 소 를 모두 앞으로 옮 겨 복사 해 야 합 니 다.이것 은 좀 서 툴 러 보 입 니 다.
그러나 이러한 실현 방법 은 목록 이 색인 에 따라 값 을 추출 하고 할당 하 는 작업 이 빠 르 고 O(1)에 이 를 수 있 도록 보장 할 수 있다.이것 도 상용 과 상용 하지 않 는 조작 에 대한 절충 방안 이 라 고 할 수 있다.
list.pop()의 시간 측정 시험 은 목록 의 크기 를 바 꾸 어 두 작업 의 증가 추 세 를 테스트 합 니 다.

import timeit

pop_first = timeit.Timer("x.pop(0)", "from __main__ import x")
pop_end = timeit.Timer("x.pop()", "from __main__ import x")
print("pop(0)          pop()")
y_1 = []
y_2 = []
for i in range(1000000, 10000001, 1000000):
    x = list(range(i))
    p_e = pop_end.timeit(number=1000)
    x = list(range(i))
    p_f = pop_first.timeit(number=1000)
    print("{:.6f}        {:.6f}".format(p_f, p_e))
    y_1.append(p_f)
    y_2.append(p_e)

결 과 는 다음 과 같다.

시험 결 과 를 시각 화하 면 성장 추 세 를 알 수 있다.pop()은 평탄 한 상수 이 고 pop(0)은 선형 성장 추세 이다.

사전 은 목록 과 달리 키(key)에 따라 데이터 항목 을 찾 고 목록 은 색인(index)에 따라 찾 습 니 다.가장 많이 사용 되 는 수치 와 할당 값 은 모두 O(1)입 니 다.또 다른 중요 한 동작 인 contains(in)는 사전 에 어떤 키(key)가 존재 하 는 지 판단 하 는 것 이 며,이 성능 도 O(1)입 니 다.

성능 테스트 를 통 해 list 에서 값 을 검색 하고 dict 에서 값 을 검색 할 때 대비 하여 연속 값 을 포함 하 는 list 와 연속 키 키 키 를 포함 하 는 key 를 생 성 합 니 다.
dict,연산 자 in 의 시간 을 무 작위 로 검사 합 니 다.

import timeit
import random

y_1 = []
y_2 = []
print("lst_time         dict_time")
for i in range(10000, 1000001, 25000):
    t = timeit.Timer("random.randrange(%d) in x" % i, "from __main__ import random, x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    x = {j: 'k' for j in range(i)}
    dict_time = t.timeit(number=1000)
    print("{:.6f}        {:.6f}".format(lst_time, dict_time))
    y_1.append(lst_time)
    y_2.append(dict_time)

결 과 는 다음 과 같다.


4.567917.사전 의 집행 시간 은 규모 와 상 관 없 이 상수 임 을 알 수 있다4.567917.목록 의 실행 시간 은 목록 의 규모 가 커지 면서 선형 으로 올라간다더 많은 Python 데이터 형식 작업 복잡 도 는 공식 문 서 를 참고 할 수 있 습 니 다.
https://wiki.python.org/moin/TimeComplexity
파 이 썬 사전 과 목록 성능 간 의 비교 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 파 이 썬 목록 과 사전 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!