实现的排序算法性能差

Question

我实现了一些排序算法，包括插入、选择、Shell、合并两种。我发现我的工具的性能不符合算法的描述（第四）。 例如，这里有两种合并排序。当对一个包含100000个元素的列表进行排序时，Merge1大约需要0.6秒，Merge2大约需要50+s。但是Merge2几乎与算法（第4个）中的一样，只是我使用python。我不明白为什么Merge2这么慢，以及如何改进它。有人能帮我吗？谢谢！你知道吗

class Merge1:
    def merge(self, a, b):
        i = 0; j = 0
        res = []
        while i < len(a) and j < len(b):
            if a[i] < b[j]:
                res.append(a[i])
                i = i + 1
            else:
                res.append(b[j])
                j = j + 1
        res = res + a[i:] +  b[j:]
        return res

    def sort(self, source):
        if len(source) <= 1:
            return source
        half = len(source) // 2
        left = self.sort(source[:half])
        right = self.sort(source[half:])
        retval = self.merge(left, right)
        return retval

    def is_sort(self, source):
        length = len(source)
        for i in range(0, length-1):
            if source[i] > source[i+1]:
                return False
        return True

class Merge2:
    def merge(self, source, lo, mid ,hi):
        i = lo
        j = mid + 1
        aux = source[:]
        k = lo
        while k <= hi:
            if i > mid:
                source[k] = aux[j]
                j = j + 1
            elif j > hi:
                source[k] = aux[i]
                i = i + 1
            elif aux[i] < aux[j]:
                source[k] = aux[i]
                i = i + 1
            else:
                source[k] = aux[j]
                j = j + 1
            k = k+1

    def sort(self, source):
        sz = 1
        N = len(source)
        while sz < N:
            for lo in range(0, N-sz, sz+sz):
                # pdb.set_trace()
                self.merge(source, lo, lo+sz-1, min(lo+sz+sz-1, N-1))
            sz = sz + sz

    def is_sort(self, source):
        length = len(source)
        for i in range(0, length-1):
            if source[i] > source[i+1]:
                return False
        return True

以下是算法实现：

测试代码如下：

    merge1 = Merge1()
    source = np.random.randint(100000, size=100000).tolist()
    start = time.time()
    merge1.sort(source)
    end = time.time()
    print("Merge1 takes: {}s".format(end-start))


    merge2 = Merge2()
    source = np.random.randint(100000, size=100000).tolist()
    start = time.time()
    merge2.sort(source)
    end = time.time()
    print("Merge2 takes: {}s".format(end-start))

结果： E:>；Python排序.py 合并1取0.6376256942749023s 合并2：57.99568271636963s

Answer 1

考虑一下这个修改。根据我的快速测试，它大大提高了性能（从近一分钟下降到不到1秒）。主要的性能增益来自于避免创建整个列表的那么多副本。其他改动只会略微提高性能。 根据一个简单的总和比较，它不应该弄乱列表，但你应该做一些更多的测试，如果你喜欢使用它。你知道吗

class Merge4:
    def merge(self, source, aux, lo, mid ,hi):
        i = lo
        j = mid + 1
        a_j= aux[j]
        a_i= aux[i]
        k = lo
        while k <= hi:
            if i > mid:
                source[k] = a_j
                j += 1
                a_j= aux[j]
            elif j > hi:
                source[k] = a_i
                i += 1
                a_i= aux[i]
            elif a_i < a_j:
                source[k] = a_i
                i += 1
                a_i= aux[i]
            else:
                source[k] = a_j
                j += 1
                a_j= aux[j]
            k += 1
        # update the aux array for the next call
        aux[lo:hi+1]= source[lo:hi+1]

    def sort(self, source):
        sz = 1
        N = len(source)
        while sz < N:
            sz_2= sz * 2
            # create the aux array, that will be maintained continuously
            # and add one extra None, so the "prefetching" works also
            # during the last iteration (refering to a_i and a_j)
            aux= source[:]
            aux.append(None)
            for lo in range(0, N-sz, sz_2):
                # pdb.set_trace()
                self.merge(source, aux, lo, lo+sz-1, min(lo+sz_2-1, N-1))
            sz = sz_2

    def is_sort(self, source):
        length = len(source)
        for i in range(0, length-1):
            if source[i] > source[i+1]:
                return False
        return True