2

CLRS の第 2 章には、挿入ソートの最悪の場合の実行時間を に改善するかどうかを尋ねる演習がありますO(n lg n)。この質問を見て、それができないことがわかりました。

最悪の場合の複雑さを改善することはできませんがmemmove、実際の実行時間を使用することで、配列要素を個別に移動するよりも優れているでしょうか?

要素を個別に移動するためのコード

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
            arr[k + 1] = arr[k];
        }
        arr[k + 1] = temp;
    }
}

を使用して要素を移動するためのコード memmove

void insertion_sort(int arr[], int length)
{
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
                ;
        }
        if (k != j - 1){
            memmove(&arr[k + 2], &arr[k + 1], sizeof(int) *(j - k - 2));
        }
        arr[k + 1] = temp;
    }
}

2番目のものを完全に実行することはできませんでしたが、それは私が考えていることの例です。

を使用することで目に見える速度の向上はありますmemmoveか?

4

4 に答える 4

2

それはすべて、コンパイラとその他の実装の詳細に依存します。memmoveいくつかのトリッキーな超最適化された方法で実装できるのは事実です。しかし同時に、スマート コンパイラは、要素ごとのコピー コードが何を行っているかを把握し、同じ (または非常に類似した) 方法で最適化できる可能性があります。試してみて、自分の目で確かめてください。

于 2013-07-09T16:00:40.333 に答える
0

C 実装で memcpy に勝るものはありません。それはasmで書かれており、優れたアルゴリズムを使用しているためです。

特定の CPU を念頭に置いて asm コードを記述し、キャッシュを考慮した優れたアルゴリズムを開発すると、チャンスがあるかもしれません。

標準ライブラリ関数は非常によく最適化されているため、常に使用することをお勧めします。

于 2013-08-20T18:31:53.583 に答える