两个List遍历效率问题

Question

本帖最后由 zhuyouyong 于 2014-05-14 09:45:26 编辑

Answer 1

List<Worker> workerList ;
Map<ID,JobTask> jobMap;
用Map做键值查询，效率比遍历List要高得多。

Answer 2

我觉得楼上说的都不对  如果把两个list封装成map  那么取的时候确实快了  但是存的时候要花时间我觉得  如果循环结束了之后两个list就无效了  可以在循环中  如果匹配  那么从集合中remove掉  这样就不是n*n了 

Answer 3

可以缩短一半时间，变成n*n/2，但是当n很大的时候跟n*n还是一个数量级的。
通常List是用数组实现的，而长数组的remove花费的时间要长一点。
个人觉得还是Map比较靠谱

Answer 4

会抛出ConcurrentModifyException的！

Answer 5

提升效率的问题，3楼说的也有道理。
6楼产生的那个异常是在用Iterator遍历集合对象时，没有用迭代器删除集合元素，而是调用集合对象的方法删除，从而产生的异常。集合对象和迭代器对象，是两个不同的对象，维护的是相同的数据镜像。
你用迭代器对象遍历一个集合镜像的同时，又用集合对象做了删除操作，导致集合对象和迭代器对象所维护的数据镜像不一致。
所以才抛出那个异常的（虽然都是同一个集合单位，但是，是看做不同镜像来思考的）。
正常的思路是，用迭代器遍历集合时，用迭代器对象进行当前对象的删除操作，这样就不抛出那个异常了。

Answer 6

如果 更多的考虑到效率 便牺牲存储， 用map吧

Answer 7

为什么不把Worker中的JobTaskId直接放JobTask呢 一对多多好啊

Answer 8

1、首先代码没有问题，然后主要看需求，比如你可能找到一个就break了，当然了如果是一对多就没办法了，只有遍历完成。
2、至于性能优化，楼上说通过匹配移除，首先匹配移除，你得使用线程安全的List，比如CopyOnWriteArrayList，但是安全是有代价的，CopyOnWriteArrayList所有的写操作，都是拷贝整个底层数组，使用移除实现优化是不可行的。
3、对于map，和设计bean的时候，一对多和键值对，这样也算解决方案，但是很少在项目开始时就会想到哪两个List会进行双重循环查询，我也觉得没必要这么做。
总结下，如果没有出现特别的大的问题，没必要做什么改变，除非真正由于这个出现了问题再想办法进行优化；还有两个非常大List迭代，考虑的更多的可能不是时间，而是内存问题，如果List中对象超级多，每个对象又占用了相当的内存，可能会导致OOM。

Answer 9

当然还是Map靠谱，Map提供比List灵活得多的存取方式，而速度上几乎与List是一个级别的，不存在Map存取的时候比List慢得多的情况。假设WorkerList的Size是n，JobList的Size是m，那么用Map，几乎是O(n)。如果只是WorkerList的Size比较大，而JobList相对较小的话，可以对JobList先排序，然后内循环就可以做成二分搜索，所以总耗费也不过O(n*log m)+O(m*log m)，可能甚至比Map法更快。

Answer 10

从你上面的描述看：
一个Job有多个work; 也就是JobList的大小要远小于workList;
如果JobList元素是唯一的；可以如下处理：long start = System.currentTimeMillis();

Collections.sort(jobTaskList, new Comparator<JobTask>() {
@Override
public int compare(JobTask j1, JobTask j2) {
if(j1.getId() == j2.getId()){
return 0;
}else if(j1.getId() < j2.getId()){
return -1;
}else{
return 1;
}
}
});


Collections.sort(workList, new Comparator<Worker>() {
@Override
public int compare(Worker w1, Worker w2) {
if(w1.getJobTaskId() == w2.getJobTaskId()){
return 0;
}else if(w1.getJobTaskId() < w2.getJobTaskId()){
return -1;
}else{
return 1;
}
}
});

int counts = 0;
int index = 0;
int size = workList.size();

for(JobTask jobTask : jobTaskList){ 
int jobId = jobTask.getId();

while(true){
if(index < size && workList.get(index).getJobTaskId() == jobId){
//......
index++;
counts++;
}else{
break;
}
}
}

long end = System.currentTimeMillis();
System.out.println("Test: " + (end - start));

Answer 11

