问个算法设计问题

Question

在系统开发的过程中有个业务需求是对数据进行年度统计
我所写的实现算法如下：/**
 * 过滤检查记录
 * @param checkMains 检查记录集合
 * @param checkYear 检查年份
 * @return 过滤后的检查记录
 */
private List<CheckMain> getFilterCheckMains(List<CheckMain> checkMains, String checkYear){
                //  检查记录拷贝
List<CheckMain> checkMainsCopy = checkMains;
// for (CheckMain checkMain : checkMains) {
for (int i = 0; i < checkMains.size(); i++) {
CheckMain checkMain = checkMains.get(i);
// 对年度匹配数据进行处理
if (checkMain.getCheckYear().equals(checkYear)) {
// for (CheckMain checkMain2 : checkMains) {
for (int j = i; j < checkMains.size(); j++) {
CheckMain checkMain2 = checkMains.get(j);
// 对相同路线编号进行处理
if (checkMain.getRoadCode().equals(checkMain2.getRoadCode())) {
// 对相同起点桩号进行处理，同一路线同一起点桩号同一年度保留最后的记录
if (checkMain.getRoadStart().floatValue() == checkMain2.getRoadStart().floatValue()) {
// 保留年度最后检查的记录
if (checkMain.getCheckDate().after(checkMain2.getCheckDate())) {
checkMainsCopy.remove(checkMain2);
} else {
checkMainsCopy.remove(checkMain);
}
}
}
}
} else { // 年度不匹配的删除
checkMainsCopy.remove(checkMain);
}
}
return checkMainsCopy;
}
解释一下：
这是一个道路检测系统路面质量年度统计算法
每条路线（路线编号识别）有多个路段（不同起止点）
CheckMain 为检查记录对象（表）
每条路线的每一个路段每年可能要检查几次
而在路面质量年度统计中只取当年最后一次检查数据库算法中对检查记录进行的两次迭代是时间复杂度的关键
目前只有200多条数据都要一分钟左右
请问如何改善算法降低时间复杂度？thanks

Answer 1

你的算法是n*n复杂度，我建议你按照下面的算法进行改写成一个线性时间复杂度算法：
初始化一个空的Hash表List(其实根据路线与路段的编号，应该也可以用数组实现)，这个表包含了所有路线的所有路段；
然后遍历你的CheckMain一次：
    如果当前的记录在List中没有出现，那么将这个记录填入List
   如果当前的记录已经在List中出现，比较它们的时间，如果时间更晚，则更新List
OK

Answer 2

好像遍历一次不行吧？
不好意思，有点看不明白你的设计思想
能否解释下？
thanks

Answer 3

你只是要过滤掉CheckMain中的一些早期记录而已，那么方法有很多的。
首先，我的方法是这样的：
1 将每条路线的每条路段对应一个记录，所有记录可以通过一次访存就能查到，所有记录用哈希表或者数组【List】保存起来
2 对CheckMain中的每个记录L，都与List中的记录进行比较（每次只需要一次访问内存操作，因为你可以从L中获取路线和路段，然后根据路线和路段信息一次访存，就知道List表中有没有与L路线和路段信息相同的记录，如果没有，就加入到List，如果有，就用L与它比较时间，如果原来的时间比较早，就用L替换它）当然，还有其他方法，比如将CheckMain中所有相同路线路段的信息分别搜集起来，然后排序，最后再搜集到一个新的CheckMain中

Answer 4

解决了
谢谢 liaomingxue 
/**
 * 过滤检查记录
 * @param checkMains
 * @param checkYear
 * @return
 */
private Map<String, CheckMain> getFilterCheckMains(List<CheckMain> checkMains, String checkYear){
Map<String, CheckMain> result = new HashMap<String, CheckMain>();
for (CheckMain checkMain : checkMains) {
if (checkMain.getCheckYear().equals(checkYear)) {
CheckMain checkMainInMap = result.get(checkYear+checkMain.getRoadCode()+checkMain.getRoadStart());
if (checkMainInMap ==null) {
result.put(checkYear+checkMain.getRoadCode()+checkMain.getRoadStart(), checkMain);
} else {
if (checkMain.getCheckDate().after(checkMainInMap.getCheckDate())) {
result.put(checkYear+checkMain.getRoadCode()+checkMain.getRoadStart(), checkMain);
}
}
}
}
return result;
}

Answer 5

200多条记录的处理，竟然跑1分多钟的时间，凭经验而论，应该不是楼主给出的算法时间复杂度太高的原因。
如果楼主不相信，可以自己手工创建200个对象放到List里面，再调用楼主的方法试试，应该在1秒内就跑完了。
（当然，我所说的200个对象，楼主可以编写循环来创建。）我觉得，问题的瓶颈，应该出在和数据库交互的时间上。
看到楼主的问题，和算法，我首先想到的是能否直接用一到两条SQL语句直接搞定，这样，应该是最省时间的。
因为，我现在负责的项目，就是直接操作SQL语句来完成系统与数据库之间数据的交互，中间没有太多的封装。
比如，楼主的问题，所要的结果集，只需要一个自链接的条件查询就能够得到。当然，楼主现在的程序，所用的对象，应该已经通过ORM层进行封装了的。
那么，是不是可以通过一些简单的程序来测试一下，问题的瓶颈具体出现在哪里？
我感觉，应该是遍历参数的那个List时，所用的时间较多。
楼主不妨试试将for循环中的循环体注释掉，只进行List遍历，看看所用的时间。
如果时间比较长的话，就解决这个遍历时间长的问题。
如果不是遍历List所用时间长的话，可以在for循环的循环体里，只进行对CheckMain对象所有属性get方法的调用。
这样，可以判断，问题是否出现在getter调用所花费的时间过长，如果是，就要看看是什么原因，并想办法解决。楼主4楼的代码已经是优化过的代码了。如果只是算法时间复杂度的问题，那么优化后的代码，时间应该至少可以提高一个数量级才对。
也就是说优化后，200条记录应该在1秒内搞定。

Answer 6

运行时加个-Xprof马上就看出来时间都花在哪里了