数据量大的list循环遍历的问题

Question

list1和list2分别是从数据库中查询得到的数据，比对list1中的值在list2中有那些是存在的，那些是不存在的。两个list循环遍历，但是两个list中都有几万条数据，这样的话比对次数就list1.size（）*list2.size（）次。所以速度慢到不行。有什么好的解决办法？现在已经做了，比对上的，不再比对，速度还是不行。list中存的都是对象，而且我只比较每个对象的一个属性的相似度。比对完成后返回完全一致的，80%以上，没有比对上的。

Answer 1

比对list1中的值在list2中有那些是存在的?
1、取出list1中不重复的值，保存到list3；
2、取出list2中不重复的值，保存到list4；
3、循环取出list3到list4对比，要list3*list4次数。

Answer 2

如果可以还是取去之前就在sql里做的好

Answer 3

我也知道数据库中效率高，但是很难，因为我需要比对的字段是字符串（中文的），需要把字符串拆分成一个一个的汉字，而且是顺序的。代码上面已经没问题。list1和list2中没有重复值。主要循环次数太多了。

Answer 4

将list2中的数据排序，放入list3中
再遍历list1，取其值a与list3的 取整(list3.length/2)对应的值进行比较，如果a大，这与大于中间值的部分的中间值进行比较，依次类推，可以大大的减少比较次数，不过不知道是不是容易实现，lz可以参考一下

Answer 5

list1排序为list3
list2排序为list4
然后可以使用合并两个有序序列的算法那样
时间复杂度：mlgm+nlgn+(m+n) 比m*n小好多

Answer 6

可能是我说的不是很清楚，因为我同时需要没有比对上，比对上的，80%以上比对上的。这些还是需要返回为list。在页面分别显示。

Answer 7

我想了一下，可以在list1遍历的时候将list1.get(i)运用like在数据库中查询得到list2，此时的list2将会非常的小，
但是这样数据库可能就受不了，查询数据库也要几万次。

Answer 8

将list2中的数据排序，放入list3中 
再遍历list1，取其值a与list3的 取整(list3.length/2)对应的值进行比较，如果a大，这与大于中间值的部分的中间值进行比较，依次类推，可以大大的减少比较次数，不过不知道是不是容易实现，lz可以参考一下list1排序为list3 
list2排序为list4 
然后可以使用合并两个有序序列的算法那样 
时间复杂度：mlgm+nlgn+(m+n) 比m*n小好多以上想法都很好，建议楼主。用用算法
这个设计到算法问题。

Answer 9

第一，我的比较值a是中文的，没有办法比大。
第二，list1排序为list3 
list2排序为list4 
然后可以使用合并两个有序序列的算法那样 
时间复杂度：mlgm+nlgn+(m+n) 比m*n小好多 
我查出的list1和list2已经是排序过的，“但是合并两个有序序列的算法那样”具体怎样。

Answer 10

import java.util.*;public class LinkedListTest {
    public static void main(String[] args) {
        
        List datelist = new LinkedList();//list1
        for(int d = 1;d < 5; d++){
            Date date = new Date();
            date.setId(d);
            date.setValue("abc"+String.valueOf(d+1));
            datelist.add(date);
        }
        List newdate = new LinkedList();        for(int i = 0;i < datelist.size();i++){
           Date date = (Date)datelist.get(i);
           newdate.add(i,date.getValue());//将要比较的值放入新的List
        }        List datelist1 = new LinkedList();  //list2
        for(int d = 1;d < 5; d++){
            Date date = new Date();
            date.setId(d);
            date.setValue("abc"+String.valueOf(d));
            datelist1.add(date);
        }
        for(int i = 0;i < datelist1.size();i ++){
            Date date = (Date)datelist1.get(i);
            if(newdate.contains(date.getValue())){    //如果list1中有list2中的值
                System.out.println("date true == "+newdate.indexOf(date.getValue())); //打印list1中该对象的位置
            }
        }        
    }    private static class  Date{        public Date(){
            
        }
        private int id;
        private String value;        public int getId() {
            return id;
        }        public void setId(int id) {
            this.id = id;
        }        public String getValue() {
            return value;
        }        public void setValue(String value) {
            this.value = value;
        }
    }
}随便写了一下 lz可以参考一下，方法比较笨！

Answer 11

我是楼主，问题在说详细一点。
我要比较的是企业名称，我想得到list1中的企业在list2中没有或相似的企业。但是问题是有可能企业名称中少一两个字，比如“有限公司”变成“公司”，北京市变成了北京，这样就叫相似的，这个我也需要，至于相似到什么程度等规则我都已经定好了，我是把企业名称拆开成一个字一个字的有序的比对，所以说数据库中直接比对不了的。且无法比对大小（全是中文）。现在数据量少的话，没有问题。但是数据量多了，就要循环list1.size（）*list2.size（）-已经比对上的size（企业名称完全一致的）。需要很长时间.就像上面说的涉及运算，有谁能提供好点的运算？或者更好的想法。

Answer 12

如果已经排过序的，那就直接合并。import java.util.ArrayList;
public class merge { private ArrayList<String> notMatch = new ArrayList<String>();
private ArrayList<String> match = new ArrayList<String>();

public void mergeArray(ArrayList<String> list1, ArrayList<String> list2) {
int i = 0;
int j = 0;

while (i < list1.size() && j < list2.size()) {
if (list1.get(i).compareTo(list2.get(j)) < 0) {
notMatch.add(list1.get(i));
i++;
}
else if (list1.get(i).compareTo(list2.get(j)) == 0) {
match.add(list1.get(i));
i++; j++;
}
else {
notMatch.add(list2.get(j));
j++;
}
}

//add remaining items
while (i < list1.size()) {
notMatch.add(list1.get(i));
i++;
}

while (j < list2.size()) {
notMatch.add(list2.get(j));
j++;
}

//print
for (i = 0; i < notMatch.size(); i++) {
System.out.println(notMatch.get(i));
}
System.out.println("*****************");
for (j = 0; j < match.size(); j++) {
System.out.println(match.get(j));
}
}
/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> list1 = new ArrayList<String>();
list1.add("abc");
list1.add("abcd");
list1.add("ert");
list1.add("ghj");
ArrayList<String> list2 = new ArrayList<String>();
list2.add("bcv");
list2.add("cxz");
list2.add("ert");
new merge().mergeArray(list1, list2);

}}

Answer 13

这个match到是很快的到了，但是notmcatch（数据量还是很大）还要再进行比对，要找出相似80%以上的。match其实数量并不是很多。还是一样的问题，我试了用几个线程，一个线程执行一部分，但是更慢。如果谁还有更好的方法，我可以在加分。谢谢了。