Java 对大型抽象列表的二分查找

标签 java linked-list abstract binary-search

简短版本:

我有一个LinkedListn随机Integer s 按升序排列。
如果我使用 Collections.binarySearch在该列表中,它适用于任何 n我试过了。
当我包裹LinkedList时与 AbstractList然而,对于 n>10000二分查找开始变得非常奇怪。
它不运行适当的二分搜索,而是迭代整个列表。

<小时/>

长版本:

我有一个"file"包含按升序排列的随机数,其中每一行保存一个数字。
我想对 "file" 进行二分搜索并找到给定数字的索引(或 "line number" )。

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

现在,假设我得到了从 "file" 读取一行的信息这是一项成本高昂的操作。

我试图做的就是尽量减少我阅读 "file" 的时间,就是“模拟”LinkedList ,并使用AbstractList每次我使用get(int index)时在哪里在那AbstractList我刚刚读了这行 index来自"file" .

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

<小时/>

我似乎已经将问题范围缩小到使用带有二分搜索的大型 AbstractList。 我不确定为什么会发生这种情况,并且希望得到一些帮助。

我已经包含了“长版本”,以防有人能够提出其他解决方案。

谢谢!

最佳答案

Javadoc to the rescue :

[binarySearch] runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.

LinkedListAbstractList 未实现 RandomAccess

关于Java 对大型抽象列表的二分查找,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43530851/

相关文章:

c - 这是一个链表吗?

c# - 密封类中没有主体的虚拟方法

java - java中的抽象与抽象

java - 从两个不同的接口(interface)调用相同的方法名称 - Java

java - 强制将JRE系统库添加到android项目中

java - 网络 4 : set default endianness of ByteBuf

java - 使用 Jackson 解析 Json 文件

java - 如何在 Spring Boot 中使用自定义前缀配置数据库配置连接池?

java - 如何从linkedList中递归删除一个项目?

java - Long 列表如何检查它是否包含值?