Triển khai thuật toán nhanh để sắp xếp danh sách rất nhỏ

Question

Đây là vấn đề tôi đã gặp phải trong thời gian dài trước đây. Tôi nghĩ tôi có thể hỏi ý kiến ​​của bạn. giả sử tôi có một danh sách rất nhỏ các số (số nguyên), 4 hoặc 8 phần tử, cần được sắp xếp, nhanh chóng. phương pháp tiếp cận/thuật toán tốt nhất là gì?

cách tiếp cận của tôi là sử dụng các hàm tối đa/phút (10 hàm để sắp xếp 4 số, không có nhánh, iirc).

// s(i,j) == max(i,j), min(i,j) 
i,j = s(i,j) 
k,l = s(k,l) 
i,k = s(i,k) // i on top 
j,l = s(j,l) // l on bottom 
j,k = s(j,k) 

Tôi đoán câu hỏi của tôi liên quan nhiều hơn đến việc triển khai, thay vì loại thuật toán.

Tại thời điểm này, nó sẽ trở thành phần cứng phụ thuộc, vì vậy chúng ta hãy giả sử bộ xử lý Intel 64 bit với SSE3.

Cảm ơn

Answer 1

Đối với các mảng nhỏ như thế này, có thể bạn nên xem xét sorting networks. Như bạn có thể thấy trên trang đó, sắp xếp chèn có thể được biểu diễn dưới dạng một mạng phân loại. Tuy nhiên, nếu bạn biết kích thước của mảng trước, bạn có thể tạo ra một mạng tối ưu. Hãy xem this site có thể giúp bạn tìm mạng phân loại tối ưu cho một kích thước nhất định của mảng (mặc dù tối ưu chỉ được đảm bảo lên đến kích thước 16 tôi tin). Các bộ so sánh thậm chí được nhóm lại với nhau trong các phép toán có thể được thực hiện song song. Các so sánh về cơ bản giống như hàm s (x, y) của bạn mặc dù nếu bạn thực sự muốn nó nhanh, bạn không nên dùng min và max bởi vì sau đó bạn đang làm gấp đôi số so sánh cần thiết.

Nếu bạn cần thuật toán phân loại này hoạt động trên nhiều kích thước, thì có thể bạn chỉ cần đi với sắp xếp chèn như những người khác đã đề xuất.

Answer 2

Để có tập dữ liệu nhỏ như vậy, bạn muốn đơn giản hóa thuật toán càng tốt. Nhiều khả năng là không, một Insertion Sort cơ bản sẽ hoạt động tốt như bạn muốn.

Cần biết thêm về hệ thống đang chạy, số lần bạn cần thực hiện việc này một giây, v.v ... nhưng quy tắc chung trong các loại nhỏ là giữ cho nó đơn giản. Quicksort và những thứ tương tự không có lợi.

Answer 3

Loại chèn được coi là tốt nhất cho các mảng nhỏ. Xem Fast stable sort for small arrays (under 32 or 64 elements)

Answer 4

Tôi thấy bạn đã có một giải pháp sử dụng 5 so sánh (giả sử rằng s (i, j) so sánh hai số một lần và hoán đổi chúng hay không). Nếu bạn dính vào phân loại dựa trên so sánh, thì bạn không thể thực hiện việc đó với bất kỳ ít hơn 5 so sánh.

Điều này có thể được chứng minh vì có 4! = 24 cách có thể để đặt 4 số. Mỗi so sánh chỉ có thể cắt giảm khả năng phân nửa, vì vậy với 4 so sánh, bạn chỉ có thể phân biệt giữa 2^4 = 16 thứ tự có thể.

Answer 5

Để sắp xếp một số lượng nhỏ các số bạn muốn một thuật toán đơn giản vì độ phức tạp sẽ tăng thêm chi phí.

Cách hiệu quả nhất để sắp xếp ví dụ bốn mục sẽ được làm sáng tỏ những thuật toán sắp xếp để so sánh tuyến tính, do đó elliminating tất cả các chi phí:

function sort(i,j,k,l) { 
    if (i < j) { 
    if (j < k) { 
     if (k < l) return [i,j,k,l]; 
     if (j < l) return [i,j,l,k]; 
     if (i < l) return [i,l,j,k]; 
     return [l,i,j,k]; 
    } else if (i < k) { 
     if (j < l) return [i,k,j,l]; 
     if (k < l) return [i,k,l,j]; 
     if (i < l) return [i,l,k,j]; 
     return [l,i,k,j]; 
    } else { 
     if (j < l) return [k,i,j,l]; 
     if (i < l) return [k,i,l,j]; 
     if (k < l) return [k,l,i,j]; 
     return [l,k,i,j]; 
    } 
    } else { 
    if (i < k) { 
     if (k < l) return [j,i,k,l]; 
     if (i < l) return [j,i,l,k]; 
     if (j < l) return [j,l,i,k]; 
     return [l,j,i,k]; 
    } else if (j < k) { 
     if (i < l) return [j,k,i,l]; 
     if (k < l) return [j,k,l,i]; 
     if (j < l) return [j,l,k,i]; 
     return [l,j,k,i]; 
    } else { 
     if (i < l) return [k,j,i,l]; 
     if (j < l) return [k,j,l,i]; 
     if (k < l) return [k,l,j,i]; 
     return [l,k,j,i]; 
    } 
    } 
} 

Tuy nhiên, mã mọc rất nhiều cho từng hạng mục thêm bạn thêm . Việc thêm một mục thứ năm làm cho mã này lớn gấp bốn lần.Tại tám mục, nó sẽ có khoảng 30000 dòng, vì vậy mặc dù nó vẫn là hiệu quả nhất, đó là rất nhiều mã, và bạn sẽ phải viết một chương trình viết mã để làm cho nó chính xác.

Answer 6

Các mạng phân loại có thể dễ dàng được triển khai trong SIMD, mặc dù nó bắt đầu trở nên xấu ở khoảng N = 16. Đối với N = 4 hoặc N = 8 mặc dù đây sẽ là một lựa chọn tốt. Lý tưởng nhất là bạn cần rất nhiều tập dữ liệu nhỏ để sắp xếp đồng thời, tức là nếu bạn sắp xếp giá trị 8 bit thì bạn muốn có ít nhất 16 tập dữ liệu để sắp xếp - khó thực hiện loại điều này trên vectơ SIMD.

Xem thêm: Fastest sort of fixed length 6 int array