Mat*_*ugh 20 java list distinct-values java-7 java-8
如果我有:
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方法之间的性能差异,或者是否有更好的技术？
Mat*_*ugh 31
我现在已经根据提供的优秀答案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的专家,所以如果有人发现我的结果或方法有缺陷,请通知我,我会尽力纠正答案.
向支票添加价值时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);}
}