logo标签列表

Java集合中计算出现次数的优雅方法

javadictionarycollectionscount
32

给定一组可能包含重复元素的对象集合，我想得到每个对象出现次数的计数。我通过初始化一个空的 Map，然后遍历 Collection 并将对象映射到其计数（每次在 map 中已经包含该对象时递增计数）来实现此目标。

public Map<Object, Integer> countOccurrences(Collection<Object> list) {
    Map<Object, Integer> occurrenceMap = new HashMap<Object, Integer>();
    for (Object obj : list) {
        Integer numOccurrence = occurrenceMap.get(obj);
        if (numOccurrence == null) {
            //first count
            occurrenceMap.put(obj, 1);
        } else {
            occurrenceMap.put(obj, numOccurrence++);
        }
    }
    return occurrenceMap;
}

这看起来对于简单的计算出现次数逻辑来说太啰嗦了。有没有更优雅/更短的方法来完成这个任务？我可以考虑完全不同的算法或允许更短代码的Java语言特定功能。

6
统计出现次数并不是那么简单，你的代码似乎是你能做到的最好的。 - Henry
1
为了获得所有元素发生的完整列表，你必须遍历整个集合，我认为你的实现是不错的。 - hovanessyan
1
你为什么认为这是啰嗦的？在我看来很清晰。这就是Java的样子。 - Joe
2
@DariuszWawer 无论如何都只有一次迭代，排序在这里不会有任何影响。 - NimChimpsky
1
这段代码有错误。 else 语句中应该是 ++numOccurrence，否则我们会用1覆盖出现次数。 - Jernej Jerin
显示剩余5条评论
12个回答
21

现在让我们尝试一些Java 8的代码：

static public Map<String, Integer> toMap(List<String> lst) {
    return lst.stream()
            .collect(HashMap<String, Integer>::new,
                    (map, str) -> {
                        if (!map.containsKey(str)) {
                            map.put(str, 1);
                        } else {
                            map.put(str, map.get(str) + 1);
                        }
                    },
                    HashMap<String, Integer>::putAll);
}

static public Map<String, Integer> toMap(List<String> lst) {
    return lst.stream().collect(Collectors.groupingBy(s -> s,
                                  Collectors.counting()));
}

我认为这段代码更加优雅。

也许我搜索的术语不对，但这个Java 8示例在其他地方真的很难找到，感谢您的发布！ - Jason
只是好奇为什么您提供冗长的方法和非冗长的方法？请注意，静态导入Collectors.*也使其更简洁，在许多情况下不需要使用静态方法，因为它通常可以附加到现有流上。 - Brett Ryan
3
使用累加器可以使代码更加优雅，例如：(map, str) -> map.merge(str, 1, (old, one) -> old+one)。 - Jan Martiška
1
Collectors.counting 会生成一个 Long，因此返回类型应为 Map<String,Long>。 - Witbrock
1
补充@Witbrock的评论：如果你想要一个“Map<String，Integer>”，你可以使用“Collectors.reducing(0，e -> 1，Integer :: sum)”代替“Collectors.counting()”。 - Yurim
20

请查看Guava的Multiset，它基本上就是你要找的东西。

不幸的是，它没有一个addAll（Iterable iterable）函数，但是对集合进行简单的循环，并调用add（E e）足以轻松解决问题。

编辑

我犯了个错误，它确实有一个addAll方法 - 因为它实现了Collection接口。

另外，Iterables.addAll(Collection, Iterable)。 - Louis Wasserman
14

我知道这是一个老问题，但在Java 8中我找到了一种更优雅的方式来计算这些投票，希望你喜欢。

Map<String, Long> map = a.getSomeStringList()
            .stream()
            .collect(Collectors.groupingBy(
                    Function.identity(),
                    Collectors.counting())
            );

如有任何错误，请留言评论。

7
5
Collections.frequency 适用于计算特定对象的出现次数，但是 OP 需要计算所有对象的出现次数，这使得该方法非常低效。 - Hui Zheng
啊，我不知道这个方法。然而在我的情况下，我想在一次遍历中计算集合中所有唯一对象的出现次数。 - fo_x86
我同意，这很低效。这只是来自本地Java库的一种方法建议，用于完成这项任务。我不知道其他解决此问题的方法，请使用外部方法。 - Vic
3

这里有一篇关于Java计数器的好文章：http://www.programcreek.com/2013/10/efficient-counter-in-java/，它更注重效率而非优雅。

获胜者是这个：

