Trong tham chiếu đến fastest sort of fixed length 6 int array, tôi không hoàn toàn hiểu cách này sorting network đánh bại một thuật toán như insertion sort.Mạng phân loại đánh bại thuật toán phân loại chung như thế nào?
Mẫu câu hỏi đó, đây là một so sánh về số lượng CPU chu kỳ thực hiện để hoàn thành việc sắp xếp:
Linux 32 bit, gcc 4.4.1, Intel Core 2 Quad Q8300, -O2
- Insertion Sort (Daniel Stutzbach): 1425
- Networks Sorting (Daniel Stutzbach): 1080
Mã được sử dụng như sau:
Insertion Sort (Daniel Stutzbach)
static inline void sort6_insertion_sort_v2(int *d){
int i, j;
for (i = 1; i < 6; i++) {
int tmp = d[i];
for (j = i; j >= 1 && tmp < d[j-1]; j--)
d[j] = d[j-1];
d[j] = tmp;
}
}
Networks Sorting (Daniel Stutzbach)
static inline void sort6_sorting_network_v1(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
SWAP(1, 2);
SWAP(0, 2);
SWAP(0, 1);
SWAP(4, 5);
SWAP(3, 5);
SWAP(3, 4);
SWAP(0, 3);
SWAP(1, 4);
SWAP(2, 5);
SWAP(2, 4);
SWAP(1, 3);
SWAP(2, 3);
#undef SWAP
}
tôi understan d rằng các mạng phân loại thực sự tốt để phân loại song song, bởi vì một số bước độc lập với các bước khác. Nhưng ở đây chúng tôi không sử dụng song song.
Tôi hy vọng nó sẽ nhanh hơn, vì nó có lợi thế là biết chính xác số lượng các yếu tố trước đó. Vị trí và lý do chính xác việc chèn sắp xếp thực hiện các so sánh không cần thiết?
EDIT1:
Đây là đầu vào thiết lập các mã được so sánh với:
int d[6][6] = {\
{1, 2, 3, 4, 5, 6},\
{6, 5, 4, 3, 2, 1},\
{100, 2, 300, 4, 500, 6},\
{100, 2, 3, 4, 500, 6},\
{1, 200, 3, 4, 5, 600},\
{1, 1, 2, 1, 2, 1}\
};\
Thứ tự của mảng nhập liệu ngẫu nhiên ở đây? Hoặc bạn đang sử dụng một mảng giảm dần? –
@crypto: câu hỏi đã được cập nhật! – Lazer