Quichesort的好处

Question

我为一个赋值创建了这个程序,我们需要在它中创建一个Quichesort实现.这是一种混合排序算法,它使用Quicksort直到达到某个递归深度(log2(N),其中N是列表的长度),然后切换到Heapsort,以避免超过最大递归深度.

在测试我的实现时,我发现虽然它通常比常规Quicksort表现更好,但Heapsort一直表现优于两者.任何人都可以解释为什么Heapsort表现更好,在什么情况下Quichesort会比Quicksort 和 Heapsort 更好？

请注意,由于某种原因,赋值将算法称为"Quipsort".

编辑:很显然,"Quichesort"其实等同于 内省排序.

我还注意到我的medianOf3()函数中的逻辑错误导致它为某些输入返回错误的值.这是该功能的改进版本:

def medianOf3(lst):
    """
    From a lst of unordered data, find and return the the median value from
    the first, middle and last values.
    """

    first, last = lst[0], lst[-1]
    if len(lst) <= 2:
        return min(first, last)
    middle = lst[(len(lst) - 1) // 2]
    return sorted((first, middle, last))[1]

这会解释算法的性能相对较差吗？

Quichesort代码:

import heapSort             # heapSort
import math                 # log2 (for quicksort depth limit)

def medianOf3(lst):
    """
    From a lst of unordered data, find and return the the median value from
    the first, middle and last values.
    """

    first, last = lst[0], lst[-1]
    if len(lst) <= 2:
        return min(first, last)
    median = lst[len(lst) // 2]
    return max(min(first, median), min(median, last))

def partition(pivot, lst):
   """
   partition: pivot (element in lst) * List(lst) -> 
        tuple(List(less), List(same, List(more))).  
   Where:
        List(Less) has values less than the pivot
        List(same) has pivot value/s, and
        List(more) has values greater than the pivot

   e.g. partition(5, [11,4,7,2,5,9,3]) == [4,2,3], [5], [11,7,9]
   """

   less, same, more = [], [], []
   for val in lst:
      if val < pivot:
         less.append(val)
      elif val > pivot:
         more.append(val)
      else:
         same.append(val)
   return less, same, more

def quipSortRec(lst, limit):
    """
    A non in-place, depth limited quickSort, using median-of-3 pivot.
    Once the limit drops to 0, it uses heapSort instead.
    """

    if lst == []:
        return []

    if limit == 0:
        return heapSort.heapSort(lst)

    limit -= 1
    pivot = medianOf3(lst)
    less, same, more = partition(pivot, lst)
    return quipSortRec(less, limit) + same + quipSortRec(more, limit)

def quipSort(lst):
    """
    The main routine called to do the sort.  It should call the
    recursive routine with the correct values in order to perform
    the sort
    """

    depthLim = int(math.log2(len(lst)))
    return quipSortRec(lst, depthLim)

Heapsort代码:

import heapq    # mkHeap (for adding/removing from heap)

def heapSort(lst):
    """
    heapSort(List(Orderable)) -> List(Ordered)
        performs a heapsort on 'lst' returning a new sorted list
    Postcondition: the argument lst is not modified
    """

    heap = list(lst)
    heapq.heapify(heap)
    result = []
    while len(heap) > 0:
        result.append(heapq.heappop(heap))
    return result

Answer 1

基本事实如下：

• 堆排序具有最坏情况下的 O(n log(n)) 性能，但在实践中往往很慢。
• 快速排序的平均性能为 O(n log(n))，但在最坏情况下为 O(n^2)，但在实践中速度很快。
• Introsort旨在利用快速排序的快速实践性能，同时仍然保证堆排序的最坏情况 O(n log(n)) 行为。

要问的一个问题是，为什么快速排序“在实践中”比堆排序更快？ 这是一个很难回答的问题，但大多数答案都指出快速排序如何具有更好的空间局部性，从而减少缓存未命中。然而，我不确定这对 Python 有多适用，因为它在解释器中运行，并且比其他语言（例如 C）在幕后有更多的垃圾，可能会干扰缓存性能。

至于为什么你的特定 introsort 实现比 Python 的堆排序慢——同样，这很难确定。首先，请注意 heapq 模块是用 Python 编写的，因此它与您的实现处于相对平衡的基础上。创建和连接许多较小的列表可能成本很高，因此您可以尝试重写快速排序以就地执行操作，看看是否有帮助。您还可以尝试调整实现的各个方面，看看这对性能有何影响，或者通过分析器运行代码，看看是否存在任何热点。但最终我认为你不太可能找到明确的答案。它可能只是归结为 Python 解释器中哪些操作特别快或特别慢。