2个List的比较优化问题
有两个list——list1和list2.每个list的大小为95000。现在要求出2个list中相同的数据，哪种方法时间最快？我现在有3个方案。
方案1：2层for循环进行比较，比较并写库的时间一共为42分钟。
方案2：用map保存list1记录，然后查看list2中的每条数据是否在list1中，比较并写库的时间一共为32分钟，比方案1快了10分钟。
方案3：使用list1.retainAll(list2)，未进行测试。
哪位达人还有更好的优化方案。。。 大小都一样,一次循环就可以了, 1,2方法都不必考虑了 这跟你一开始把数据load到什么样的结构中有关，比如array, arraylist, linkedlist, map，，都会有不同的考虑。
如果是基于Arraylist, 只能考虑怎么在compare的过程中，动态减少第二个list的大小（比如overwrite一下contains方法来实现），来减少整体的比较次数。最少也得nlogn吧 我只用过方案1 感觉你的性能瓶颈可能是在对象比较和入库这两个地方。
/**
* Cost 220 second.
*
* @param list1
* @param list2
* @return
*/
public static Collection<Integer> alg1(List<Integer> list1, List<Integer> list2) {
Set<Integer> equSet = new HashSet<Integer>();
for (int i = 0; i < list1.size(); i++) {
Integer int1 = list1.get(i);
for (int j = 0; j < list2.size(); j++) {
if (int1.equals(list2.get(j))) {
equSet.add(int1);
}
}
}
return equSet;
}
/**
* Cost 98 second.
*
* @param list1
* @param list2
* @return
*/
public static Collection<Integer> alg2(List<Integer> list1, List<Integer> list2) {
List<Integer> listEqu = new ArrayList<Integer>(list1);
listEqu.retainAll(list2);
return listEqu;
}
/**
* Cost 0.047 second.
*
* @param list1
* @param list2
* @return
*/
public static Collection<Integer> alg3(List<Integer> list1, List<Integer> list2) {
Set<Integer> equSet = new HashSet<Integer>();
Set<Integer> tmpSet = new HashSet<Integer>();
for (Integer i : list1) {
tmpSet.add(i);
}
for (Integer i : list2) {
if (tmpSet.contains(i)) {
equSet.add(i);
}
}
return equSet;
}
美女真历害 回复 6# surpass_li
他是雌雄同体 回复surpass_li
他是雌雄同体
tong0245 发表于 2010-11-01 10:24 http://bbs.chinaunix.net/images/common/back.gif
:oo 回复 2# eye_onme
你说的方案是行不通的。 回复 9# renxiao2003
两个单向链表我都从第一个node开始遍历, 如List-A , List-B,顺序的把每个元素都放到HashMap 1中, 如果已经存在相同的元素,则写入到HashMap 2中,2中就是重复的元素
页:
[1]
2