qsort_bとqsort

Question

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

最初のものは当然のことながら、昔ながらの、どこでも見られます。しかしqsort_bは関数ではなくブロックをとります。私のコードは以下の通りです：

ここで私は大きな違いがあり、その違いを引き起こしています。私の理解では、ブロックは並列処理のためのものであり、この場合、関数より高速ではありません。並列処理には何もありません。

EDIT：heapsort_b（）、mergesort_b（）、およびqsort_b（）ルーチンは、_b接尾辞を持たない対応ルーチンと同じですが、比較コールバックは関数ポインタではなくブロックポインタであると考えられます。 （FROM BSD MAN PAGE）

EDIT：スピードの違い。 DATAが1000000の場合、qsortは146832 nsで終了し、qsort_bは127391 nsで終了します。それは約10％速いと考えると比較的大きな違いです。

EDIT：さらに大きな整数配列を作成できるようにコードを編集しました。私の個人的な最大のテスト結果は、28136278（28s）対23870078（24s）の100000000の整数です。それは私にとってかなり大きな違いです。

Answer 1

目的-C Blockは、異なる種類の動物です。 MACRO（コンパイル前の置換）、inline functions（コンパイラ"関数呼び出しのオーバーヘッドを排除するために最善を尽くす"）のように見えるかもしれませんが、全体の構造はこれらの構造よりはるかに異なります。

ブロックオブジェクト、さらに、スタックオブジェクトあります。スタック内に作成できるオブジェクト（少なくともトリックはありません）。

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

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

あなたの質問への答えとして

、qsort()とqsort_b()任意のアルゴリズムの違いはありませんが、精巧な構造、機能対ブロック。

Answer 2

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