收集Java列表中唯一数据的最快方法

我的问题的基础是在Java中给出了List对象，返回唯一数据集合的最快方法是什么？收集Java列表中唯一数据的最快方法

更具体的版本是，我有一个2d ArrayList（想象它像一个表），我想循环给定的列索引并返回唯一的数据。

这里是我的当前设置：

public Set<Object> getDistinctColumnData(int colIndex) { 

    //dataByIndex = List<List<Object>> 

    Set<Object> colDistinctData = new HashSet<Object>(dataByIndex.size() + 1, 1f) ; 

    for(List<Object> row : dataByIndex) { 
     colDistinctData.add(row.get(colIndex)) ; 
    } 

    return colDistinctData ; 

}

我有一个小的性能增益，当我最初的容量设置为加一个非组不同的大小和负载因子1（我的想法是它赢得直到它达到100％才需要增长，即使原始设置已经100％截然不同（或者我错了吗？））。

有没有更快的方法？

来源

2012-02-21 CrazyPenguin

downvoter会照顾一个理由吗？ – CrazyPenguin 2012-02-21 19:59:45

我会使用'（dataByIndex.size（）* 3/2）'作为初始大小，并保留负载因子，除非您预计会有大量重复项。 – 2012-02-21 20:02:46

你的代码看起来不错。处理别的事情。 – Bohemian 2012-02-21 20:09:17

我认为如果你只有两个独特的集合，它会更快。维护你的dataByIndex列表，还维护一个dataSet集合（Set）。当你插入到你的dataByIndex列表中时，也放入你的dataSet集合中。然后在需要的地方使用你的dataSet。 Set将会保持Set的本质唯一性。

来源

2012-02-21 20:03:05 Shinzul

我想过这个。将处理移至添加行的时间。但是增加数据的性能损失（发生这种情况比获取不同数据更频繁）并不是真正值得获取不同数据的收益。 – CrazyPenguin 2012-02-21 20:06:12

你有基准差异吗？这应该是一个相对简单的代码更改，我认为你可能会对这种影响感到惊讶... – Shinzul 2012-02-21 20:08:33

如果OP说插入比独立查询发生得更多（这是不寻常的，但我们没有理由怀疑它），那么确实保持一个单独的独立集可能会达到性能而不是改善它。 – biziclop 2012-02-21 20:26:23

我认为将容量和负载系数设置为您指定的值没有多大意义。你使用什么散列函数？可能是降级到链接列表？

来源

2012-02-21 20:05:11 jdevelop

如果增加HashSet的初始容量，您可能会进一步提高性能（平均）。这是因为您的列表中对象的散列值的分布可能会导致碰撞更可能发生。

例如，给定以下列表，除第一次插入外，除第一次插入之外的所有插入都将导致冲突，尽管没有重复的值。（整数的Java哈希函数是整数本身的值，并且HashSet在发生冲突时使用开放寻址和线性探测）。

[0,10,1,2,3,4,5,6,7]

甚至更糟，因为每个插入必须检查每个非空闲空间才能插入。

[0, 5, 25, 125]

在最后一个例子0投入指数0.5得到去索引0最初5％的大小（即5）等于0，所以后来去索引1 125会去索引0，但是0在索引0处，5在索引1处并且25在索引2处。这意味着在三次检查之后最终可以在索引3处插入125.

如果增加初始容量，则这降低了碰撞概率平均），并且如果发生碰撞，平均也会减少所需的检查次数。默认情况下，java使用0.75的加载因子作为性能和内存使用率之间的良好平衡。因此，除以0.75的负载系数，并加1应该给你一个很好的初始容量。

来源

2012-02-21 20:12:15 Dunes

收集Java列表中唯一数据的最快方法

回答

相关问题