java - 在实时数据流中找到前 k 个频繁词

Question

我正在尝试使用 java 树集解决算法问题。

问题如下:

Find top k frequent words in realtime data stream.

Implement three methods for Topk Class:

TopK(k). The constructor.
add(word). Add a new word.
topk(). Get the current top k frequent words.

我的想法是使用 HashMap 来记住频率，并使用树集作为缓冲区。

我的实现通过了大部分情况，除了一个:

TopK(10)
add("aw")
add("fb")
add("fb")
topk()

答案应该是 [fb,aw] 但现在是 [fb,aw, fb] 但是，我的代码通过了如下测试用例:

    TopK(10)
    add("iiiiii")
    add("fb")
    add("fb")
    topk()

和

TopK(10)
add("fb")
add("fb")
topk()

我不知道出了什么问题，所以我在调用比较器时打印了一些值。它给了我这个:

 aw aw
11111111
fb aw
33333333
fb aw
33333333
fb aw
222222222
fb aw
222222222

这意味着，第二个“fb”与“aw”进行了两次比较，比较完成。我花了几个小时进行调试，但到目前为止我一无所获。

这是我的实现:

public class TopK {
    int size;
    HashMap<String, Integer> map;
    TreeSet<String> seen;
    public TopK(int k) {
        // do intialization if necessary
        size = k;
        seen = new TreeSet<String>(new Comparator<String>(){
            @Override
            public int compare(String str1, String str2){
                System.out.println(str1 + " "+ str2);
                if (str1.equals(str2)){
                    System.out.println("11111111");
                    return 0;
                }
                // important !https://www.jiuzhang.com/qa/7646/
                // 128 以后integer就不同了
                int number1 = map.get(str1);
                int number2 = map.get(str2);
                if (number1 != number2){
                    System.out.println("222222222");
                    return map.get(str1) - map.get(str2);
                } else {
                    System.out.println("33333333");
                    return str2.compareTo(str1);
                }
            }
        });
        map = new HashMap<String, Integer>();
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        if (!map.containsKey(word)){
            map.put(word, 0);
        }
        map.put(word, map.get(word) + 1);

        if (seen.contains(word)){
            seen.remove(word);
            seen.add(word);
        } else {
            seen.add(word);
            if (seen.size() > size){
                seen.pollFirst();
            }
        }
    }

    /*
     * @return: the current top k frequent words.
     */
    public List<String> topk() {
        // Write your code here
        List<String> results = new ArrayList<String>();
        Iterator it = seen.iterator();
        while(it.hasNext()) {
             String str = (String)it.next();
             results.add(0, str);
        }
        return results;
    }
}

Answer 1

我们的第一个线索是那个案例:

aw
fb
fb

失败但是:

iiiii
fb
fb

成功。

这只会因为以下行而发生:return str2.compareTo(str1); - 如果通过字符串比较出现的次数不同(这可以很容易地检查 - 请这样做) .

我能想到的唯一解释是 java TreeSet 的 contains 函数具有“优化”搜索，只搜索到元素应该出现的位置 - 如果您有顺序并且元素不在它应该出现的位置然后将其视为 TreeSet 中不存在(考虑应该对数组进行排序以检查您在 log(n) 中运行的数字，但在所有数组中都不存在 - 因此如果他存在于错误的位置，您将错过他)。

请注意，在检查 contains 函数之前，您更改了元素应该放置的位置。那么让我们看一下第 2 次迭代 - 我们有 fb 和 aw 在 map 中的值为 1。在 TreeSet 上，它们是 [fb,aw](因为字符串比较如前所述)。现在您更改 map 并且 fb 的值为 2 -> 它应该在最后一个位置但是 contains 函数与 aw 比较并思考它应该在它之后 - 但他是最后一个元素，所以它假设 fb 不存在，只需添加他 -> 这就是为什么你看到 2 比较 fb 和 aw - 一个用于 contain，一个用于 add。

希望这是可以理解的......