HashMap<String, int[]> intCounter = new HashMap<String, int[]>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
    for (String a : sArr) {
        int[] valueWrapper = intCounter.get(a);

        if (valueWrapper == null) {
            intCounter.put(a, new int[] { 1 });
        } else {
            valueWrapper[0]++;
        }
    }
}
2

对于Java来说，这并不冗长。您可以使用 TObjectIntHashMap：

public <T> TObjectIntHashMap<T> countOccurrences(Iterable<T> list) {
    TObjectIntHashMap<T> counts = new TObjectIntHashMap<T>();
    for (T obj : list) counts.adjustOrPut(obj, 1, 1);
    return counts;
}
这个选项比Guava更好吗？ - NimChimpsky
如果你说“更好”的意思是更快，那么是的。MultiSet可能更清晰。 - Peter Lawrey
1
请参考以下解决方案，以计算集合中每个元素的数量。
对于整数值：
List<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(2);
list.add(5);
list.add(1);
list.add(8);
list.add(0);
list.add(2);
list.add(32);
list.add(72);
list.add(0);
list.add(13);
list.add(32);
list.add(73);
list.add(22);
list.add(73);
list.add(73);
list.add(21);
list.add(73);

HashSet<Integer> set = new HashSet<>();

for (int j = 0; j < list.size(); j++) {
    set.add(list.get(j));
}

Iterator<Integer> itr = set.iterator();
while (itr.hasNext()) {
    int a = itr.next();
    System.out.println(a + " : " + Collections.frequency(list, a));
}

输出：

0 : 2
32 : 2
1 : 1
2 : 2
3 : 1
5 : 1
21 : 1
22 : 1
8 : 1
72 : 1
73 : 4
13 : 1

字符串值：

List<String> stringList = new ArrayList<>();
stringList.add("ABC");
stringList.add("GHI");
stringList.add("ABC");
stringList.add("DEF");
stringList.add("ABC");
stringList.add("GHI");

HashSet<String> setString = new HashSet<>();

for (int j = 0; j < stringList.size(); j++) {
    setString.add(stringList.get(j));
}

Iterator<String> itrString = setString.iterator();
while (itrString.hasNext()) {
    String a = itrString.next();
    System.out.println(a + " :::  " + Collections.frequency(stringList, a));
}

输出：

ABC :::  3
DEF :::  1
GHI :::  2
1
我很惊讶没有人提供这种简单易懂的解决方案。你可以直接使用Map#getOrDefault()。
 public Map<Object, Integer> countOccurrences(Collection<Object> list){
      Map<Object, Integer> occurrenceMap = new HashMap<Object, Integer>();
      for(Object obj: list){
          occurrenceMap.put(obj, occurrenceMap.getOrDefault(obj, 0) + 1);
      }
      return occurrenceMap;
 }

它能够完美解决您所遇到的问题，并且消除了笨重的if..else语句。
1
我希望没有人发布这个答案，这样我就可以写了，但你做了 :'D。 - Gregordy
0
你可以从Eclipse Collections中使用Bag。
Iterable<Object> iterable = Arrays.asList("1", "2", "2", "3", "3", "3");
MutableBag<Object> counts = Bags.mutable.withAll(iterable);

Assertions.assertEquals(1, counts.occurrencesOf("1"));
Assertions.assertEquals(2, counts.occurrencesOf("2"));
Assertions.assertEquals(3, counts.occurrencesOf("3"));
Assertions.assertEquals(0, counts.occurrencesOf("4"));
MutableBagFactory 接口上的 withAll 方法接受一个 Iterable 作为参数，并返回一个 MutableBag。在 MutableBag 上的 occurrencesOf 方法返回一个 int，即元素出现的次数。与 Map 不同，如果 Bag 不包含元素，则不会返回 null。相反，occurrencesOf 方法将返回 0。 MutableBag 是一个 Collection，因此它具有一个接受 Collection 作为参数的 addAll 方法。
counts.addAll(Arrays.asList("4", "4", "4", "4"));
Assertions.assertEquals(4, counts.occurrencesOf("4"));

MutableBag 还有一个 addAllIterable 方法，它接受一个 Iterable。

Stream<Object> stream = Stream.of("1", "2", "3", "4");
counts.addAllIterable(stream::iterator);

Assertions.assertEquals(2, counts.occurrencesOf("1"));
Assertions.assertEquals(3, counts.occurrencesOf("2"));
Assertions.assertEquals(4, counts.occurrencesOf("3"));
Assertions.assertEquals(5, counts.occurrencesOf("4"));

Eclipse Collections中的HashBag实现由ObjectIntHashMap支持，因此int计数不会被装箱。有一篇博客提供了有关Eclipse Collections中Bag类型的更多信息，链接在这里。

