Viết chương trình thể hiện thuật toán sắp xếp khác nhau trong C++ trên Mac. Tôi tìm thấy hai triển khai quicksort, qsort và qsort_b.qsort_b và qsort
Điều đầu tiên tất nhiên là qsort cũ, được xem ở mọi nơi. Nhưng có qsort_b, một khối thay vì một hàm. Đây là mã của tôi:
#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;
}
Ở đây tôi thấy sự khác biệt về tốc độ lớn, điều gì gây ra sự khác biệt đó. Theo hiểu biết của tôi, các khối là để xử lý song song, trong trường hợp này sẽ không nhanh hơn các hàm. Không có gì để xử lý song song, phải không? EDIT: Các thói quen heapsort_b(), mergesort_b(), và qsort_b() giống như các thói quen tương ứng không có hậu tố _b, hy vọng rằng hàm gọi lại so sánh là một con trỏ khối thay vì một con trỏ hàm. (FROM BSD MAN PAGE)
EDIT: Chênh lệch tốc độ. Với DATA là 1000000, qsort đã hoàn thành nó trong 146832 ns, với qsort_b, trong 127391 ns. Đó là một sự khác biệt khá lớn so với việc nó nhanh hơn khoảng 10%.
EDIT: Tôi đã chỉnh sửa mã để làm cho nó có thể có mảng lớn hơn các số nguyên. Kết quả thử nghiệm lớn nhất cá nhân của tôi là 100000000 số nguyên, 28136278 (28) so với 23870078 (24 giây). Đó là một sự khác biệt lớn đáng kể đối với tôi.
bạn có thể giải thích thêm về "chênh lệch tốc độ lớn" –
@KarthikT Tôi không chắc chắn với đơn vị đo lường, nhưng tôi nghĩ rằng đó là nano giây. Với qsort, nó là 146832, với qsort_b, nó là 127391. Với DATA là 1000000. –
Tôi đã thử nghiệm nó với dữ liệu lớn hơn bao giờ hết, 100000000 số nguyên. Đó là 28136278 (28) so với 23870078 (24 giây). Đó là một sự khác biệt lớn đáng kể đối với tôi. –