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

Mặc dù chỉ mục chuỗi con (chẳng hạn như cây Hậu tố ) sẽ làm cho việc này nhanh hơn, nhưng tìm kiếm trực tiếp sẽ là:

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

đâu slà chuỗi truy vấn và llà danh sách các đối tượng.

Theo kinh nghiệm, thuật toán sau hoạt động khá tốt:

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

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

3. Khi người dùng xóa 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ả đều không thành công, bạn sẽ hiển thị một danh sách trống và làm mất hiệu lực của các tìm kiếm đã lưu trữ trước đó.

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 có thể ăn tới 1000 hoặc 10.000 lượt đánh giá mà không cần đổ 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 gốc, 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 các 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: https://github.com/kriskowal/es5-shim

20000 mục ngẫu nhiên (xem bộ lọc bản ghi 20k với thời gian trong thời gian thực)

let dictionary = [];
  var time=0;
  var answer = [];

  var possible = "abcdefghijklmnopqrstuvwxyz";
  function makeid(len) {
    var text = "";


    for (var i = 0; i < len; i++)
      text += possible.charAt(Math.floor(Math.random() * possible.length));

    return text;
  }

  function addWord(number){
    for (var inc=0; inc<number; inc++){
      var wl = 5+Math.floor(Math.random() * 5);
      dictionary.push({word:makeid(wl)});
    }
  }

  function findWord(start){
    return dictionary.filter(function(e){
      return e.word.startsWith(start);
    })
  }


  $(document).ready(function( $ ) {

    addWord(20000);
    $("#time").text( 'Search from ' + dictionary.length + ' random items!' );

    $("#search-input").keyup(function() {
      var term = $(this).val() || '';
      

      if( term ) {

        var init = new Date().getTime();
        var sol = findWord( term );
        time= (new Date()).getTime() - init;
        
        console.log( term );
        $("#answer").text(JSON.stringify(sol));
        $("#time").text( sol.length + ' items found in time ' + time + 'ms' );
      } else {
        $("#answer").text(JSON.stringify(dictionary));
        $("#time").text( 'Search from ' + dictionary.length + ' items' );
      }

    });
  });

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<input id="search-input" placeholder="Search..">
<p id="time"></p>
<p id="answer"></p>

https://jsfiddle.net/maheshwaghmare/cfx3p40v/3/

Từ đơn giản đến phức tạp hơn (không có thêm lib):

1. Giới hạn tìm kiếm cho các ký tự x tối thiểu (thường là 3 được chấp nhận)
2. Trì hoãn việc lọc trong khi người dùng đang nhập bằng cách sử dụng thời gian chờ:

//clear previous timed filtering
if (typingTimeout) {
      clearTimeout(typingTimeout);
      typingTimeout = null;
    }
//schedule new filtering
typingTimeout = setTimeout(() => {
   // do some filtering
}, 2000); //acceptable 1-2s

3. Nếu bạn vẫn muốn lọc nhanh hơn, Bạn có thể nhóm danh sách của mình theo thứ tự bảng chữ cái trong một đối tượng:

{
   A: ['Aron', 'Arnold', ...],
   B: ['Baby'],
   ....
}

Sau đó, lọc chúng bằng cách sử dụng danh sách có tiền tố với ký tự đầu tiên được nhập. Nó chỉ là một ví dụ, bạn nên nhóm dữ liệu của bạn khi bạn thấy phù hợp (có thể là 2 chữ cái đầu tiên ...).

Đây là một hàm mà tôi đã triển khai để giúp tạo tiền tố cho mảng của tôi:

export function prefixStringsArray(arr, prefixLength) {
  const prefixArr = arr.map((s) => s.substr(0, prefixLength));
  const filter = (item, query) =>
    item.toLowerCase().startsWith(query.toLowerCase());

  const prefixObj = {};
  for (const pre of prefixArr) {
    prefixObj[pre] = arr.filter((item) => filter(item, pre));
  }

  return prefixObj;
}

Bạn nên biết rằng sử dụng đối tượng JS là một lựa chọn rất tốt vì chúng được truy cập trong O (1) (nó là một loại bản đồ băm) và nếu bạn nhóm dữ liệu của mình một cách tối ưu, bạn sẽ nhận được các mảng nhỏ để lọc.

Ghi chú:

1. Nếu bạn chọn đặt tiền tố cho mảng của mình, bạn nên để ý người dùng đang tìm kiếm query.length < prefixLength
2. Điều này đã mang lại cho tôi kết quả tuyệt vời trong việc phát triển thiết bị di động (React native)
3. Mã chỉ là bản nháp - được kiểm tra thủ công