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

如果我有:

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

在Java中,什么是创建List listDistinctInts的有效方法, List listDistinctInts包含List listDistinctInts中的不同值?

我的想法是创建一个Set setInts其中包含Set setInts中的所有值,然后调用List listDistinctInts = new ArrayList(setInts);

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

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

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

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

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

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

我现在已经从提供的优秀答案MicroBenchmarked大多数提议的选项。 像大多数非平凡的表现相关的问题一样,最好的答案是“它取决于”

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

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


1. Java 8 Stream – 使用stream()的解决方案如果使用Java8,我已经预测了它的可能性:

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

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

缺点 需要Java 8


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

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

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

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


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

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

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

cons 需要第三方库和FastList而不是常规List


4. GS集合适应 – FastList解决方案并没有完全比较,因为它需要传递给方法的FastList而不是一个好的’ ArrayList所以我还测试了Craig提出的适配器方法:

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

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

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


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

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

专业人士 据说非常快,适用于Java 7或8

cons 返回一个Immutable List ,不能处理输入列表中的空值,并需要第三方库


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

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

pros 在Java 7和8中工作,没有第三方依赖

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


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

 public List testLinkedHashSet(List listInts) { return new ArrayList(new LinkedHashSet(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计算的数据类型列表时, HashSetLinkedHashSet方法都会表现更差,因此如果您尝试从List选择不同的Foo ,请执行自己的分析。

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

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

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

如果您正在使用Eclipse Collections (以前称为GS Collections ),则可以使用distinct()方法。

 ListIterable listInts = FastList.newListWith(1, 1, 3, 77, 2, 19, 77, 123, 14, 123); Assert.assertEquals( FastList.newListWith(1, 3, 77, 2, 19, 123, 14), listInts.distinct()); 

使用distinct()而不是转换为Set然后返回List的优点是distinct()保留了原始List的顺序,保留了每个元素的第一次出现。 它是通过使用Set和List实现的。

 MutableSet seenSoFar = UnifiedSet.newSet(); int size = list.size(); for (int i = 0; i < size; i++) { T item = list.get(i); if (seenSoFar.add(item)) { targetCollection.add(item); } } return targetCollection; 

如果无法将原始List转换为GS Collections类型,则可以使用ListAdapter获取相同的API。

 MutableList distinct = ListAdapter.adapt(integers).distinct(); 

没有办法避免创建Set。 尽管如此,UnifiedSet比HashSet更有效,因此会有一些速度优势。

如果您想要的只是不同项目的数量 ,那么在不创建列表的情况下创建集合会更有效。

 Verify.assertSize(7, UnifiedSet.newSet(listInts)); 

Eclipse Collections 8.0需要Java 8. Eclipse Collections 7.x适用于Java 8,但只需要Java 5。

注意:我是Eclipse集合的提交者。

您应该尝试new LinkedList(new HashSet(listInts))

番石榴可以是您的选择:

 ImmutableSet set = ImmutableSet.copyOf(listInts); 

API非常优化。

它比listInts.stream().distinct()new LinkedHashSet<>(listInts)

listInts添加值时检查:

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

如果您有一个现有列表,请使用for-each语句将该列表中的所有值复制到您想要“不同”的新值:

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

别担心。 使用HashSet是一种非常简单有效的方法来消除重复:

  Set uniqueList = new HashSet<>(); uniqueList.addAll(listInts); // Add all elements eliminating duplicates for (int n : uniqueList) // Check the results (in no particular order) System.out.println(n); System.out.println("Number distinct values: " + uniqueList.size()); 

在更具体的情况下,只是在已知可能值的范围的情况下,不是很大,而listInts非常大。
计算列表中我能想到的唯一条目数的最有效方法是:

  boolean[] counterTable = new boolean[124]; int counter = 0; for (int n : listInts) if (!counterTable[n]) { counter++; counterTable[n] = true; } System.out.println("Number of distinct values: " + counter); 

这应该工作:

yourlist.stream()。map(覆盖equals的包装器和hashchode方法:: new).distinct()。map(上面定义的包装器::返回最终输出的方法).collect(Collectors.toList());

Interesting Posts