qsort_b和qsort [英] qsort_b and qsort

问题描述

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

Writing a program that demonstrate different sorting algorithm in C++ on Mac. I found two quicksort implementation, qsort and qsort_b.

第一个当然是老式的，随处可见的qsort.但是有qsort_b，它接受一个块而不是一个函数.这是我的代码:

The first one is of course the old-fashioned, seen-everywhere qsort. But there's qsort_b, which takes an block rather than a function. Here's my code:

#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;
}

在这里，我看到速度差异很大，是什么造成了所有差异.据我了解，块是用于并行处理的，在这种情况下，它不会比函数更快.没有什么要并行处理的了吗?

Here I see big speed difference, what's causing all that difference. To my understanding, blocks is for parallel processing, which in this case won't be faster than functions. There's nothing to parallel process, is there?

heapsort_b()，mergesort_b()和qsort_b()例程就像没有_b后缀的相应例程一样，希望compar回调是块指针而不是函数指针. ( FROM BSD手册页)

The heapsort_b(), mergesort_b(), and qsort_b() routines are like the corresponding routines without the _b suffix, expect that the compar callback is a block pointer instead of a function pointer. (FROM BSD MAN PAGE)

速度差.在DATA为1000000的情况下，qsort在146832 ns中完成了操作，而qsort_b在127391 ns中完成了操作.考虑到它快10％左右，这是一个相对较大的差异.

The speed difference. With DATA being 1000000, qsort finished it in 146832 ns, with qsort_b, in 127391 ns. It's a relatively big difference considering it's about 10% faster.

我已经编辑了代码，以使更大的整数数组成为可能.我个人最大的测试结果是100000000个整数，即28136278(28s)和23870078(24s).对我来说是一个很大的不同.

I've edited the code to make it possible to have even bigger array of integers. My personal biggest test result are 100000000 integers, 28136278 (28s) vs. 23870078 (24s). It's a considerably big difference to me.

推荐答案

Objective-C Block是另一种动物.看起来像MACRO(编译前的替代)和inline functions(告诉编译器尽力消除函数调用的开销" )，但总体结构与这些结构有很大不同

Objective-C Block is a different kind of animal. It may seem like MACRO(substitution before compilation), and inline functions(telling compiler "Do your best to eliminate function call overhead"), but the overall structure is much more different than those structures.

块是对象，此外，是堆栈对象.唯一允许在堆栈中创建的对象(至少没有一些技巧).

Block is an object, furthermore, a stack object. The only object that is allowed to be created in the stack (at least without some tricks).

在堆栈中创建Block对象时，编译器将添加所有局部变量，块变量，其引用的读/写变量的地址以及指向块的可执行代码的指针.因此，即使在开始执行之前，一切都已准备就绪，无需任何堆栈操作即可进行计算.

When a Block object created in the stack, compiler adds all local variables, block variables, the addresses of read/write variables it references, and a pointer to block's executable code. So even before starting to execute, everything is ready for computation without any stack operation.

因此，这不是优化问题，而是Block的属性.它没有堆栈变量 PUSH 和 POP 的任何函数调用开销.

So, it is not an optimization issue, rather an attribute of the Block. It does not have any function call overhead of PUSH and POP s of stack variables.

作为对您问题的回答，qsort()和qsort_b()在算法上没有任何区别，但是详细的结构为 block vs function .

As an answer to your question, qsort() and qsort_b() does not have any algorithmic difference, but the elaborated structure, block vs function.

这篇关于qsort_b和qsort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！