remove()方法太慢了

Question

我有一个读取内存追踪的问题。我已经阅读并保存了页面及其引用的位置。

地图结构：

    Map<Integer, List<Integer>> map = new HashMap<>();

然后我再次读取文件，并从整数列表中删除引用。

FileReader arq = new FileReader(new File(Path));
BufferedReader reader = new BufferedReader(arq, 41943040);
while ( (std = reader.readLine()) != null ) {
        requestedPage = Integer.parseInt(std, 16);
        //do something
        M.map.get(requestedPage).remove(0));
    }

问题在于删除这些引用太耗费时间，对于大型跟踪，删除引用需要几个小时。请问还有其他解决方案吗？

谢谢！

- Felipe Carminati

---

你使用的 List 实现是什么？ - cheeken

抱歉，这是一个ArrayList的实现。 - Felipe Carminati

谢谢，我已经反转了LinkedList并从末尾移除，现在读取跟踪仅需要4秒钟。 - Felipe Carminati

Answer 1

我认为如果您只打算在列表中执行remove(0)操作，则LinkedList是一种更好的数据结构：

尝试：

Map<Integer, LinkedList<Integer>> map = new HashMap<Integer, LinkedList<Integer>>();

- Strelok

---

抱歉，我确实改变了时间。从我的跟踪中的17分钟缩短到了10分钟。不幸的是，我需要更快的速度。但还是谢谢你的提示！;) - Felipe Carminati

@FelipeCarminati 你需要10分钟来删除LinkedList的头部吗？我很确定这个方法不会导致程序变慢。列表中有多少元素？ - Strelok

@FelipeCarminati - 从链表中移除第一个元素770万次只需要不到一秒钟的时间...无论链表的长度如何。这并不是你代码的瓶颈所在。我建议你对此进行科学分析。对你的代码进行性能分析。 - Stephen C

问题不仅仅是要删除列表的所有第一个位置，我还需要读取页面编号，然后检查它是否已经在内存中，然后从映射中删除其引用。删除第一个位置（即使在LinkedList上）需要很长时间（老实说我不知道为什么），但是反转列表顺序并从末尾删除就解决了我的问题。这只需要几秒钟。 - Felipe Carminati

@FelipeCarminati请确保使用旁边的勾选框将帮助您最多的答案标记为“已接受”。这样，遇到相同问题的人们将很快看到解决方案。 - Strelok

Answer 2

如果列表非常大，问题可能是所有从索引1到大小-1的元素都必须移动：逻辑上，索引n处的项目被移动到索引n-1。如果查看{{link1：ArrayList源代码}}，您会发现有一个System.arrayCopy调用来执行此操作。您报告的操作所需时间似乎表明存在更深层次的问题，但您可以尝试使用LinkedList或重新设计算法，以便从列表末尾而不是前面删除元素。对于LinkedList，将删除头元素，无需修改任何其他节点。如果坚持使用ArrayList，但每次删除最后一个元素而不是第一个元素，则不需要进行arrayCopy。

此外，还要看一下Guava的Multimap。它在逻辑上是一个带有值Collection的Map，就像你在这里所拥有的一样，但它提供了更好的接口。如果你还没有使用过Guava库中的其他惊人类别，那么你也应该去看看！

- smjZPkYjps

---

使用LinkedList并没有产生任何区别（正如应该的那样），我将尝试反转列表顺序，然后按照您所说的从末尾删除。谢谢！ - Felipe Carminati

抱歉，我确实改变了时间。从我的跟踪中的17分钟缩短到10分钟。不幸的是，我需要它更快。 - Felipe Carminati

访问文件的速度比从LinkedList中删除节点或从ArrayList中删除最后一个元素要慢得多。您确定您看到的缓慢一定是由于列表删除而不是文件访问引起的吗？此外，请尝试使用BufferedReader中的缓冲区大小进行实验，或者不指定大小并使用默认大小。 - smjZPkYjps

是的，我尝试将其替换为-1而不是删除它，速度非常快，但每次访问地图时都需要测试是否等于-1。 - Felipe Carminati

随意接受并点赞建议反转列表并从末尾移除的答案（提示，提示）。但是如果您查看 LinkedList 的源代码中的第169行，您会发现从 LinkedList 中删除第一个元素应该非常快，所以我觉得还有其他问题。也许是由于 LinkedList 中的节点被快速创建和删除导致的某些垃圾回收开销？ - smjZPkYjps

你可以查看https://dev59.com/JkbRa4cB1Zd3GeqP2aU0，以确定是否确实是垃圾回收导致了大量的缓慢。 - smjZPkYjps

Answer 3

谢谢，我已经反转了LinkedList并从末尾删除，现在只需要4秒钟就可以读取跟踪信息。

编辑：反转和从末尾删除并没有改变结果，我犯了一个错误。只需使用LinkedList而不是ArrayList即可解决我的问题。

- Felipe Carminati