Плохая производительность реализованных алгоритмов сортировки

Question

Я реализовал несколько алгоритмов сортировки, включая вставку, выделение, оболочку, два вида слияния.Я обнаружил, что производительность моих инструментов не соответствует описанию Алгоритмов (4-е).Например, вот два вида сортировки слиянием.Когда сортировка списка содержит 100 000 элементов, Merge1 занимает около 0,6 с, а Merge2 - около 50 с.Но 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 sort.py Merge1 принимает: 0,6376256942749023s Merge2 принимает: 57,9956871636963s

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