我正在做一项任务,要求我测量两种不同的搜索算法所花费的时间,顺序和二进制(我想说明效率)。我有一个大约 280 个单词的目标列表和一个大约 1200 个单词的搜索池列表。我已经读取了这两个文件并将单词存储在 ArrayLists 中。
这是我到目前为止实现的顺序算法的相关位:
long startTime = System.nanoTime();
//search sorted list for as long as end of list has not been reached and
//current list item lexicographically precedes target String
while((compareResult > 0)&&(position != searchPool.size()-1)){
//update to current position
position += 1;
compareResult = target.compareTo(searchPool.get((int)position));
comparisonCount += 1;
}//end while loop
long endTime = System.nanoTime();
timeElapsed = endTime - startTime; //timeElapsed also a long
在此之后,我会显示进行的比较次数和经过的时间(以毫秒为单位,所以我先除以一百万)。
前几个数字的返回时间约为 0.5 到 0.7 毫秒。这个数字向下摆动到第 32 个字,耗时 0.1 毫秒。剩下的 150 个字都需要 0.0 ms。
我期望比较次数和经过的时间之间存在直接相关性。知道出了什么问题吗?
旁白:我想到 compareTo 方法进行的比较次数(即字长)可能会影响时间,但是即使是未出现在搜索列表中的长字(因此必须与之前的所有项目进行比较)得出结论)如果它们出现得更远,请不要花时间。