0

我需要执行以下任务：

  • 我有一个物品清单。
  • 每个项目还有一个列表，其中包含“ gkejgueieriug”之类的字符串
  • 现在我需要运行 throw the list 并检查每个项目的列表中有多少项目也在当前元素中

这是一个小伪代码：

OneItem;
List AllItems;
for Item in AllItems:
    int count = number strings in Item.Values which are also in OneItem.Values

因为数据非常大，我需要一些帮助来进行有效的实施。

这该怎么做？我应该使用哈希图吗？如何计算重叠？

4

4 回答 4

1

您的问题没有提供有关您要比较的所涉及类型的详细信息。所以我假设你有一个List<Item>. 每个项目都有一个String和一个自己的List<Item>

所以首先我会在你的HashSet-List中String创建一个。迭代并将每个字符串添加到. 然后在第二步中再次迭代并在s 中迭代并在此处检查每个 String 是否在之前创建的 HashSet 中。ItemsAllItemsAllListItemHashSetAllListListItem

如果您必须多次检查这一点，您可以将 HashSet 保留为缓存，在AllList更改时刷新它。

// Step 1: Create Set of Strings
Set<String> allStrings = new HashSet<String>();
for (Item item : allList) {
   allStrings.add(item.getString());
}

// Step 2: Calculate occurrences
for (Item item : allList) {
   for (Item internalItem : item.getItems()) {
       if (allStrings.contains(internalItem.getString()) {
           // Count one up for this String
           // This might be done by replacing the HashSet by a HashMap and use its values for counting
       }
   }
}
于 2013-05-24T09:05:09.547 回答
0

将 Item.Values 设为 Set 而不是 List。一个像样的 Set 实现——如 HashSet——将在恒定时间内运行 contains() 操作。然后迭代一个集合并在每次另一个集合包含元素时增加一个计数。

优化是始终迭代较小的集合。这样计数操作是 O(n)，其中 n 是较小集合的大小。

于 2013-05-24T09:00:36.887 回答
0

如果比较只是一种方式（即只计算一个列表中的字符串，这些字符串也在另一个列表中，但不是相反），那么最好的方法可能是将两个列表放在一个 Set 中：

HashSet firstSet = ...
HashSet secondSet = ...

for(each value in firstSet)
{
    if(secondSet.contains(value)
    {
        // Do what you want with the value.
        // Sugestion: Add value to a separate set
        // so you can track duplicates etc
    }
}
于 2013-05-24T09:03:44.177 回答
0

使用此代码，您可以使用字符串值和 OneItem.Values 中的匹配数创建一个ArrayListof ...Map

ArrayList<Map<String,Integer>> matches=new ArrayList<>();
for (Item i : AllItems) {
      Map<String,Integer> map=new HashMap<>();
      for(String s:values){
        map.put(s,Collections.frequency(OneItem.Values, s));
      }
      matches.add(map); 
}
于 2013-05-24T09:10:37.143 回答