比双重嵌套的ArrayList更高效吗？

我正在构建一个每天处理中等数据量的Java后端组件。我们有一个POJO，我们称之为Widget，它有大约10个属性。我的软件必须处理Widget列表组：本质上还有其他进程（完全不同的系统）将它们自己的List<Widget>放在一起，然后将它们发送到我的软件。我的软件实际收到的包装POJO，看起来像这样：比双重嵌套的ArrayList更高效吗？

public class Payload { 
    private List<Widget> widgets; // <-- what I want 
    private String guid; // GUID; my software doesn't need this 
    private boolean fizz; // again, my software doesn't need this 
    ... many other properties that I don't care about 
}

我的软件汇集了所有这些List<Widget>，各由不同的系统上创建的，然后在一个大批量一起对其进行处理。

我暂时选择了ArrayList<ArrayList<Widget>>作为保存这批Widget列表的数据结构。将会有大约500,000个组List<Widget>（外部ArrayList），并且每个List<Widget>将各自具有大约5个Widget;在内部ArrayList的总共约250万Widget s。

在最近的代码审查中，一些技术负责人告诉我，我为这个批处理小部件选择了错误的数据结构。他们告诉我，我应该使用HashMap<String,List<Widget>>，因为它更高效，更容易使用。 hashmap密钥是我的软件给出的Payload中包含的GUID。不是因为任何原因我需要GUID，它只是保持〜500,000 List<Widget>独立的关键 - 我确实需要这样做。

这让我想到：谁是对的？！？我们在这个数据结构上做的唯一操作是“增加”（在ArrayList的情况下，只需通过add(...)添加Widget或List<Widget>）然后“读取”（在我的软件中，我必须遍历每个Widget并检查。它的东西与我的嵌套ArrayList它的要点是：

for(List<Widget> widgetList : myDoublyNestedArrayOfWidgets) { 
    for(Widget widget : widgetList) { 
     ... 
    } 
}

这些都是我们所需要的只是操作：添加不同List<Widget> s到一些大“批量”数据结构，然后在以后的时间，检查所有这些软件，并与每个Widget一起做这个软件。这个软件运行在一些内存和处理能力都很强大的服务器上。

所以我问：**是ArrayList<ArrayList<Widget>>正确的选择，HashMap<String,List<Widget>>，还是别的......为什么？

来源

2013-02-14 IAmYourFaja

我觉得你说的很多东西不是回答核心问题所必需的。试着把它看作是列举事实而不是讲故事。 – Dukeling 2013-02-14 13:10:15

如果你一起处理所有东西，你可以使用'ArrayList '，并在进入主列表时添加Widget？另外，在开始处理之前是否需要全部500k套，或者是否可以处理每个小列表，并将结果存储起来。产生一个处理每个小列表的线程，然后在完成后抛出列表可能会提高内存效率 – Windle 2013-02-14 13:12:10

在附注中，您的用户名让我大笑=） – Windle 2013-02-14 13:14:18

所以我问：是ArrayList<ArrayList<Widget>>正确的选择，HashMap<String,List<Widget>>，或其他什么......为什么？

最后，重要的是你的软件解决了它应该解决的问题。

HashMap比ArrayList更昂贵，如果您不需要通过键访问数据，ArrayList更可能是最佳选择。此外，使用ArrayList时，需要编写的代码执行处理似乎更简单高效。

顺便说一句，有ArrayList<ArrayList<Widget>>或HashMap<String,List<Widget>>闻起来有点。也许你正在建模的是ArrayList<WidgetGroup>和WidgetGroup包含一个List<Widget>（与所有其他属性，目前，你可能不需要）。但是，如果你的WidgetGroup只包含一个ArrayList，那么不要引入这个新类（保持简单）。

这让我想到：谁是对的？！？

在您的解决方案和您的同行评审者之间，我个人非常喜欢你的解决方案。

但是，您可以保留这一点，并遵循“技术线索”。如果这是他们的角色，那么他们的决定是重要的，他们有责任提供这些选择。（支付支票的人永远是对的）

来源

2013-02-14 13:12:04

哈希映射不比数组列表更有效或更容易使用。如果某些时候您需要通过GUID键查找批处理，则更改可能是合理的。

哈希映射不如数组列表有效，因为调整它的大小意味着必须重新评估哈希代码并将数据重新分配到相当随机的内存位置。另一方面调整数组的大小会将旧数组中的内容线性复制到新的数组中，这对CPU高速缓存非常友好。

哈希映射也不容易处理。要访问条目，您必须通过地图的条目集，这会打破law of Demeter。

来源

2013-02-14 13:09:30 Joni

也许你最终想要的是一个嵌入式（核心）数据库。另一种可能性是JavaSpaces/NoSQL，解耦交付和处理。依靠。

来源

2013-02-14 13:13:09

有一个名词，您继续使用，但从您的数据模型中缺失：批次。如果你真的关心他们留在他们的批次，并保持你的代码的可读性，然后封装进行批量类：

 
class Batch { 
    String guid; 
    List&ltWidget> widgets; 
}

而且，如果你不关心批次，则可能你只是它们压平全部变成单个List<Widget>？

来源

2013-02-14 13:14:35

从你的问题很明显，你正在做这些事情。

从您的数据中读取数据。
添加更多小部件。

问题是如何改变您的数据结构ArrayList<ArrayList<Widget>> to HashMap<String,List<Widget>>如何影响以上两项活动。

1）阅读：你将这些措施分成4组，所以使用hashmap你将存储使用散列您的组这确实是没有意义的小数据集（在你的情况下，组），所以没有必要在这里使用hashmap。

2）添加更多小部件：您将访问您要添加到的列表，所以再次同样你的阅读。它不会伤害使用ArrayListObj.get(index)。

现在使用ArrayList将始终按顺序读取widgets。这不会使用Hashmap完成，但无论如何，我不认为这是你的关注还是它？如果你有随机访问内部列表，并使用一个HashMap 代码看起来更优雅到谁荨麻疹爆发时，他们看到的嵌套循环评审:-)

来源

2013-02-14 13:14:44

的Hashmap会更有效。但是，如果您必须迭代并访问每个节点，则不会比On^2做得更好。你可以将它们填入数据库中，但除了复杂性之外，这不会带来任何好处。它更加优雅，就像hashmap。当然，所有这一切都假定你有记忆一次容纳250万个Widget。如果您必须对其进行分页，那么某种类型的DB SQL或NoSQL可能会更好。

来源

2013-02-14 13:18:26 WPrecht

比双重嵌套的ArrayList更高效吗？

回答

相关问题