Python如何解决基准测试countsort的最大值要求？

Question

我一直在尝试对一些不同的排序进行基准测试，并且已经解决了大部分问题，但计数排序被证明是尴尬的。 我在哪里给它一个最大的值？

我已经尝试了一些不同的方法，但是这个

def counting_sort(arr, maxval)。

n = len(arr)
m = maxval + 1
count = [0] * m               
for a in arr:
    count[a] += 1             
i = 0
for a in range(m):           
    for c in range(count[a]): # - emit 'count[a]' copies of 'a'
        arr[i] = a
        i += 1
return arr

给出了错误 TypeError: counting_sort() 缺少1个必要的位置参数: 'maxval' 。

所以我想我可以尝试一个不在开始时调用最大值的方法。

    arr = []
    for i in range(0, n, 1):
        arr.append(randint(0, 100))
    return arr

def counting_sort(arr):
    size = len(arr)
    output = [0] * size

    # Initialize count array
    count = [0] * 10

    # Store the count of each elements in count array
    for i in range(0, size):
        count[arr[i]] += 1

    # Store the cummulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Find the index of each element of the original array in count array
    # place the elements in output array
    i = size - 1
    while i >= 0:
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
        i -= 1

    # Copy the sorted elements into original array
    for i in range(0, size):
        arr[i] = output[i]

    return arr

num_runs = 10
elements = [100, 250, 500, 750, 1000, 1250, 2500, 3750, 5000]
def countrunTime():    

    stimes = []    
    for i in elements:
        arr = random_array(i)
        countresults = []
        for r in range(num_runs):

            start_time = time.time()

            counting_sort(arr)

            end_time = time.time()

            time_elapsed = end_time - start_time
            countresults.append(time_elapsed)
        s = round(mean(countresults),3)
        stimes.append(s)
    return stimes

Returns the error in counting_sort
    count[arr[i]] += 1
IndexError: list index out of range

Answer 1

如果你不给一个参数一个默认值，你就不能在不提供默认值的情况下调用该方法。

def counting_sort(arr, maxval):
    pass

counting_sort([])  # Will fail
counting_sort([], 123)  # Will work

我建议计算 maxval 来代替。

def counting_sort(arr):
    maxval = max(array)
    # ...

对于第二个错误，你试图访问一个大于count数组长度的索引。我想你会从使用 collections.Counter 来代替pythons的stdlib。

from collections import Counter
counter = Counter()
for value in arr:
   counter[value] += 1
print(counter)

collections.Counter 不需要为一个大小进行初始化，而且对于任何你没有改变的值，它都会报告0。

额外提示:你的很多代码都会从Pythons的列表理解中受益(入门指南). 相信我，它们真的值得我们努力学习。