Lọc một ArrayList hiệu quả trong Java/Android

Question

Tôi đang phát triển một ứng dụng Android (Android 1.6), nhưng đây có lẽ là một câu hỏi Java tổng quát hơn.

Tôi có một ArrayList khoảng 10.000 đối tượng

đối tượng chứa 3 chuỗi (firstName, middleName, lastName).

Người dùng được hiển thị với "hộp tìm kiếm" trên Android nơi họ có thể tìm kiếm "đối tượng" cụ thể bằng cách nhập một phần tên.

Tôi có một lớp (mà tôi gọi là Bộ lọc) tìm kiếm trong danh sách 10.000 đối tượng phù hợp và sau đó trả về chúng dưới dạng "danh sách phụ".

Tìm kiếm là một chút SLOW (đặc biệt là trên điện thoại Android) và tôi chắc chắn tôi không thực hiện tìm kiếm/lọc theo cách hiệu quả nhất có thể.

Có ai có bất kỳ đề xuất nào về cách tăng tốc độ tìm kiếm của tôi không? Mã của tôi là dưới đây. Một khả năng để tìm kiếm dựa trên "masterList" phụ đã có mọi thông tin trong chữ thường và ghép nối ... nhưng có thể có thêm các cách để cải thiện tìm kiếm này cũng có thể hữu ích.

TIA !!

public void filterNames() { 
    this.filteredList.clear(); 
    String sv = this.searchString.toString.trim().toLowerCase(); // search value 
    for (int i = 0; i < this.masterList.size(); i++) { 
    MyObject d = this.masterList.get(i); 
    String fn = d.getFirstName().toString().toLowerCase(); 
    String mn = d.getMiddleName().toString().toLowerCase(); 
    String ln = d.getLastName().toString().toLowerCase(); 

    if (fn.indexOf(sv) >= 0 || 
     md.indexOf(sv) >= 0 || 
     ln.indexOf(sv) >= 0) { 
     this.currentList.add(d); 
    } 
    } 
} 

Answer 1

Vâng, nó chắc chắn đau đớn to-chữ thường một số đối tượng cho mỗi lần lặp (cộng với một khả năng dư thừa toString?), Và cũng có thể thực hành xấu để gọi list.size() cho mỗi lần lặp — rằng giá trị nên được lưu trữ trước khi vòng lặp bắt đầu.

Dù sao, nếu bạn đang làm việc với nhiều dữ liệu này, có lý do nào bạn không sử dụng cơ sở dữ liệu SQLite để lưu trữ và hiển thị/lọc danh sách của mình bằng cách sử dụng CursorAdapter không?

Đó sẽ là cách được khuyến nghị để triển khai thứ gì đó có kích thước này.

Answer 2

Có thể bạn có thể giao dịch một số không gian cho một số tốc độ? Tạo một số biểu mẫu của chỉ mục cho dữ liệu của bạn?

Ví dụ:

1. Tạo một danh sách cho mỗi ký tự (a-z) với tất cả các "MyObject" là nơi một phần của tên chứa ký tự (được nhận thức của các nhân vật đặc biệt!). Đối với mỗi mục nhập, hãy đếm số "MyObject" s
2. Nếu người dùng nhập truy vấn, hãy tìm các ký tự riêng lẻ và chỉ tìm kiếm danh sách có số lượng mục nhập nhỏ nhất.

Tất nhiên việc thêm tên sẽ yêu cầu bạn thêm nó vào chỉ mục.

Answer 3

Sau khi nghiên cứu thêm một chút, tôi đã nhận thấy rằng Suffix Arrays có thể giúp bạn có được câu trả lời nhanh chóng. Ngoài ra, hãy xem mục nhập Wikipedia cho Suffix Trees để biết thêm một chút về giải thích chi tiết.
Bên cạnh đó tôi đồng ý với answer above rằng bạn có thể sử dụng Cơ sở dữ liệu SQL cho các truy vấn như vậy. Làm một truy vấn Sql chống lại dữ liệu có lẽ là một trong những cách nhanh nhất để có được những gì bạn muốn mà không có mảng hậu tố.
Một điều để tăng tốc mọi thứ lên một chút mà không cần làm SQL sẽ đặt firstName, middleName, lastName vào một chuỗi ký tự chữ thường và đặt nó vào một Bản đồ mới có tham chiếu đến chỉ mục Mảng. Bằng cách đó bạn có thể giảm tìm kiếm chỉ còn 10.000 chuỗi hashmap mà không cần phải viết thường xuyên mỗi lần. Nó có thể nhanh hơn một chút nhưng tất nhiên đòi hỏi nhiều bộ nhớ hơn. Có thể cố gắng làm điều gì đó với các biểu thức thông thường để tăng tốc độ khớp.
Một tùy chọn khác sẽ thực sự tạo một searchindex với một cái gì đó như Lucene mặc dù tôi nghĩ rằng nó sẽ thực sự quá mức trên một thiết bị Android nhưng có thể làm việc trong Java đơn giản và tìm kiếm infix trong Lucene không phải là siêu hiệu suất cao hoặc.

Answer 4

Ban đầu bạn sẽ truy xuất danh sách 10.000+ như thế nào? Nếu bạn chỉ sử dụng instance of SQLite, tôi thực sự, mạnh mẽ khuyên bạn nên làm điều này trong SQL.

Answer 5

có thể là câu trả lời quá muộn nhưng đó là trợ giúp cho người khác trong vấn đề tương tự bị mắc kẹt.

Java 8 (2014) giải quyết vấn đề này bằng con suối và lambdas trong một dòng mã:

Sử dụng Stream Api bạn có thể lọc dữ liệu mà không cho vòng lặp và tính năng hơn của có sẵn.

List<MyObject> mFilteredMyObjectList = mMyObjectList.stream() 
    .filter(d -> d.getFirstName().toString().toLowerCase().indexOf(sv) >= 0 
    || d.getMiddleName().toString().toLowerCase().indexOf(sv) >= 0 
    || d.getLastName().toString().toLowerCase().indexOf(sv) >= 0).collect(Collectors.toList()); 

Để biết thêm thông xem dưới đây liên kết,

Link1 Link2