我有一个自定义类列表，我想在其中通过名称或编号搜索一些项目，而不使用任何for循环，因为它有大约100000个项目
class Contact{
String name;
String phone;
}
但是使用循环进行迭代需要很长时间才能完成，有什么有效的方法可以做到这一点吗？？
public static void main(String[] args){
String textToSearch = "name"; //or it can be number also
List<Contact> list = new ArrayList<>();
list.addAll(myOldListOfCustomContacts);
for(Contact contact : list){
if(contact.name.toLowerCase().contains(textToSearch) || contact.phone.toLowerCase().contains(textToSearch)){
Log.e("TAG", "found");
}
}
}
在提出这个问题之前，我在StackOverFlow上搜索了它，但没有得到答案，就像下面这样查看ArrayList是否包含Java中对象的最有效方法
这并不容易，因为您正在联系人姓名或电话号码中的某个位置搜索子字符串。你需要一种能迅速将一百万候选人减少到可管理数量的东西。
如果你找不到一个库在做你想做的事情，你可以去做三角图索引。让我们解释一下联系人姓名的想法(那么电话号码只是同一索引的第二个化身)。
创建一个以trigraph为键、以多个Contacts为值的HashMap<String,List<Contact>>(那些以trigraph作为其名称子串的联系人)。因此，对于每个联系人名称中的每三个字符的子字符串(trigraph)，将此Contact添加到trigraph键下的列表中。
当您使用给定的子字符串搜索Contact时，取搜索字符串的前三个字符，然后从地图中读取列表。这种查找将很快，并为您提供一百万个原始元素中的一个子集。然后依次检查在该子集中找到的Contacts是否包含完整的搜索字符串。
除了主过程之外，您可能还需要支持角大小写，如名称或短于三个字符的搜索字符串。根据典型的搜索字符串，可能更智能地选择搜索三角图会比只取前三个字母得到更好的结果，例如所有搜索字符串三角图的结果的交集。
此解决方案使用索引列表来帮助您使用Collections.binarySearch().
/**
* Adds indexing on a list of type C given a field accessor that can extract a field of type T from a C.
*
* Please ensure your list is `RandomAccess`.
*/
class Index<C, T extends Comparable<T>>
extends AbstractList<T> implements List<T>, RandomAccess {
// The actual list.
final List<C> actual;
// My sorted index to the list.
final List<Integer> index;
// The getter to get a T from a C
final Function<C, T> getter;
public Index(List<C> actual, Function<C, T> getField) {
this.actual = actual;
getter = getField;
// Start the index mapping i -> i
index = IntStream.rangeClosed(0, actual.size() - 1).boxed().collect(Collectors.toList());
// Sort it on the actual.
Collections.sort(index, (o1, o2) -> get(o1).compareTo(get(o2)));
}
@Override
public T get(int index) {
// Translate all access through the index.
return getter.apply(actual.get(this.index.get(index)));
}
@Override
public int size() {
return index.size();
}
// Finds all occurrences of thing.
public List<C> find(T thing) {
// Is it there at all?
int where = Collections.binarySearch(this, thing);
if (where >= 0) {
// Step back to ensure we aren't in the middle of a run.
while (where > 0 && get(where - 1).equals(thing)) {
where -= 1;
}
// Gather the list.
List<C> found = new ArrayList<>();
while (where < index.size() && get(where).equals(thing)) {
found.add(actual.get(index.get(where++)));
}
return found;
} else {
return Collections.EMPTY_LIST;
}
}
}
// For demo.
class Contact {
final String name;
final String phone;
public Contact(String name, String phone) {
this.name = name;
this.phone = phone;
}
public String getName() {
return name;
}
public String getPhone() {
return phone;
}
@Override
public String toString() {
return "Contact{" +
"name='" + name + ''' +
", phone='" + phone + ''' +
'}';
}
}
private void test(String[] args) {
// Sample list.
List<Contact> list = new ArrayList<>();
list.add(new Contact("Me", "1234"));
list.add(new Contact("You", "5678"));
list.add(new Contact("Us", "6666"));
list.add(new Contact("Many", "6666"));
list.add(new Contact("Them", "9999"));
list.add(new Contact("Them", "99999"));
list.add(new Contact("Them", "999999"));
// Build sorted indexes by name and phone.
Index<Contact, String> byName = new Index<>(list, Contact::getName);
Index<Contact, String> byPhone = new Index<>(list, Contact::getPhone);
// Use binary search to find a name and a phone.
int me = Collections.binarySearch(byName, "Me");
System.out.println(me + " -> " + list.get(me));
int six = Collections.binarySearch(byPhone, "6666");
System.out.println(six + " -> " + list.get(six));
System.out.println("Them -> " + byName.find("Them"));
System.out.println("6666 -> " + byPhone.find("6666"));
}
1)您可以按姓名或电话对列表进行排序，之后搜索会更容易(二进制搜索等)
2) 若你们只有唯一的联系人，你们可以在找到结果时打破循环。
3) 如果您有多个姓名或电话相同的联系人，请尝试对列表进行排序。并添加一个分区，就像所有按a、B、C等名称命名的联系人一样。
4) 如果你像"a"一样搜索，在那之后是"an"，在"ana"之后。您可以使用子列表。类似：
1步骤：找到所有与"a"的联系人并使用其结果。
2步骤：将不从完整列表中搜索，您将从步骤1的结果中搜索。
3步骤：从步骤2的结果中搜索。
电话号码也是如此。
您可以使用旧Java的ThreadPoolExecutor。
在开始之前，我建议阅读其他答案和评论，其中指出了一些有用的数据结构，这些数据结构应该可以在不需要多线程实用程序的情况下改进搜索功能。
正如@Xenolion所提到的，如果您从数据库加载联系人，请考虑直接查询，而不阻塞UI线程。
如果使用ThreadPoolExecutor，则基本上将Array划分为更小的块，每个块将由Thread处理。
你可以在安卓文档中找到一个详尽的例子。
您需要实现一个Runnable类，该类将为您的数据分配一个分区。
class Worker implements Runnable {
// ...
public Worker(final Contact[] data, final int start, final int end) {
// have your workers hold a reference to the data array
this.data = data;
// ...
}
@Override public void run() {
for (int i = this.start, i < this.end; i++) {
if (this.data[i].contains(....) || ...) {
this.notifySearchEnded(i);
break;
}
}
// found nothing...
}
private void notifySearchEnded(final int index) {
// do whatever you want with the contact
log("Runnable " + this.id + " has found the contact at index " + index);
// hold somehow a reference to the executor
EXECUTOR.shutdown(); // tell the executor to stop the other threads
}
}
然后，您将实例化ExecutorService并执行Worker Threads。
private static final int CORES = Runtime.getRuntime().availableProcessors();
public static final ExecutorService EXECUTOR = Executors.newFixedThreadPool(CORES);
将数组拆分为更小的块。
final int dataSize = data.lenght; // let's say 76'513
final int step = (int) (dataSize / CORES); // 76'513 / 4 = 19128
for (int i = 0; i < CORES; i++) {
final int start = i * step;
// give the left-over data to the last thread
final int end = (i == (CORES - 1)) ? (dataSize - 1) : (start + step - 1);
EXECUTOR.execute(new Worker(this.data, start, end));
}
不过，我的例子不是很有效上面提到的Android链接包含一个更好的例子，它使用了线程的动态数量和执行器的超时。以我的例子为基础，按照文档进行优化。
更多的例子，这里和(与期货)，这里和这里：