algorithm - 堆排序在 MATLAB 上应该很慢吗？

Question

我在 MATLAB 中写了一个堆排序函数，它工作正常，除了当输入的长度大于或等于 1000 时，它可能需要很长时间(例如 1000 的长度需要半秒)。我不确定是不是 MATLAB 在堆排序算法上运行得不是很快，或者只是我的代码需要改进。我的代码如下所示:

function b = heapsort(a)

[~,n] = size(a);
b = zeros(1,n);
for i = 1:n
    a = build_max_heap(a);
    b(n+1-i) = a(1);

    temp = a(1);
    a(1) = a(n+1-i);
    a(n+1-i) = temp;

    a(n+1-i) = [];
    a = heapify(a,1);
end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function a = build_max_heap(a)
[~,n] = size(a);
m = floor(n/2);
for i = m:-1:1
    a = heapify(a,i);
end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function a = heapify(a,i)
[~,n] = size(a);

left = 2*i;
right = 2*i + 1;

if left <= n 
    if a(left) >= a(i)
        large = left;
    else
        large = i;
    end
else
    return
end
if right <= n
    if a(right) >= a(large)
        large = right;
    end
end

if large ~= i
    temp = a(large);
    a(large) = a(i);
    a(i) = temp;
    a = heapify(a,large);
end
end

我知道可能是代码 a(n+1-i) = []; 可能会消耗大量时间。但是，当我将 [] 更改为 -999(低于输入向量的任何数量)时，它并没有帮助，但甚至花费了更多 时间。

Answer 1

你应该使用 profiler检查哪些线路花费的时间最多。肯定是 a(n+1-i) = []; 减慢了您的功能。

在循环中调整数组大小非常慢，因此您应该始终尽量避免它。

一个简单的测试:

• 创建一个函数，将一个大向量作为输入，并迭代地删除元素，直到它为空。
• 创建一个函数，将相同的向量作为输入并迭代地将每个值设置为 0、Inf、NaN 或其他值。

使用timeit检查哪个功能更快。您会看到最后一个函数大约快 100 倍(当然取决于向量的大小)。

-999之所以花费更多的时间，很可能是因为a不再越来越小，因此a = heapify(a,1); 不会越来越快。我还没有测试过，但是如果你在你的第一个函数中尝试以下，你可能会得到一个更快的程序(你必须插入 n+1-i) 在你的代码的其他地方作为好吧，但我会把它留给你):

a(n+1-ii) = NaN;
a(1:n+1-ii) = heapify(a(1:n+1-ii),1);

请注意，我将 i 更改为 ii。这部分是因为我想给你一个好的建议，部分是为了避免被提醒到 not use i and j as variables in MATLAB .