带有用于保持计数排序的索引的 PriorityQueue

Question

我在Java中经常遇到的一个问题（通常是在编写计算语言学代码时）是需要计算数据集中某些项目的出现次数，然后根据它们的数量对项目进行排序。最简单的具体例子是字数统计：我需要统计文本文件中每个字词出现的次数，然后根据次数对字词进行排序，找出最常用的字词。

不幸的是，Java 似乎没有适合此任务的数据结构。我需要在计数时将单词用作集合的索引，以便每次读取单词时都能有效地查找正确的计数器以增加，但我要排序的值是计数，而不是单词。

Map<String, Integer> 提供了查找与单词关联的计数所需的界面，但地图只能按其键排序（即 TreeMap）。 PriorityQueue 是一个很好的堆实现，它将根据您提供的任何比较器进行排序，但它无法提供通过某种索引访问元素的方法，也无法更新和重新堆化元素（除了通过删除并添加）。它的单一类型参数也意味着我需要将单词和它们的计数放在一个对象中才能使用它。

我现在的"solution"是在统计的时候把计数存到一个Map里，然后全部copy到一个PriorityQueue里排序：

Map<String, Integer> wordCounts = countStuff();
PriorityQueue<NamedCount> sortedCounts = new PriorityQueue<>(wordCounts.size(),
                                             Collections.reverseOrder());
for(Entry<String, Integer> count : wordCounts.entrySet()) {
    sortedCounts.add(new NamedCount(count.getKey(), count.getValue()));
}

（请注意，NamedCount 只是一个简单的 pair<string, int>，它实现了 Comparable 来比较整数）。但这是低效的，尤其是因为数据集可能非常大，并且在内存中保留两份计数集副本是一种浪费。

有什么方法可以让我随机访问 PriorityQueue 中的对象，这样我就可以只在 PriorityQueue 中存储一份计数副本，并在更新它们时重新堆化它们？使用将 "pointers" 保留到 PriorityQueue<NamedCount> 中的对象的 Map<String, NamedCount> 有意义吗？

Answer 1

如果你可以使用像 Guava 这样的第三方库，Multiset 是专门为解决这个问题而设计的：

Multiset<String> multiset = HashMultiset.create();
for (String word : words) {
  multiset.add(word);
}
System.out.println(Multisets.copyHighestCountFirst(multiset));

Answer 2

首先，对于基础数据结构，通常Guava的Multiset<String>优于Map<String, Integer>，就像Set<String>优于Map<String, Boolean>一样。它更干净 API 并封装了递增。

现在，如果这是我，我会实现一个自定义 Multiset，它添加一些额外的逻辑来索引计数，return 它们。像这样：

class IndexedMultiset<T extends Comparable<T>> extends ForwardingMultiset<T> {

    private final Multiset<T> delegate = HashMultiset.create();
    private final TreeMultimap<Integer, T> countIndex = TreeMultimap.create();

    @Override
    protected Multiset<T> delegate() {
        return delegate;
    }


    @Override
    public int add(T element, int occurrences) {
        int prev = super.add(element, occurrences);
        countIndex.remove(prev, element);
        countIndex.put(count(element), element);
        return prev;
    }

    @Override
    public boolean add(T element) {
        return super.standardAdd(element);
    }

    //similar for remove, setCount, etc


}

然后我会根据计数添加您需要的任何查询功能。例如，按降序检索 word/count 对的迭代可能看起来像这样：

public Iterable<CountEntry<T>> descendingCounts() {
    return countIndex.keySet().descendingSet().stream()
            .flatMap((count) -> countIndex.get(count).stream())
            .map((element) -> new CountEntry<>(element, count(element)))
            .collect(Collectors.toList());
}

public static class CountEntry<T> {
    private final T element;
    private final int count;

    public CountEntry(T element, int count) {
        this.element = element;
        this.count = count;
    }

    public T element() {
        return element;
    }

    public int count() {
        return count;
    }

    @Override
    public String toString() {
        return element + ": " + count;
    }
}

而且都会这样使用：

public static void main(String... args) {
    IndexedMultiset<String> wordCounts = new IndexedMultiset<>();

    wordCounts.add("foo");
    wordCounts.add("bar");
    wordCounts.add("baz");
    wordCounts.add("baz");

    System.out.println(wordCounts.descendingCounts()); //[baz: 2, bar: 1, foo: 1]


    wordCounts.add("foo");
    wordCounts.add("foo");
    wordCounts.add("foo");

    System.out.println(wordCounts.descendingCounts()); //[foo: 4, baz: 2, bar: 1]
}

带有用于保持计数排序的索引的 PriorityQueue

PriorityQueue with indices for keeping counts sorted

java

sorting

heap

counting