在Java 7和8中从现有列表创建不同的列表？

Question

如果我有:

List<Integer> listInts = { 1, 1, 3, 77, 2, 19, 77, 123, 14, 123... }

在Java中,什么是创建List<Integer> listDistinctInts仅包含不同值的有效方法listInts？

我的直接想法是创建一个Set<Integer> setInts包含所有值listInts然后调用List<Integer> listDistinctInts = new ArrayList<>(setInts);

但这似乎效率低下 - 使用Java 7是否有更好的解决方案？

我没有使用Java 8,但我相信使用它我可以做这样的事情(？):

List<Integer> listDistinctInts = listInts.stream().distinct().collect(Collectors.toList());

这会比上面的方法更高效和/或在Java 8中有更有效的方法吗？

最后,(我知道,如果我只关心不同元素的数量,那么提出多个问题可能会不受欢迎,但这是直接相关的)是否listInts有更有效的方法来获得该值(在Java 7和8中) -没有先创建一个列表或所有不同元素的集合？

我最感兴趣的是使用本机Java方法来实现这一点并避免重新发明任何轮子,但如果它们提供更好的清晰度或性能,则会考虑手动代码或库.我已经阅读了这个相关的问题Java - 不同的对象列表,但是它并不完全清楚Java 7和8方法之间的性能差异,或者是否有更好的技术？

Answer 1

我现在已经根据提供的优秀答案MicroBenchmark大多数提议的选项.像大多数非平凡的表现相关的问题一样,最好的答案是"它取决于".

我的所有测试都是用JMH Java Microbenchmarking Harness完成的.

大多数这些测试都是使用JDK 1.8进行的,尽管我也使用JDK 1.7进行了一些测试,以确保其性能不会太差异(几乎完全相同).我测试了目前为止提供的答案中的以下技术:

1. Java 8 Stream - stream()如果使用Java8,使用I 的解决方案可能会成为可能:

public List<Integer> testJava8Stream(List<Integer> listInts) {
    return listInts.stream().distinct().collect(Collectors.toList());
}

专业的 现代Java 8方法,没有第三方依赖

缺点 需要Java 8

2.添加到列表 - Victor2748提出的解决方案,其中构建并添加新列表,当且仅当列表尚未包含该值时.请注意,我还以原始大小(可能的最大值)预先分配目标列表,以防止任何重新分配:

public List<Integer> testAddingToList(List<Integer> listInts) {
    List<Integer> listDistinctInts = new ArrayList<>(listInts.size());
    for(Integer i : listInts)
    {
        if( !listDistinctInts.contains(i) ) { listDistinctInts.add(i); }
    }
    return listDistinctInts;
}

专业版 适用于任何Java版本,无需创建一个Set然后复制,没有第三方代表

cons 需要在构建时反复检查列表中的现有值

3. GS Collections Fast (现在是Eclipse集合) - Craig P. Motlin使用GS Collections库及其自定义List类型提出的解决方案FastList:

public List<Integer> testGsCollectionsFast(FastList listFast)
{
    return listFast.distinct();
}

专业人士 据说非常快速,简单的表达代码,适用于Java 7和8

缺点 需要第三方库FastList而不是常规库List<Integer>

4. GS集合适应 - FastList解决方案并没有完全比较像是因为它需要FastList传递给方法而不是一个好的ol' ArrayList<Integer>因此我也测试了Craig提出的适配器方法:

public List<Integer> testGsCollectionsAdapted(List<Integer> listInts)
{
    return listAdapter.adapt(listInts).distinct();
}

专业版 不需要FastList,适用于Java 7和8

cons 必须适应List所以可能表现不佳,需要第三方库

5.番石榴ImmutableSet - Louis Wasserman在评论中提出的方法,以及卢声远盛源路在使用番石榴的回答中:

public List<Integer> testGuavaImmutable(List<Integer> listInts)
{
    return ImmutableSet.copyOf(listInts).asList();
}

专业人士 报道非常快,适用于Java 7或8

cons 返回一个Immutable List,无法处理输入List中的空值,并需要第三方库

7. HashSet - 我最初的想法(也由EverV0id,ulix和Radiodef推荐)

public List<Integer> testHashSet(List<Integer> listInts)
{
    return new ArrayList<Integer>(new HashSet<Integer>(listInts));
}

专业人员 在Java 7和8中工作,没有第三方依赖

cons 不保留列表的原始顺序,必须构造集然后复制到列表.

6. LinkedHashSet - 由于HashSet解决方案没有保留原始列表中整数的顺序,我还测试了一个使用LinkedHashSet来保存顺序的版本:

public List<Integer> testLinkedHashSet(List<Integer> listInts)
{
    return new ArrayList<Integer>(new LinkedHashSet<Integer>(listInts));
}

pros 保留原始排序,适用于Java 7和8,没有第三方依赖

缺点 不像常规HashSet方法那么快

结果

以下是各种不同尺寸的listInts结果(从最慢到最快排序的结果):