注意：我是Eclipse Collections的提交者。

0
作为对与@NimChimpsky的讨论的回应，这里提供一种使用排序集合进行计数的替代方法，该方法更快 - 我正在尝试证明这一点。根据元素数量和“sortFactor”（请参见代码），速度差异会有所不同，但是对于运行环境中大量对象（而非调试）来说，我的方法相对于默认方法具有20-30％的速度提升。 以下是两种方法的简单测试类。
public class EltCountTest {

    final static int N_ELTS = 10000;

    static final class SampleCountedObject implements Comparable<SampleCountedObject>
    {
        int value = 0;

        public SampleCountedObject(int value) {
            super();
            this.value = value;
        }

        @Override
        public int compareTo(SampleCountedObject o) {
            return (value == o.value)? 0:(value > o.value)?1:-1; // just *a* sort
        }

        @Override
        public int hashCode() {
            return value;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof SampleCountedObject) {
                return value == ((SampleCountedObject)obj).value;
            }
            return false;
        }

        @Override
        public String toString() {
            return "SampleCountedObject("+value+")";
        }
    }

    /**
     * * @param args
     */
    public static void main(String[] args) {
        int tries = 10000;
        int sortFactor = 10;
        Map<SampleCountedObject, Integer> map1 = null;
        Map<SampleCountedObject, Integer> map2 = null;

        ArrayList<SampleCountedObject> objList = new ArrayList<EltCountTest.SampleCountedObject>(N_ELTS);

        for (int i =0, max=N_ELTS/sortFactor; i<max; i++){
            for (int j = 0; j<sortFactor; j++) {
                objList.add(new SampleCountedObject(i));
            }
        }

        long timestart = System.nanoTime();
        for (int a=0; a< tries; a++) {
            map1 = method1(objList);
        }
        System.out.println();
        long timeend1 = System.nanoTime();
        System.out.println();

        for (int a=0; a< tries; a++) {
            map2 = metod2(objList);
        }
        long timeend2 = System.nanoTime();
        System.out.println();


        long t1 = timeend1-timestart;
        long t2 = timeend2-timeend1;
        System.out.println("\n        org count method=["+t1+"]\nsorted collection method=["+t2+"]"+
                 "\ndiff=["+Math.abs(t1-t2)+"] percent=["+(100d*t2/t1)+"]");

        for (SampleCountedObject obj: objList) {
            int val1 = map1.get(obj);
            int val2 = map2.get(obj);
            if (val1 != val2) {
                throw new RuntimeException("val1 != val2 for obj "+obj);
            }
        }
        System.out.println("veryfy OK");

    }

    private static Map<SampleCountedObject, Integer> method1(ArrayList<SampleCountedObject> objList) {
        Map<SampleCountedObject, Integer> occurenceMap = new HashMap<SampleCountedObject, Integer>();

        for(SampleCountedObject obj: objList){
             Integer numOccurrence = occurenceMap.get(obj);
             if(numOccurrence == null){
                 occurenceMap.put(obj, 1);
             } else {
                 occurenceMap.put(obj, ++numOccurrence);
             }
        }
        return occurenceMap;
    }

    private static Map<SampleCountedObject, Integer> metod2(ArrayList<SampleCountedObject> objList) {
        Map<SampleCountedObject, Integer> occurenceMap = new HashMap<SampleCountedObject, Integer>();
        int count = 0;
        Collections.sort(objList);
        SampleCountedObject prevObj = objList.get(0);

        for(SampleCountedObject obj: objList){
            if (!obj.equals(prevObj)) {
                occurenceMap.put(prevObj, count);
                count = 1;
            } else {
                count ++;
            }
            prevObj = obj;
        }
        occurenceMap.put(prevObj, count);
        return occurenceMap;
    }
}

请注意，我还会验证结果是否相同，并在打印测试结果后进行验证。
有趣的是，在调试运行中，我的方法比原始方法慢得多（取决于集合中元素的数量，通常为10-20%）。
你正在生成一个已经排序好的列表，所以你甚至没有看到进行排序所带来的真正性能损失。对于第一种方法，时间复杂度是O(n)。而你的时间复杂度是O(n)，再加上排序方法，这可能是O(n log n)，或者像O(n^2)这样糟糕。基本上除了排序之外（你做的）就是用equals()替换了哈希映射get()。我真的不认为这会带来多少节省（它们都是O(1)），除非你有专门为你的方法优化的数据（在现实世界中可能永远不会出现）。 - tobii
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接