qsort_b 및 qsort

Question

Mac의 C++에서 다른 정렬 알고리즘을 보여주는 프로그램 작성. qsort와 qsort_b라는 두 가지 quicksort 구현을 발견했습니다.

첫 번째 것은 당연히 구식이며 모든 곳에서 볼 수 있습니다. 그러나 qsort_b가 있습니다. 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; 
} 

여기에는 큰 차이점이 있습니다. 그 차이점은 무엇입니까? 필자의 이해를 돕기 위해 블록은 병렬 처리를위한 것으로,이 경우 함수보다 빠르지는 않습니다. 평행 과정에는 아무 것도 없지, 그렇지?

EDIT : heapsort_b(), mergesort_b() 및 qsort_b() 루틴은 _b 접미사가없는 해당 루틴과 유사하므로 compar 콜백이 함수 포인터 대신 블록 포인터임을 기대합니다. (FROM BSD MAN PAGE)

편집 : 속도 차이. DATA가 1000000 인 경우 qsort는 qsort_b와 함께 146832 ns에서 127391 ns로 완료됩니다. 상대적으로 큰 차이점은 약 10 % 빨라진다는 점입니다.

편집 : 더 큰 정수 배열을 가질 수 있도록 코드를 편집했습니다. 개인적으로 가장 큰 테스트 결과는 28136278 (28 초) 대 23870078 (24 초)의 정수 100000000 개입니다. 나에게는 상당히 큰 차이가있다.

Answer 1

Objective-C Block은 다른 종류의 동물입니다. MACRO (컴파일하기 전에 대체) 및 inline functions (컴파일러에서 "함수 호출 오버 헤드를 제거하기 위해 최선을 다합니다")와 같을 수 있지만 전반적인 구조는 해당 구조와 훨씬 다릅니다.

블록 객체이고, 또한, 스택 객체. 적어도 일부 트릭없이 스택에서 만들 수있는 유일한 개체입니다.

스택에 Block 개체가 만들어지면 컴파일러는 모든 로컬 변수, 블록 변수, 참조하는 읽기/쓰기 변수의 주소 및 블록의 실행 코드에 대한 포인터를 추가합니다. 따라서 실행을 시작하기 전에 모든 스택 작업없이 모든 것이 계산을 위해 준비됩니다.

따라서 최적화 문제는 아니며 Block의 속성입니다. 의 함수 호출 오버 헤드가 없습니다. PUSH 및 POP 스택 변수입니다. 귀하의 질문에, qsort() 및 qsort_b() 어떤 알고리즘 차이가 없습니다에 대한 답변,하지만 정성 들여 구조, 기능 대 블록으로

.

Answer 2

나에게 최적화 차이가있는 것처럼 보입니다. qsort_b에서는 컴파일러가 비교를 인라인하는 반면 qsort에서는 그렇지 않습니다. 차이점은 비교 당 함수 호출의 오버 헤드입니다.