在 Java/Android 中高效过滤 ArrayList
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2139410/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficiently filter an ArrayList in Java/Android
提问by user141146
I'm developing an Android app (Android 1.6), but this is probably a more general Java question.
我正在开发一个 Android 应用程序（Android 1.6），但这可能是一个更一般的 Java 问题。
I have an ArrayList of about 10,000 objects
我有一个大约 10,000 个对象的 ArrayList
the objects contain 3 strings (firstName, middleName, lastName).
这些对象包含 3 个字符串（firstName、middleName、lastName）。
The user is presented with a "search box" on android where they can search for a particular "object" by typing in part of the name.
用户在 android 上会看到一个“搜索框”，他们可以在其中通过输入名称的一部分来搜索特定的“对象”。
I have a class (which I call Filterer) that searches through the list of 10,000 for matching objects and then returns them as a "sublist".
我有一个类（我称之为 Filterer），它在 10,000 个列表中搜索匹配的对象，然后将它们作为“子列表”返回。
The search is a little bit SLOW (especially on an Android handset) and I'm sure I'm not doing the search/filtering in the most efficient manner possible.
搜索有点慢（尤其是在 Android 手机上），我确定我没有以最有效的方式进行搜索/过滤。
Does anyone have any suggestions on how to speed up my search? My code is below. One possibility to to search against a secondary "masterList" that already has every piece of information in lowercase and concatenated…but there may be additional ways to improve this search that would also help.
有人对如何加快搜索速度有任何建议吗？我的代码如下。搜索辅助“主列表”的一种可能性，该辅助“主列表”已经包含小写和连接的每条信息……但可能还有其他方法可以改进此搜索，这也将有所帮助。
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);
}
}
}
采纳答案by Christopher Orr
Yes, it's certainly painful to lower-case several objects for each loop iteration (plus a possibly redundant toString?), and also bad practice to call list.size()for every iteration — that value should be cached before the loop starts.
是的，为每次循环迭代将几个对象小写肯定是痛苦的（加上可能是多余的toString？），而且list.size()每次迭代都调用也是不好的做法——应该在循环开始之前缓存该值。
Anyway, if you're working with this much data, is there a reason that you're not using an SQLite database for storage and displaying/filtering your list using CursorAdapter?
无论如何，如果您正在处理这么多数据，是否有理由不使用 SQLite 数据库来存储和显示/过滤您的列表CursorAdapter？
That would be the recommended way to implement something of this size.
这将是实现这种规模的东西的推荐方法。
回答by Arne Deutsch
Maybe you can trade some space for some speed? Create some form of an index for your data?
也许你可以用一些空间换取一些速度？为您的数据创建某种形式的索引？
For example:
例如：
- Create a list for each character (a-z) with all "MyObject"s where a part of the name contains the character (be aware of special characters!). For each entry count the number of "MyObject"s
- If a user type in an query, look for the individual characters and only search the list with the smallest amount of entries.
- 为每个字符 (az) 创建一个包含所有“MyObject”的列表，其中名称的一部分包含该字符（注意特殊字符！）。对于每个条目，计算“MyObject”的数量
- 如果用户键入查询，则查找单个字符并仅搜索条目数最少的列表。
Of course the addition of an name would require you to add it to the index.
当然，添加名称需要您将其添加到索引中。
回答by AGrunewald
After researching a bit more I have found that Suffix Arrayscould get you the fasted answers. Also have a look at the Wikipedia entry for Suffix Treesfor a bit more of an in depth explanation.
Besdies that I agree with the answer abovethat you could probably use an SQL Database for such queries. Doing an Sql Query against the data is probably one of the fastest ways to get what you want without suffix arrays.
One thing to speed things up a little without doing SQL would be to put firstName, middleName, lastName into one lowercase string, and put that into a new Map that is referencing the Array index. That way you can reduce search to just 10.000 strings of the hashmap without having to do a lowercase every time. It might be a bit faster but of course require more memory. Maybe try to do something with regular expressions to speed up the matching.
Another option would be to really create a searchindex with something like Luceneeven though I think that would be really overkill on an Android device but could work in plain Java and infix search in Lucene isn't super high performance either.
经过更多研究后，我发现后缀数组可以为您提供快速答案。另请查看后缀树的维基百科条目，以获得更深入的解释。
Besdies，我同意上面的答案，您可能可以使用 SQL 数据库进行此类查询。对数据执行 Sql 查询可能是在没有后缀数组的情况下获得所需内容的最快方法之一。
在不执行 SQL 的情况下加快速度的一件事是将 firstName、middleName、lastName 放入一个小写字符串中，然后将其放入引用 Array 索引的新 Map 中。这样您就可以将搜索减少到哈希映射的 10.000 个字符串，而不必每次都使用小写字母。它可能会快一点，但当然需要更多的内存。也许尝试用正则表达式做一些事情来加速匹配。
另一种选择是使用Lucene 之类的东西真正创建一个搜索索引，尽管我认为这在 Android 设备上真的有点矫枉过正，但可以在纯 Java 中工作，并且 Lucene 中的中缀搜索也不是超级高性能。
回答by Magesh Pandian
may be too late answer but it's help for other in stuck same problem.
答案可能为时已晚，但它对其他陷入相同问题的人有所帮助。
Java 8 (2014)solves this problem using streams and lambdas in one line of code:
Java 8 (2014)在一行代码中使用流和 lambda 来解决这个问题：
Using Stream Apiyou can filter data without for loop and more feature's are available.
使用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());
For more info see below link,
有关更多信息，请参阅以下链接，
回答by Civil Disobedient
How are you initially retrieving the 10,000+ list? If you're just using an instance of SQLite, I would really, stronglyrecommend you do this in SQL.
您最初如何检索 10,000+ 列表？如果您只是使用SQLite 的一个实例，我真的强烈建议您在 SQL 中执行此操作。
