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

Question

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

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

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

我目前的“解决方案”是在计数时将计数存储在 Map 中，然后将它们全部复制到 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 中存储一份计数副本，并在更新它们时重新堆化？使用 Map<String, NamedCount> 有意义吗？保留指向 PriorityQueue<NamedCount> 中对象的“指针” ？

Answer 1

首先，对于基础数据结构，典型的是Guava的 Multiset<String> 优于 Map<String, Integer>与 Set<String> 相同优于 Map<String, Boolean> .它是一个更简洁的 API，并且封装了递增。

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

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


}

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

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]
}