在大AbstractList上的Java二进制搜索

Question

精简版:

我有一个LinkedList的n随机Integer升序秒.
如果我Collections.binarySearch在该列表上使用它,它适用于任何n我尝试过的.
当我换行LinkedList与AbstractList然而,对于n>10000二进制搜索开始表现得非常奇怪.
它不是运行适当的二进制搜索,而是遍历整个列表.

---

长版:

我有一个"file"包含升序的随机数,其中每行包含一个数字.
我想二进制搜索"file"并找到"line number"给定数字的索引(或).

一个简单的解决方案就是读取整个文件并将每个数字放入a中LinkedList,然后使用Collections.binarySearch它LinkedList.

现在,让我们说我得到的信息是,从中读取一行"file"是一项代价高昂的操作.

我试图做的,尽量减少我必须阅读的时间"file",是"模拟"那个LinkedList,并AbstractList在每次使用时使用一个地方get(int index),AbstractList我只是index从中读取行"file".

当我的AbstractList大小是<1000,当我尝试更大的列表时,二进制搜索似乎停止工作,并且只是迭代所有AbstractList(从第一个节点到最后一个节点),这似乎工作得很好.

---

我似乎已经将问题缩小到使用带有二进制搜索的大型AbstractList.我不确定为什么会这样,并且会喜欢一些帮助.

我已经包含了"长版",以防有人能够提出另一种解决方案.

谢谢!

Answer 1

Javadoc救援:

[ binarySearch]在log(n)时间运行"随机访问"列表(提供接近恒定时间的位置访问).如果指定的列表没有实现RandomAccess接口并且很大,则此方法将执行基于迭代器的二进制搜索,该搜索执行O(n)链接遍历和O(log n)元素比较.

LinkedList并且AbstractList不实施RandomAccess.