for循环代码需要提高性能

Question

我需要你的建议来改进下面的代码，因为它需要很多时间来执行method1和method2。当我执行RemoveFullyContains时，我正在调用method1和method2。我在这两种方法中都放了一个时间计数器，并且注意到执行这两种方法需要很多时间。可能有人可以给我一个指导来改善它。

public static List<VG> RemoveFullyContains(List<VG> lTree) { 
     for (int x = lTree.size()-1; x >= 0; x--) { 
      VG vg1 = lTree.get(x); 
      for (int y = lTree.size()-1; y >= 0; y--) { 
       if (y != x) { 
        VG vg2 = lTree.get(y); 
        if (method1(vg2.getAndVar(), vg1.getAndVar())) { 
         if (method2(vg1.getNotVar(), vg2.getNotVar())) { 
          lTree.remove(x); 
          break; 
         } 
        } 
       } 
      } 
     } 
     return lTree; 
    } 

    private boolean method1(List<String> searchList, List<String> mainList) { 
     if (searchList == null || searchList.size() == 0) { 
      return true; 
     } 
     if (mainList == null || mainList.size() == 0) { 
      return false; 
     } 
     if (searchList.size() > mainList.size()) { 
      return false; 
     } 
     for (String item : searchList) { 
      if (!mainList.contains(item)) { 
       return false; 
      } 
     } 
     return true; 
    } 

    private boolean method2(List<String> list1, List<String> list2) { 
     if ((list1 == null || list1.size() == 0) && (list2 == null || list2.size() == 0)) { 
      return true; 
     } 
     if ((list1 == null || list1.size() == 0) || (list2 == null || list2.size() == 0)) { 
      return false; 
     } 
     if (list1.size() != list2.size()) { 
      return false; 
     } 
     for (String item : list1) { 
      if (!list2.contains(item)) { 
       return false; 
      } 
     } 
     return true; 
    } 

VG is a class that has the following methods: hashcode, equal and clone 
public class VG { 
    private List<String> andVar = new ArrayList(); 
    private List<String> notVar = new ArrayList(); 
    private List<VG> orVar = new ArrayList(); 
    private VG parent; 
.... 
} 

Answer 1

如果List s永远不会为空，您可以删除空检查。当然，大部分时间将花费迭代Lists。

由于同样的List正在被重新使用，它会更快地使用Set给恒定时间查找。对于构建Set有一定的代价，但在下一次迭代中重复使用相同的Set会更快。

import java.util.ArrayList; 
import java.util.Collection; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 
import java.util.UUID; 

public class Method1 { 

    public static void main(String[] args) { 
     Method1 methods = new Method1(); 

     List<VG> vgs = new ArrayList<VG>(1000); 
     System.out.print("building VGs..."); 
     for (int i = 0; i < 1000; i++) { 
      vgs.add(methods.buildVg(i)); 
     } 
     System.out.println("complete."); 

     System.out.print("testing method1 using List..."); 
     long current = System.currentTimeMillis(); 
     for (int i = 0; i < vgs.size() - 2; i++) { 
      VG currentVG = vgs.get(i); 
      VG nextVG = vgs.get(i + 1); 
      methods.method1(currentVG.getAndVar(), currentVG.getAndVar()); 
      methods.method1(currentVG.getAndVar(), nextVG.getAndVar()); 
      methods.method1(nextVG.getAndVar(), currentVG.getAndVar()); 
      methods.method1(nextVG.getAndVar(), nextVG.getAndVar()); 
     } 
     System.out.println("completed in " + (System.currentTimeMillis() - current) + " ms"); 

     System.out.print("testing method1 using Set..."); 
     current = System.currentTimeMillis(); 
     for (int i = 0; i < vgs.size() - 2; i++) { 
      VG currentVG = vgs.get(i); 
      VG nextVG = vgs.get(i + 1); 
      methods.method1(currentVG.getAndVarAsSet(), currentVG.getAndVarAsSet()); 
      methods.method1(currentVG.getAndVarAsSet(), nextVG.getAndVarAsSet()); 
      methods.method1(nextVG.getAndVarAsSet(), currentVG.getAndVarAsSet()); 
      methods.method1(nextVG.getAndVarAsSet(), nextVG.getAndVarAsSet()); 
     } 
     System.out.println("completed in " + (System.currentTimeMillis() - current) + " ms."); 
    } 

    private VG buildVg(int i) { 
     VG vg = new VG(); 

     List<String> strings = new ArrayList<String>(6000); 
     for (int j = 0; j < 6000; j++) { 
      String s = UUID.randomUUID().toString(); 
      strings.add(i + s + j); 
     } 

     vg.setAndVar(strings); 
     return vg; 
    } 

    private boolean method1(Collection<String> searchList, Collection<String> mainList) { 
     if (searchList.size() == 0) { 
      return true; 
     } 
     if (mainList.size() == 0) { 
      return false; 
     } 
     if (searchList.size() > mainList.size()) { 
      return false; 
     } 

     for (String item : searchList) { 
      if (!mainList.contains(item)) { 
       return false; 
      } 
     } 
     return true; 
    } 

    private class VG { 
     private List<String> andVar = new ArrayList<String>(); 
     private Set<String> andVarSet; 

     public List<String> getAndVar() { 
      return andVar; 
     } 

     public void setAndVar(List<String> andVar) { 
      this.andVar = andVar; 
     } 

     public Set<String> getAndVarAsSet() { 
      if (andVarSet != null) { 
       return andVarSet; 
      } 

      andVarSet = new HashSet<String>(andVar.size()); 
      andVarSet.addAll(andVar); 
      return andVarSet; 
     } 
    } 
} 

输出：

building VGs...complete. 
testing method1 using List...completed in 140966 ms 
testing method1 using Set...completed in 1755 ms. 

如果您使用的是Java 8则流可能能够使它更快。