Результаты итеративного и рекурсивного теста QuickSort должны выглядеть следующим образом? - PullRequest
Новая
       8

Результаты итеративного и рекурсивного теста QuickSort должны выглядеть следующим образом?

0 голосов
/ 01 февраля 2020

Я просто создаю бенчмарк для сравнения скорости двух реализаций быстрой сортировки. Итеративный и рекурсивный.

Я ожидал, что рекурсивный будет медленнее, но я получил этот график (синий - re c):

enter image description here

Возможно, что рекурсия быстрее? Может, я просто допустил ошибку в своем коде?

На всякий случай я делаю код на своем. 

    import time
import random
import sys


arrayList = []
arr = [random.randint(1,15000) for _ in range(1000)]

numbersList = [100000, 300000, 500000, 900000, 1000000, 1500000]
numbersForBenchmark = []
for i in range(len(numbersList)):
    arr = [random.randint(1,15000) for _ in range(numbersList[i])]
    numbersForBenchmark.append(arr)

print(numbersForBenchmark)
recursionTimeArray = []
iterationTimeArray = []


arrRe = arr
arrIt = arr



def partition(lst, start, end):
    pos = start

    for i in range(start, end):
        if lst[i] < lst[end]:             # in your version it always goes from 0
            lst[i],lst[pos] = lst[pos],lst[i]
            pos += 1

    lst[pos],lst[end] = lst[end],lst[pos] # you forgot to put the pivot
                                          # back in its place
    return pos

def quick_sort_recursive(lst, start, end):
    if start < end:                       # this is enough to end recursion
        pos = partition(lst, start, end)
        quick_sort_recursive(lst, start, pos - 1)
        quick_sort_recursive(lst, pos + 1, end)
        #print(lst)

def iter(arr,l,h):
    i = ( l - 1 )
    x = arr[h]

    for j in range(l , h):
        if   arr[j] <= x:

            # increment index of smaller element
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]

    arr[i+1],arr[h] = arr[h],arr[i+1]
    return (i+1)

def quickSortIterative(arr,l,h):
    size = h - l + 1
    stack = [0] * (size)

    top = -1

    top = top + 1
    stack[top] = l
    top = top + 1
    stack[top] = h

    while top >= 0:

        # Pop h and l
        h = stack[top]
        top = top - 1
        l = stack[top]
        top = top - 1

        p = iter( arr, l, h )

        if p-1 > l:
            top = top + 1
            stack[top] = l
            top = top + 1
            stack[top] = p - 1

        if p+1 < h:
            top = top + 1
            stack[top] = p + 1
            top = top + 1
            stack[top] = h


for i in range(len(numbersForBenchmark)):
    arrRe = numbersForBenchmark[i][:]
    arrIt = numbersForBenchmark[i][:]

    n = len(arrIt)
    start = time.time()
    quickSortIterative(arrIt, 0, n-1)
    end = time.time()
    ITime = end - start
    iterationTimeArray.append(ITime)


    try:
        n = len(arrRe)
        start = time.time()
        quick_sort_recursive(arrRe,0,n-1)
        end = time.time()
        rekTime = end - start
        recursionTimeArray.append(rekTime)
    except RecursionError as re:
        print('Sorry but this maze solver was not able to finish '
              'analyzing the maze: {}'.format(re.args[0]))


print("REK time", recursionTimeArray)
print("ITER TIME", iterationTimeArray)



# evenly sampled time at 200ms intervals
import matplotlib.pyplot as plt

plt.plot([10,100,500,1000,5000,8000 ], recursionTimeArray,[10,100,500,1000,5000,8000], iterationTimeArray)
plt.show()

Графики выглядят нормально, но я ожидал совершенно другого результата. Отсюда и мои сомнения по поводу результатов.

...