Cách hiệu suất cao nhất để lọc danh sách các đối tượng JSON trong JavaScript là gì?

Question

Giả sử tôi có một (1000) danh sách rất lớn của các đối tượng như thế này:

[{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..] 

Tôi muốn lọc danh sách này bằng tên (nhân vật khôn ngoan).

filter('j') => [{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..] 

filter('jo') => [{name: 'john dow', age: 38, gender:'m'}, ..] 

filter('dow') => [{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..] 

Cách hiệu suất cao nhất để làm điều đó là gì? RegEx rõ ràng là một trong các khóa, sắp xếp danh sách trước nếu bạn cho rằng người dùng thường có xu hướng bắt đầu tên từ đầu cũng có thể là một ý tưởng hay, nhưng nó chỉ giúp trong một số trường hợp.

Có bất kỳ hàm JavaScript tích hợp nào để ánh xạ bộ lọc không? Tôi hy vọng những thứ đó sẽ nhanh hơn việc triển khai JavaScript.

P.S .: Có, tôi muốn lọc ở phía máy khách vì "khả năng ngoại tuyến" mà tôi muốn cung cấp.

Answer 1

Mặc dù một substring index (chẳng hạn như một Suffix tree) sẽ thực hiện điều này nhanh hơn, việc tìm kiếm trực tiếp sẽ là:

function (s, l) { 
    return l.filter(function (v) { 
     return v.name.find(s) !== -1; 
    }); 
} 

nơi s là chuỗi truy vấn và l là danh sách các đối tượng.

Answer 2

Từ kinh nghiệm, các thuật toán sau đây hoạt động khá tốt:

1. Khi người dùng nhập chữ cái đầu tiên, bạn thực hiện một tìm kiếm bằng Array.filter() lẽ và cửa hàng mà kết quả dưới bất cứ loại người sử dụng (ví dụ: "j");

2. Khi người dùng nhập một lá thư khác (ví dụ: "o"), bạn thực hiện tìm kiếm trên bất cứ điều gì đã gõ trước đó ("j"), giảm số lượng các mặt hàng phải đi qua

3. Khi xóa sử dụng một hoặc nhiều ký tự bạn cố gắng tìm các tìm kiếm được lưu trữ dựa trên bất kỳ thứ gì còn lại trong hộp tìm kiếm; nếu tất cả không thành công, bạn sẽ hiển thị một danh sách trống và vô hiệu hóa các tìm kiếm được lưu trữ trước đó.

Answer 3

Tôi sẽ không lo lắng quá nhiều về hiệu suất trong trường hợp này. Một máy tính để bàn nên ăn 1000, hoặc 10.000 đánh giá mà không có mồ hôi. Tôi sẽ tránh bất kỳ loại tối ưu hóa phức tạp nào vì nguy cơ phá vỡ chức năng có thể cao hơn lợi ích của việc xử lý hiệu quả một chút.

Javascript (ECMAScript 5) cung cấp các phương pháp mới để lọc mảng. Là một phương pháp bản địa, nó được cho là nhanh hơn một chút.

var regex = ... 

results = json.filter(function(result) { 
    return regex.test(result.name) 
} 

Array.prototype.filter được hỗ trợ trong trình duyệt hiện đại, xem http://kangax.github.com/es5-compat-table/. Có thể thêm bản vá cho các trình duyệt cũ hơn với điều này: https://github.com/kriskowal/es5-shim