如何在列表中搜索元素？

Question

我有两个清单，例如:

列表1：只有一个元素

List<String> ids=new ArrayList<String>();

列表2:有1000个对象

List<ABC> abc=  new ArrayList<ABC>();

a.matIDS

注意：矩阵是字符串集合（例如：abc，定义，ghi）

for(ABC a : abc){
    for(String id : a.matIDs()){
        if(ids.contains(id)){
            LOG.info("ID found:::");
        }else{
            LOG.info("ID NOT found:::");
        }
    }
}

问题:

在列表1中只有1个元素，而在列表2中有1000个。我需要检查所有这1000个元素才能找到1个元素吗？

有没有更好的办法？

Answer 1

如果您确实需要针对另一个集合快速查找一个列表中的值（或多个值），那么最快的数据结构可能是针对一组进行搜索：

Set<String> set = new HashSet<>(abc);

然后，您可以迭代第一个列表并在另一个集合中以恒定时间查找每个条目：

for (String id : ids) {
    if (set.contains(id)) {
        LOG.info("ID found:::");
    }
    else {
        LOG.info("ID NOT found:::");
    }
}

这是对当前暴力破解方法的改进，该方法为 O（n*m），其中 n 和 m 是 id 和 abc 列表的大小。现在，运行时间只是O（m），即ids列表的大小。

Answer 2

如果你说的“更好”是指更清晰，那么也许你可以考虑使用streams:

abc.stream().flatMap(ABC::matIDs).anyMatch(ids::contains);

你是否认为这“更好”取决于你想要什么。

如果您定期检查某个ID是否在列表中，那么您可以收集一组ID:

Set<String> abcIDs = abc.stream().flatMap(ABC::matIDs).collect(toSet());

然后，检查某个特定字符串是否在集合中是很简单的，无需返回原始列表。

Answer 3

您可以优化现有代码以在找到匹配时退出循环。

booean isFound=false;
for(ABC a : abc){
    for(String id : a.matIDs()){
        if(ids.contains(id)){
            isFound=true;
            break;
        }
    }
    if(isFound)
        break;
}
if(isFound)
    LOG.info("ID found:::");
else
    LOG.info("ID NOT found:::");

您也可以使用流，

boolean isFound=abc.stream().flatMap(e-> e.matIDS.stream()).anyMatch(ids::contains);
if(isFound)
    LOG.info("ID found:::");
else
    LOG.info("ID NOT found:::");

要查找匹配的元素，您可以在集合中使用过滤和收集

  Set<String>  matchedElements=abc.stream()
                .flatMap(e-> e.matIDS.stream())
                .filter(ids::contains)
                .collect(Collectors.toSet());

希望能有所帮助。