내 정렬 코드의 실행 시간이 일정하지 않은 이유는 무엇입니까?

저는 파이썬을 배우고 있으며 퀵 소트 알고리즘 (일종의)을 구현했습니다. 나는 파이썬의 sort() 메소드가 더 빠를 것이라고 알고 있지만, 얼마나 많은지 알고 싶었 기 때문에 비교를 위해 timeit 모듈을 사용했습니다.내 정렬 코드의 실행 시간이 일정하지 않은 이유는 무엇입니까?

sort() 메서드에 대한 래퍼 (wrapper) 함수를 만들어서 구현과 동일한 구문으로 작동하고 (내부 정렬이 중지됨) 두 함수 모두에 timeit.repeat(3, 2000)을 호출했습니다.

[0.00019502639770507812, 0.00037097930908203125, 0.00013303756713867188]

그리고 파이썬의 종류() :

[0.0001671314239501953, 0.0001678466796875, 0.00016808509826660156]

당신이 볼 수 있듯이

, 파이썬의 알고리즘은 훨씬 더 일관성있는 내 자신의 것보다 실행 시간을 가지고 여기에

내 기능에 대한 결과입니다. 아무도 이유를 아나요?

코드 :

import timeit 
import random 


def quick(lst): 
    if not lst: 
     return [] 
    else: 
     first, rest = lst[0], lst[1:] 
     great = [] 
     less = [] 
     for item in rest: 
      great.append(item) if item >= first else less.append(item) 
     return quick(less) + [first] + quick(great) 

def sort(lst): 
    lst.sort() 
    return lst 


x = [random.randint(1, 10000) for i in xrange(1, 1000)] 

quick_t = timeit.Timer("'quick(x)'") 

print quick_t.repeat(3, 2000) 

sort_t = timeit.Timer("'sort(x)'") 

print sort_t.repeat(3, 2000)

출처

2016-09-10 luizfelipe

는 "이 ...를 적절히 분류되고 중지 그래서 정렬() 메소드에 대한 '래퍼'기능을 만들어"- 어, 아니. [아니, 당신은하지 않았다.] (http://ideone.com/B7EnUX) 또한, 당신의 정렬이 빌트인 정렬과 경쟁 할 수있는 방법이 없다. – user2357112

첫 번째 정보를 보내 주셔서 감사합니다. 두 번째 부분은 ideone의 실제 출력입니다. 'timeit' 모듈을 잘못 사용하고 있습니까? '[0.0006148815155029297, 0.0005340576171875, 0.0004949569702148438]'' [0.0005309581756591797, 0.0005269050598144531, 0.0005059242248535156]' http://ideone.com/Glkc3T – luizfelipe

귀하의 타이밍은 여러 가지 방법으로 끔찍하게 잘못입니다. 먼저, sort 래퍼는 여전히 대신 새로운 목록을 반환하는 입력을 변이합니다 :

>>> x = [2, 1] 
>>> sort(x) 
[1, 2] 
>>> x 
[1, 2]

둘째, 당신은 두 종류의 모든 타이밍 아닙니다. 문자열 리터럴 'quick(x)' 또는 'sort(x)'의 평가를 타이밍하고 있습니다. 실제로는 정렬 작업이 수행되지 않습니다.

다음은 실제로 타이밍을 수행 할 거라고 방법은 다음과 같습니다

>>> x = [random.randint(1, 10000) for i in xrange(1, 1000)] 

>>> print timeit.repeat('quick(x)', 'from __main__ import quick, x', repeat=3, number=500) 
[1.1500223235169074, 1.0714474915748724, 1.0657452245240506] 
>>> print timeit.repeat('sorted(x)', 'from __main__ import quick, x', repeat=3, number=500) 
[0.0944752552401269, 0.10085532031979483, 0.09799135718691332]

출처

2016-09-10 23:41:20 user2357112

내 정렬 코드의 실행 시간이 일정하지 않은 이유는 무엇입니까?

답변

관련 문제