整个示例：
测试发现有10倍以上的提升；public class CollectionsDemo { public static void main(String[] args) {
List<Worker> workList = new ArrayList<Worker>();
List<JobTask> jobTaskList = new ArrayList<JobTask>();

init(workList, jobTaskList);

test(workList, jobTaskList);
test2(workList, jobTaskList);
} public static void init(List<Worker> workList, List<JobTask> jobTaskList){
int workId = 0;
int jobId = 0;
Random ran = new Random(37);

for(int i = 0; i < 10000; i++){
jobId = ran.nextInt(1000000);
JobTask job = new JobTask(jobId, "job");
if(!jobTaskList.contains(job)){
jobTaskList.add(job);
}

for(int j = 0; j < 5; j++){
workId = ran.nextInt(1000000);
Worker worker = new Worker(workId, "worker", jobId);
if(!workList.contains(worker)){
workList.add(worker);
}
}
}

System.out.println("Job:" + jobTaskList.size());
System.out.println("Work:" + workList.size());
}

public static void test(List<Worker> workList, List<JobTask> jobTaskList){

System.out.println("workList 有 ： " + workList.size());
long start = System.currentTimeMillis();

Collections.sort(jobTaskList, new Comparator<JobTask>() {
@Override
public int compare(JobTask j1, JobTask j2) {
if(j1.getId() == j2.getId()){
return 0;
}else if(j1.getId() < j2.getId()){
return -1;
}else{
return 1;
}
}
});


Collections.sort(workList, new Comparator<Worker>() {
@Override
public int compare(Worker w1, Worker w2) {
if(w1.getJobTaskId() == w2.getJobTaskId()){
return 0;
}else if(w1.getJobTaskId() < w2.getJobTaskId()){
return -1;
}else{
return 1;
}
}
});

int counts = 0;
int index = 0;
int size = workList.size();

for(JobTask jobTask : jobTaskList){ 
int jobId = jobTask.getId();

while(true){
if(index < size && workList.get(index).getJobTaskId() == jobId){
//......
index++;
counts++;
}else{
break;
}
}
}

long end = System.currentTimeMillis();
System.out.println("Test: " + (end - start));

System.out.println("workList处理了： " + counts);
}

public static void test2(List<Worker> workList, List<JobTask> jobTaskList){
long start = System.currentTimeMillis();
int counts = 0;

for(Worker worker : workList){
for(JobTask jobTask : jobTaskList){
if(worker.getJobTaskId() == jobTask.getId()){
//......
counts++;
}
}
}

long end = System.currentTimeMillis();
System.out.println("Test2: " + (end - start));
}
}class Worker{
int id;
String name;
int jobTaskId;

Worker(int id, String name, int jobTaskId){
this.id = id;
this.name = name;
this.jobTaskId = jobTaskId;
}

public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getJobTaskId() {
return jobTaskId;
}
public void setJobTaskId(int jobTaskId) {
this.jobTaskId = jobTaskId;
} @Override
public int hashCode() {
return this.id * 37;
} @Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj == this) return true;
if(obj instanceof Worker){
if(this.id == ((Worker)obj).id){
return true;
}else{
return false;
}
}
return false;
}
}class JobTask{
int id;
String name;

JobTask(int id, String name){
this.id = id;
this.name = name;
}

public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}

@Override
public int hashCode() {
return this.id * 37;
} @Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj == this) return true;
if(obj instanceof JobTask){
if(this.id == ((JobTask)obj).id){
return true;
}else{
return false;
}
}
return false;
}}

Answer 12

将List<JobTask> jobList排序，或者使用TreeSet添加比较器。
再循环的时候，使用二分查找Collections.binarySerach()，看数据量大小，有可能效率会高一点。

Answer 13

Map<T,List> 这种形式如何？

Answer 14

还是采用hashmap<JobTaskId,jobList>存储吧。hash数组实现，查找、获取对象最快。

Answer 15

workerList 循环一次是不可避免的，现在是 jobList 循环问题，吧jobList 用map代替感觉还是很不错的

Answer 16

个人建议将job变成map！
一个work对应多个jobList！
所以jobMap的key 为job  id，而value为 job ID相同的记录的集合
Map<String,List<job>>这样直接根据work 中的job id就可以从Map 中取值了

Answer 17

13楼的方法是有效的；
我也是同样的问题，主表4W，明细表15W；
外层循环主表，内层循环明细表，不用技巧直接比较下来，耗时13分钟；
按照13楼办法，将两个list都按关联字段排好序，内层循环找到了明细时标记号，下一次比较后不符合，则直接消除内层循环了，时间缩短到80秒。
不过因为排序字段的规则问题，风险还是蛮大的。

Answer 18

            CisZhCardTcxx cisZhCardTcxx = null;
List<CisZhCardTcxx> listCisZhCardTcxx = new ArrayList<CisZhCardTcxx>();
for (int i = 0; i < listCardRecordSize; i++) {
CardRecord cardRecord_ = listCardRecord.get(i);
String cardNum = cardRecord_.getCard_num();
boolean haveCardTcxx = false; //是否存在

//循环匹配
for (int j = 0; j < listCardRecordPackageSize; j++) {
CardRecordPackage cardRecordPackage_ = listCardRecordPackage.get(j);
if(cardNum.equals(cardRecordPackage_.getCard_num())){
cisZhCardTcxx = new CisZhCardTcxx();
cisZhCardTcxx.setCardno(cardNum);
cisZhCardTcxx.setXh(j + 1); //序号
Integer tclx = this.getTclx(cardRecord_); //类型
cisZhCardTcxx.setTclx(tclx);
cisZhCardTcxx.setTcdm(cardRecordPackage_.getPackage_num());
cisZhCardTcxx.setTcmc(cardRecordPackage_.getPackage_name());
listCisZhCardTcxx.add(cisZhCardTcxx);
haveCardTcxx = true; //存在
}else if(haveCardTcxx == true){
//已经匹配到套餐,则直接跳出(listCardRecord和listCardRecordPackage都必须严格按关联字段排序)
break;
}
}

if(haveCardTcxx == false){
super.AjaxFailure("未查询到***,请联系管理员");
}
}