400x Sorting Speedup bởi Switching a.localeCompare (b) (a <b?-1:(a> b 1: 0))

Question

Bằng cách chuyển một chức năng sắp xếp javascript từ

myArray.sort(function (a, b) { 
    return a.name.localeCompare(b.name); 
}); 

để

myArray.sort(function (a, b) { 
    return (a.name < b.name ? -1 : (a.name > b.name ? 1 : 0)); 
}); 

tôi đã có thể để giảm thời gian sắp xếp mảng phần tử ~ 1700 trong Chrome từ 1993 mili giây đến 5 mili giây. Tốc độ tăng lên gần 400 lần. Thật không may, điều này là do chi phí phân loại chính xác các chuỗi không phải tiếng Anh.

Rõ ràng là tôi không thể chặn giao diện người dùng của mình trong 2 giây khi tôi cố gắng sắp xếp. Có bất cứ điều gì tôi có thể làm để tránh locale chậm khủng khiếpCompare nhưng vẫn duy trì hỗ trợ cho các chuỗi địa phương?

Answer 1

Rất khó để biết sắp xếp nhanh nhất mà không thấy dữ liệu bạn sắp xếp. Nhưng jsperf có rất nhiều bài kiểm tra tốt cho thấy sự khác biệt hiệu suất giữa các loại phân loại: http://jsperf.com/javascript-sort/45 http://jsperf.com/sort-algorithms/31

Tuy nhiên không ai trong số những tài khoản cho các chuỗi cục bộ, và tôi muốn tưởng tượng không có cách nào dễ dàng để sắp xếp chuỗi cục bộ và localeCompare là có lẽ là giải pháp tốt nhất cho việc này.

Nhìn vào tham chiếu mozilla là: "Khi so sánh số lượng lớn chuỗi, chẳng hạn như sắp xếp mảng lớn, tốt hơn là tạo đối tượng Intl.Collator và sử dụng hàm do thuộc tính so sánh của nó cung cấp." https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare

Nhưng đi đến Intl.Collator tham khảo nó cho thấy rằng không được hỗ trợ cho firefox/safari https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator

bạn có thể thử sử dụng một số các tùy chọn trên localCompare để tăng tốc độ hiệu suất. Nhưng tôi vừa thực hiện một thử nghiệm nhanh thay đổi mức độ nhạy cảm và nó có vẻ như nó sẽ không cải thiện hiệu suất:

list.sort(function(a, b) { 
    return a.localeCompare(b, {sensitivity:'base'}); 
}); 

http://jsperf.com/sort-locale-strings

Answer 2

Tôi không biết bạn vẫn đang tìm kiếm giải pháp cho vấn đề này

// Defaulted to ascending 
// 1 asc | -1 desc 
var direction = 1; 
myArray.sort(function (a, b) { 
    return a.name.localeCompare(b.name) === 1 ? direction : -1 * direction; 
}); 

tôi đã thêm một tấm séc === 1 mã của bạn và điều này được cải thiện về hiệu suất 400x đó có nghĩa là cả hai đều có số perf thể so sánh được.

số Perf với kích thước arr localeCompare: 3200 Avg thời gian mất trong 10 lần lặp lại: 60 ms

số Perf với> cách tiếp cận. Thời gian trung bình mất 55 ms

Answer 3

Phương pháp tiếp cận hiệu quả mà tôi tìm thấy khi giao dịch với/chủ yếu/ký tự latin là sử dụng toán tử bất cứ khi nào cả hai chuỗi khớp với một regex cụ thể. EG: /^[\w-.\s,]*$/

Sẽ nhanh hơn nếu cả hai chuỗi khớp với biểu thức và tệ nhất là có vẻ chậm hơn một chút so với ngôn ngữ gọi là localeCompare.

Ví dụ ở đây: http://jsperf.com/operator-vs-localecompage/11

Answer 4

Hãy thử sắp xếp nó theo 2 bước:

1. Với các nhà điều hành: như bạn nói, nó sẽ nhanh hơn
2. Sau đó, với localCompare() 400 lần: đây có bây giờ ít so sánh để làm vì mảng chủ yếu được sắp xếp.

Lưu ý: Tôi nghĩ rằng localCompare() chủ yếu sẽ được gọi với ít nhất 1 chuỗi không phải là tiếng Anh. Vì vậy, số lượng các cuộc gọi đến localCompare() với 2 chuỗi tiếng Anh nên được giảm đáng kể.

Đây là mã:

myArray.sort(function(a, b) { 
    return (a.name < b.name ? -1 : (a.name > b.name ? 1 : 0)); 
}); 

myArray.sort(function(a, b) { 
    return a.name.localeCompare(b.name); 
}); 

Giải pháp này có ưu điểm là ngắn và dễ sử dụng. Nó sẽ hiệu quả nếu mảng chứa hầu hết các chuỗi tiếng Anh. Bạn không có nhiều chuỗi tiếng Anh, loại đầu tiên sẽ ít hữu ích hơn. Nhưng vì nó rất dễ dàng để thêm vào các kịch bản của bạn, nó cũng dễ dàng để xem nếu phương pháp này là đáng giá.

Bây giờ nếu tôi là bạn, tôi cũng sẽ sử dụng một số Intl.Collator, vì nó được cho là nhanh hơn nhiều so với localCompare() khi bạn có nhiều so sánh để thực hiện.