5

Mac 上の C++ で異なる並べ替えアルゴリズムを示すプログラムを作成します。qsort と qsort_b という 2 つのクイックソートの実装が見つかりました。

最初のものはもちろん、昔ながらのどこにでもある qsort です。しかし、関数ではなくブロックを取る qsort_b があります。これが私のコードです：

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <ctime>

#define DATA 1000000

using namespace std;

int compare(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

int main(int argc, char *argv[])
{
    int* array = new int[DATA];

    srand(time(0));

    for ( int i = 0 ; i < DATA ; ++ i )
    {
        array[i] = rand() % 2147483647;
    }

    clock_t begin = clock();

    qsort(array, DATA, sizeof(array[0]), compare);
    //qsort_b(array, DATA, sizeof(array[0]), ^(const void* a, const void* b) { return *(int*)a - *(int*)b; });

    clock_t end = clock();

    cout << "Time it takes to sort " << DATA << " integers with quicksort: " << end - begin;
}

ここに大きな速度の違いが見られます。その違いの原因は何ですか。私の理解では、ブロックは並列処理用であり、この場合は関数よりも高速ではありません。並列処理するものは何もありませんね。

編集: heapsort_b()、mergesort_b()、および qsort_b() ルーチンは、_b サフィックスのない対応するルーチンに似ています。compar コールバックが関数ポインターではなくブロック ポインターであることを期待してください。( BSD MAN ページより)

編集：速度の違い。DATA が 1000000 の場合、qsort は 146832 ns、qsort_b は 127391 ns で終了しました。約 10% 高速であることを考えると、これは比較的大きな違いです。

編集:コードを編集して、さらに大きな整数配列を使用できるようにしました。私の個人的な最大のテスト結果は、100000000 整数、28136278 (28 秒) 対 23870078 (24 秒) です。私にとってはかなり大きな違いです。

4

2 に答える 2

4

Objective-CBlockは別の種類の動物です。MACRO(コンパイル前の置換) と inline functions(コンパイラーに「関数呼び出しのオーバーヘッドをなくすために最善を尽くせ」と伝える) のように見えるかもしれませんが、全体的な構造はそれらの構造とは大きく異なります。

ブロックはオブジェクトであり、さらにはスタックオブジェクトです。スタックで作成できる唯一のオブジェクト (少なくともいくつかのトリックなし)。

オブジェクトがスタックに作成されるBlockと、コンパイラは、すべてのローカル変数、ブロック変数、それが参照する読み取り/書き込み変数のアドレス、およびブロックの実行可能コードへのポインターを追加します。したがって、実行を開始する前であっても、スタック操作なしですべてが計算の準備ができています。

したがって、これは最適化の問題ではなく、 の属性ですBlock。スタック変数のPUSHおよびPOPの関数呼び出しオーバーヘッドはありません。

あなたの質問への答えとして、アルゴリズムの違いはqsort()ありqsort_b()ませんが、精巧な構造、block vs function .

于 2015-10-23T20:43:56.507 に答える
2

私には最適化の違いのように見えます。qsort_b を使用すると、コンパイラはおそらく比較をインライン化しますが、qsort ではインライン化しません。違いは、比較ごとの関数呼び出しのオーバーヘッドです。

于 2012-12-17T08:25:10.033 に答える