1.区分100,000个随机整数的ArrayList在0-50,000之间(即大列表,一些重复)

Benchmark                Mode       Samples     Mean   Mean error    Units

AddingToList            thrpt        10        0.505        0.012    ops/s
Java8Stream             thrpt        10      234.932       31.959    ops/s
LinkedHashSet           thrpt        10      262.185       16.679    ops/s
HashSet                 thrpt        10      264.295       24.154    ops/s
GsCollectionsAdapted    thrpt        10      357.998       18.468    ops/s
GsCollectionsFast       thrpt        10      363.443       40.089    ops/s
GuavaImmutable          thrpt        10      469.423       26.056    ops/s

2.与0到50之间的1000个随机整数的ArrayList不同(即中等列表,多个重复)

Benchmark                Mode       Samples     Mean   Mean error    Units

AddingToList            thrpt        10    32794.698     1154.113    ops/s
HashSet                 thrpt        10    61622.073     2752.557    ops/s
LinkedHashSet           thrpt        10    67155.865     1690.119    ops/s
Java8Stream             thrpt        10    87440.902    13517.925    ops/s
GsCollectionsFast       thrpt        10   103490.738    35302.201    ops/s
GsCollectionsAdapted    thrpt        10   143135.973     4733.601    ops/s
GuavaImmutable          thrpt        10   186301.330    13421.850    ops/s

3.取0-100之间的100个随机整数的ArrayList(即小列表,一些重复)

Benchmark                Mode       Samples     Mean   Mean error    Units

AddingToList            thrpt        10   278435.085    14229.285    ops/s
Java8Stream             thrpt        10   397664.052    24282.858    ops/s
LinkedHashSet           thrpt        10   462701.618    20098.435    ops/s
GsCollectionsAdapted    thrpt        10   477097.125    15212.580    ops/s
GsCollectionsFast       thrpt        10   511248.923    48155.211    ops/s
HashSet                 thrpt        10   512003.713    25886.696    ops/s
GuavaImmutable          thrpt        10  1082006.560    18716.012    ops/s

4.在0-50之间取10个随机整数的ArrayList(即微小列表,几个重复)

Benchmark                Mode       Samples     Mean   Mean error    Units

Java8Stream             thrpt        10  2739774.758   306124.297    ops/s
LinkedHashSet           thrpt        10  3607479.332   150331.918    ops/s
HashSet                 thrpt        10  4238393.657   185624.358    ops/s
GsCollectionsAdapted    thrpt        10  5919254.755   495444.800    ops/s
GsCollectionsFast       thrpt        10  7916079.963  1708778.450    ops/s
AddingToList            thrpt        10  7931479.667   966331.036    ops/s
GuavaImmutable          thrpt        10  9021621.880   845936.861    ops/s

结论

• 如果您只从列表中获取一次不同的项目,并且列表不是很长,则这些方法中的任何一种都应该足够.

• 最有效的一般方法来自第三方库:GS Collections和Guava表现令人钦佩.

• 在选择性能最佳的方法时,您可能需要考虑列表的大小以及可能的重复次数.

• 只有当值不在其中时才添加到新列表的天真方法适用于小型列表,但只要在输入列表中有多个值,它就会执行所尝试的最差方法.

• Guava ImmutableSet.copyOf(listInts).asList()方法在大多数情况下运行速度最快.但请注意以下限制:返回的列表是Immutable,输入列表不能包含空值.

• 该HashSet方法执行最好的非第三方方法,通常比Java 8流更好,但重新排序整数(根据您的用例可能会或可能不是一个问题).

• 该LinkedHashSet方法保持了排序,但不出所料通常比HashSet方法更糟糕.

• 当使用具有复杂HashCode计算的数据类型列表时,HashSet和LinkedHashSet方法都会表现得更差,如果您尝试Foo从a中选择不同的s ,那么您自己的分析也是如此List<Foo>.

• 如果您已经将GS Collections作为依赖项,那么它的表现非常好,并且比ImmutableList Guava方法更灵活.如果您没有将它作为依赖项,那么如果选择不同项目的性能对应用程序的性能至关重要,则值得考虑添加它.

• 令人失望的是Java 8流似乎表现得相当糟糕.编码distinct()调用的方式可能比我使用的方式更好,因此评论或其他答案当然是受欢迎的.

NB.我不是MicroBenchmarking的专家,所以如果有人发现我的结果或方法有缺陷,请通知我,我会尽力纠正答案.

Answer 2

向支票添加价值时listInts：

int valueToAdd;
//...
if (!listInts.contains(valueToAdd)) {listInts.add(valueToAdd)}

如果您有一个现有列表，请使用 for-each 语句将该列表中的所有值复制到您希望“不同”的新列表：

List<Integer> listWithRepeatedValues;
List<Integer> distinctList;
//...
for (Integer i : listWithRepeatedValues) {
    if (!listInts.contains(valueToAdd)) {distinctList.add(i);}
}