5

在 Mac 上用 C++ 编写一个演示不同排序算法的程序。我找到了两个快速排序实现，qsort 和 qsort_b。

第一个当然是老式的、随处可见的 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 后缀的相应例程一样，期望比较回调是块指针而不是函数指针。（来自 BSD 手册页）

编辑：速度差异。DATA 为 1000000，qsort 在 146832 ns 内完成，qsort_b 在 127391 ns 内完成。考虑到它快 10% 左右，这是一个相对较大的差异。

编辑：我已经编辑了代码，使其可以拥有更大的整数数组。我个人最大的测试结果是 100000000 个整数，28136278 (28s) vs. 23870078 (24s)。这对我来说是一个相当大的不同。

4

2 回答 2

4

Objective-CBlock是另一种动物。它可能看起来像MACRO（编译前的替换）和 inline functions（告诉编译器“尽最大努力消除函数调用开销”），但整体结构与这些结构有很大不同。

Block 是一个对象，此外，一个堆栈对象。唯一允许在堆栈中创建的对象（至少没有一些技巧）。

当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 回答