Эффективно фильтровать ArrayList в Java / Android

Question

Я занимаюсь разработкой приложения для Android (Android 1.6), но, возможно, это более общий вопрос Java.

У меня ArrayList около 10000 объектов

объекты содержат 3 строки (firstName, middleName, lastName).

Пользователю предоставляется «окно поиска» на Android, где он может искать определенный «объект», введя часть имени.

У меня есть класс (который я называю Filterer), который ищет в списке 10000 подходящих объектов, а затем возвращает их как «подсписок».

Поиск немного медленный (особенно на телефоне Android), и я уверен, что не буду выполнять поиск / фильтрацию самым эффективным способом.

У кого-нибудь есть предложения по ускорению моего поиска? Мой код ниже. Одна возможность поиска по вторичному «masterList», в котором уже есть все фрагменты информации в нижнем регистре и объединены ... но могут быть и другие способы улучшить этот поиск, что также поможет.

ТИА !!

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

Да, конечно, больно писать несколько объектов в нижнем регистре для каждой итерации цикла (плюс, возможно, избыточный toString?), А также плохой способ вызывать list.size() для каждой итерации & mdash; это значение должно быть кэшировано до начала цикла.

В любом случае, если вы работаете с таким большим количеством данных, есть ли причина, по которой вы не используете базу данных SQLite для хранения и отображения / фильтрации своего списка, используя CursorAdapter?

Это был бы рекомендуемый способ реализовать что-то такого размера.

Answer 2

Может быть, вы можете обменять некоторое пространство на некоторую скорость? Создать какую-либо форму индекса для ваших данных?

Например:

1. Создайте список для каждого символа (a-z) со всеми «MyObject», где часть имени содержит символ (помните о специальных символах!). Для каждой записи подсчитайте количество «MyObject» s
2. Если пользователь вводит запрос, ищите отдельные символы и ищите только список с наименьшим количеством записей.

Конечно, для добавления имени потребуется добавить его в индекс.

Answer 3

может быть слишком поздно, но это поможет другим в застрявшей той же проблеме.

Java 8 (2014) решает эту проблему, используя потоки и лямбды в одной строке кода:

Используя Stream Api , вы можете фильтровать данные без цикла и доступны дополнительные функции.

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());

Для получения дополнительной информации см. Ссылку ниже,

Link1 Link2

Answer 4

Как вы изначально получаете список 10000+? Если вы просто используете экземпляр SQLite , я бы действительно настоятельно рекомендовал бы вам сделать это в SQL.

Answer 5

Изучив немного больше, я обнаружил, что Суффиксные массивы могут дать вам быстрые ответы. Также взгляните на запись в Википедии для Деревьев суффиксов для более подробного объяснения.
Я согласен с ответом выше , что вы, вероятно, могли бы использовать базу данных SQL для таких запросов. Выполнение Sql-запроса к данным, вероятно, является одним из самых быстрых способов получить то, что вам нужно, без массивов суффиксов.
Одна вещь, чтобы немного ускорить процесс без использования SQL, - это поместить firstName, middleName, lastName в одну строчную строку и поместить это в новую Map, которая ссылается на индекс Array. Таким образом, вы можете сократить поиск до 10.000 строк хэш-карты без необходимости каждый раз вводить строчные буквы. Это может быть немного быстрее, но, конечно, потребуется больше памяти. Возможно, попробуйте что-нибудь сделать с помощью регулярных выражений, чтобы ускорить сопоставление.
Другим вариантом может быть создание поискового индекса с чем-то вроде Lucene , хотя я думаю, что это было бы излишним на Android-устройстве, но могло бы работать на простом Java, и поиск в инфиксах в Lucene тоже не слишком высок .