1

MATLAB でヒープ ソート関数を作成しましたが、正常に動作しますが、入力の長さが 1000 以上の場合、長い時間がかかる場合があります(たとえば、長さが 1000 の場合は 0.5 秒かかります)。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ず、さらに時間がかかりました。

4

1 に答える 1

4

を使用しprofilerて、最も時間がかかる行を確認する必要があります。それは間違いなくa(n+1-i) = [];あなたの機能を遅くしています。

ループ内の配列のサイズ変更は非常に遅いため、常に回避するようにしてください。

簡単なテスト:

  • 大きなベクトルを入力として取り、空になるまで要素を繰り返し削除する関数を作成します。
  • 同じベクトルを入力として受け取り、各値を0、Inf、NaNまたは別のものに繰り返し設定する関数を作成します。

timeitどちらの機能が速いかを確認するために使用します。最後の関数が約 100 倍高速であることがわかります (もちろん、ベクトルのサイズによって異なります)。

より多くの時間がかかる理由は、これ以上小さくならないため、ますます速くならない-999可能性が最も高いです。私はそれをテストしていませんが、最初の関数で次のことを試すと、おそらくはるかに高速なプログラムが得られるでしょう (コードに他の場所も挿入する必要がありますが、それはあなたに任せます):aa = 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。これは、部分的には良いアドバイスを提供したいからであり、部分的には MATLAB の変数として使用しないようiにj注意されるのを避けるためです。

于 2016-02-08T07:08:31.743 に答える