java在LinkedHashSet上的迭代比在ArrayList上的迭代要快

Question

我想迭代2个集合，每个集合大约600条记录。我想将集合1中的每个元素与集合2中的所有其他元素进行比较。如果我选择我的集合作为LinkedHashSet，那么我必须对每个集合调用迭代器，并有两个while（内部和外部）循环。 对于ArrayList的选择，我将有两个for循环（内部和外部）从每个集合读取数据

我之所以选择LinkedHashSet，主要是因为我了解到LinkedHashSet的性能更好，我也更喜欢使用set来删除重复项，但在看到它运行得非常慢，大约需要2个小时才能完成后，我认为最好将集合复制到ArrayList中，然后在ArrayList上迭代，而不是在LinkedHashSet上。 我想知道哪一个会有更好的选择来加速运行时

公共阵列列表>；processDataSourcesV2（LinkedHashMap>；ppmsFinalResult，LinkedHashMap>；productDBFinalResult）{ //每个参数都是一个hashmap，其中包含键（id）和值（一组唯一参数） ArrayList>；结果=新阵列列表>；();

  Iterator<Entry<RecordId, LinkedHashSet<String>>> ppmsIterator = ppmsFinalResult.entrySet().iterator();
  Iterator<Entry<RecordId, LinkedHashSet<String>>> productIdIterator =null;
  //pair of id from each list
  ArrayList<Pair> listOfIdPair = new ArrayList<Pair>();
  while (ppmsIterator.hasNext()) {
      //RecordId object is an object containing the id and which list this id belongs to
      Entry<RecordId, LinkedHashSet<String>> currentPpmsPair = ppmsIterator.next();
      RecordId currentPpmsIDObj = currentPpmsPair.getKey(); 
      //set of unique string
      LinkedHashSet<String> currentPpmsCleanedTerms = (LinkedHashSet<String>)currentPpmsPair.getValue();
      productIdIterator = productDBFinalResult.entrySet().iterator();

      while (productIdIterator.hasNext()) {

          Entry<RecordId, LinkedHashSet<String>> currentProductDBPair = productIdIterator.next();
          RecordId currentProductIDObj = currentProductDBPair.getKey();
          LinkedHashSet<String> currentProductCleanedTerms = (LinkedHashSet<String>)currentProductDBPair.getValue();
          ArrayList<Object> listOfRowByRowProcess = new ArrayList <Object>();
          Pair currentIDPair = new Pair(currentPpmsIDObj.getIdValue(),currentProductIDObj.getIdValue());              
          //check for duplicates 
          if ((currentPpmsIDObj.getIdValue()).equals(currentProductIDObj.getIdValue()) || listOfIdPair.contains(currentIDPair.reverse()) ) {
              continue;
          }
          else {
              LinkedHashSet<String> commonTerms = getCommonTerms(currentPpmsCleanedTerms,currentProductCleanedTerms);
              listOfIdPair.add(currentIDPair.reverse());
              if (commonTerms.size()>0) {
                  listOfRowByRowProcess.add(currentPpmsIDObj);
                  listOfRowByRowProcess.add(currentProductIDObj);
                  listOfRowByRowProcess.add(commonTerms);

                  result.add(listOfRowByRowProcess); 
              }
          }

      }


  }

  return result;
}



 public LinkedHashSet<String> getCommonTerms(LinkedHashSet<String> setOne, LinkedHashSet<String> setTwo){
     Iterator<String> setOneIt = setOne.iterator();
     LinkedHashSet<String> setOfCommon = new LinkedHashSet<String>();
     //making hard copy
     while (setOneIt.hasNext()) {
         setOfCommon.add(setOneIt.next());
     }
     setOfCommon.retainAll(setTwo);
     return setOfCommon;
 }

Answer 1

数组在迭代时比任何其他结构都要快（所有元素都按顺序存储在内存中），另一方面，在删除和插入元素时速度较慢，因为它必须确保顺序存储。在链表上迭代速度较慢，因为您可能会遇到页面错误。。。所以选择哪一个取决于你

Answer 2

如果要查找两个集合中的元素，请将其中一个设为Set，并获取其与另一个集合的交集：

Collection<T> collection1, collection2; // given these

Set<T> intersection = new HashSet<T>(collection1);
intersection.retainAll(collection2);

这将在O（n）时间内执行，其中n是collection2的大小，因为在HashSet中查找元素的时间是恒定的

我猜你是在用collection2的每个元素检查collection1的每个元素，它的时间复杂度为O（n²）