java - 在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中) -无需先创建所有不同元素的列表或集合？

我对 native Java的实现方式最感兴趣，并且避免重新发明轮子，但是如果它们提供更好的清晰度或性能，则将考虑手动编写代码或库。我已经阅读了有关的问题 Java - Distinct List of Objects，但对于Java 7和8方法之间的性能差异还是是否存在更好的技术尚不完全清楚。

Answer 1

现在，我已从提供的出色答案中对大多数建议的选项进行了基准测试。像大多数与性能无关紧要的问题一样，关于哪个最好的答案是“取决于”。

我所有的测试都是使用JMH Java Microbenchmarking Harness执行的。

尽管我使用JDK 1.7进行了一些测试，但大多数测试都是使用JDK 1.8进行的，只是为了确保其性能没有太大差异(几乎相同)。我测试了到目前为止提供的答案中采用的以下技术:

1. Java 8流-如果使用Java8，我建议使用stream()解决方案:

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然后进行复制，没有第三方部门

缺点在构建列表时需要反复检查列表中是否存在现有值

3. GS Collections快速(现为Eclipse集合)- Craig P. Motlin使用 GS Collections library及其自定义列表类型 FastList提出的解决方案:

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

优点据说非常快速，简单的表达性代码，可在Java 7和8中使用

缺点需要第3方库和 FastList，而不是常规的 List<Integer>
4. GS Collections改编的-FastList解决方案不能完全按原样进行比较，因为它需要将 FastList传递给该方法，而不是好的 ArrayList<Integer>，因此我还测试了Craig建议的适配器方法:

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

优点不需要 FastList，可在Java 7和8中使用

缺点必须适应列表，所以可能表现不佳，需要第3方库

5. Guava ImmutableSet - Louis Wasserman在评论中建议使用 卢声远 Shengyuan Lu在其答案中使用 Guava提出的方法:

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

优点据说非常快，可以在Java 7或8中运行

缺点返回 Immutable List，无法处理输入列表中的null，并且需要第3方库

7. HashSet -我的初衷(也由 EverV0id， ulix和Radiodef推荐)

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

优点在Java 7和8中工作，没有第三方依赖

缺点不保留列表的原始顺序，必须构造集合然后复制到列表。

6. LinkedHashSet -因为 HashSet解决方案没有在原始列表中保留整数的顺序，所以我还测试了一个使用LinkedHashSet保留顺序的版本:

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

优点保留原始顺序，可在Java 7和8中使用，没有第三方依赖

缺点与常规 HashSet方法一样快

结果

这是我针对各种不同大小的 listInts的结果(结果从最慢到最快排序):

1.从ArrayList的0-50,000之间的100,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.从ArrayList的0到50之间随机抽取1000个整数(即中型列表，很多重复项)

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.从ArrayList的0到100之间随机抽取100个整数(即，小列表，某些副本)

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.从ArrayList的0到50之间随机抽取10个整数(即，很小的列表，很少重复)

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中选择不同的List<Foo>，那么请进行自己的分析。

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

令人失望的是，Java 8流的性能似乎很差。可能比我使用的方法更好的方式来编码distinct()调用，因此当然欢迎提出评论或其他答案。

注意我不是MicroBenchmarking的专家，所以如果有人发现我的结果或方法存在缺陷，请通知我，我将尽力纠正答案。