在Java/Android中高效地过滤ArrayList

Question

我正在开发一个Android应用程序（Android 1.6），但这可能是一个更普遍的Java问题。

我有一个大约有10,000个对象的ArrayList

这些对象包含3个字符串（firstName，middleName，lastName）。

用户在Android上被呈现出一个“搜索框”，他们可以通过键入部分名称来搜索特定的“对象”。

我有一个类（我称之为Filterer），它搜索匹配的对象列表中的对象，然后将它们作为“子列表”返回。

搜索有点慢（尤其是在Android手机上），我相信我没有以最有效的方式进行搜索/过滤。

有人有什么建议可以加快我的搜索吗？我的代码如下。一种可能是针对已经将所有信息转换为小写和连接的次要“masterList”进行搜索...但可能还有其他改善此搜索的方法。

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

- user141146

---

请查看类似问题：https://dev59.com/E0vSa4cB1Zd3GeqPeGQR 它是以C++为主要考虑的，但通用解决方案（数据结构和算法）与编程语言无关。 - WildWezyr

Answer 1

是的，对于每次循环迭代小写几个对象（加上可能多余的toString）确实很痛苦，而且每次迭代调用list.size()也是不好的做法 - 在循环开始之前应该缓存该值。

无论如何，如果您正在处理这么多数据，那么为什么不使用SQLite数据库进行存储，并使用CursorAdapter来显示/过滤您的列表呢？

这将是实现此规模的推荐方法。

- Christopher Orr

---

SQLite（或其他SQL DBMS）是否真的有助于中缀搜索？它是否具有特殊类型的索引来支持此功能？ - WildWezyr

本地循环中的“size”变量是Java里一个老婆婆故事，就像声明方法为“final”一样。JVM会内联size()调用，你不会看到任何性能提升。 - Civil Disobedient

@不从命者：对于大多数JVM而言，这是正确的，但并不一定适用于Android设备上的Dalvik虚拟机。有关更多信息，请参阅http://developer.android.com/intl/fr/guide/practices/design/performance.html#cache_fields。 - Mark B

它的过滤功能对于Android联系人应用程序（或者是内容提供者？）来说工作得相当不错。这可能是一个好地方去看看。 - Christopher Orr

Answer 2

也许你可以为速度牺牲一些空间？为数据创建某种形式的索引？

例如：

1. 为每个字符（a-z）创建一个列表，其中包含所有名称中包含该字符部分的“MyObject”，注意特殊字符！对于每个条目，计算“MyObject”的数量。 2. 如果用户键入查询，请查找各个字符，并仅搜索条目最少的列表。

当然，添加名称需要将其添加到索引中。

- Arne Deutsch

Answer 3

也许回答有点晚，但这对于遇到同样问题的其他人会有所帮助。

Java 8 (2014)使用流和lambda在一行代码中解决了这个问题：

使用Stream Api，您可以在不使用for循环的情况下过滤数据，并且还有更多功能可用。

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

更多信息请参见下面的链接，

链接1 链接2

- Magesh Pandian

---

默认情况下，Stream API 可用于 24 及以上版本。 - Adil Soomro

Answer 4

经过更深入的研究，我发现后缀数组可以帮助您获得最快的答案。另外，请查看后缀树的维基百科条目，以获取更深入的解释。
除此之外，我同意上面的答案，您可能可以使用SQL数据库进行这些查询。针对数据的Sql查询可能是最快的方法之一，而无需使用后缀数组。
为了在不使用SQL的情况下加快速度，一个小技巧是将firstName、middleName和lastName组合成一个小写字符串，并将其放入新的Map中，引用数组索引。这样，您就可以将搜索范围减少到仅有10,000个哈希表字符串，而无需每次都进行小写操作。这可能会稍微更快一些，但需要更多的内存。也许可以尝试使用正则表达式来加快匹配速度。
另一种选择是真正创建一个类似Lucene的搜索索引，即使我认为这对Android设备来说有点过度kill了，但在纯Java和Lucene中执行中缀搜索效率也不是特别高。

- AGrunewald

---

SQLite（或其他SQL DBMS）真的可以帮助中缀搜索吗？它是否有特殊类型的索引来支持这个功能？据我所知，标准的SQL索引并不是为了快速实现中缀（包含）搜索而设计的。 - WildWezyr

使用正确的全文索引肯定不是最快的方法，但我相信在SQL Lite中查询要比搜索数组更快。 - AGrunewald

1. 据我所知，全文搜索解决方案（如Lucene等）并不是为了加速中缀搜索而设计的。如果您知道它们是如何做到的，请提供有关此内容的文章/文档章节链接。
2. 您的信仰基于什么？即使是SQL引擎也必须像遍历数组列表中的所有项一样遍历所有项（记录）。这是由于涉及中缀搜索，如果它是更简单的搜索类型（前缀搜索、精确值搜索等），使用索引将会对SQL产生严重的收益。

- WildWezyr

@WildWezyr：是的，中缀搜索总是时间上昂贵的，但Lucene支持它。http://wiki.apache.org/lucene-java/LuceneFAQ#What_wildcard_search_support_is_available_from_Lucene.3F 它不会像O(1)那样快，但至少比发布的Java代码更快。 同样，对于SQL来说也是如此，因为SQLite在Android上本地运行（C代码），我希望它比dalvik代码更快。 如果你真的想全力以赴，拥有最快的搜索速度，你需要选择类似后缀树或后缀数组这样的东西。请查看维基百科了解这些内容。 - AGrunewald

1. 您所引用的Lucene FAQ条目指出，Lucene仅仅支持中缀搜索，但默认情况下已关闭，因为它太昂贵了。结论：Lucene不是中缀搜索的好解决方案。
2. 本地C代码应该比Java代码更快-但这并不总是正确的，并且对于这种特定情况可能并不正确。也许值得尝试（修改代码以使用SQL数据库而不是ArrayList），但并不能确定它会在这里真正起到帮助作用。
3. 首先，我会尝试优化现有代码（例如，去掉小写等）。

- WildWezyr

Answer 5

你最初是如何检索10,000+的列表的？如果你只是使用SQLite的实例，我强烈建议你使用SQL来完成。

- Civil Disobedient

---

SQLite（或其他SQL DBMS）真的可以帮助进行中缀搜索吗？它是否有特殊的索引用于此？据我所知，标准的SQL索引并不是为快速进行中缀（包含）搜索而设计的。 - WildWezyr