如何用JavaScript实现top n 问题？ 如python的most_common()

Question

我们知道python内建模块的collections有很多好用的操作。
比如：

from collections import Counter
#统计字符串
# top n问题
user_counter = Counter("abbafafpskaag")
print(user_counter.most_common(3)) #[('a', 5), ('f', 2), ('b', 2)]
print(user_counter['a']) # 5

如果用js你会怎样实现？或者有造好的轮子里面有这样的操作？

python里面实现most_common:

    def most_common(self, n=None):
        '''List the n most common elements and their counts from the most
        common to the least.  If n is None, then list all element counts.

        >>> Counter('abcdeabcdabcaba').most_common(3)
        [('a', 5), ('b', 4), ('c', 3)]

        '''
        # Emulate Bag.sortedByCount from Smalltalk
        if n is None:
            return sorted(self.items(), key=_itemgetter(1), reverse=True)
        return _heapq.nlargest(n, self.items(), key=_itemgetter(1))

这里用到了个 _heapq 堆数据结构 也就是说它是堆来解决top n问题的，而不是遍历。 js有哪些类似的轮子

｀另注：｀遍历的方法可以通过str.split()实现

其实这个问题的实质是　使用堆实现Top K算法（JS实现）

Answer 1

我没有用过，应该有，毕竟 npm 里那么多库，不过没检索过就是了。

我觉得对于 JS 来说，最大的问题是你不好确定是

arr.sort((a, b) => a < b);
return arr.slice(0, 3);

这样比较快还是手写一个堆排序比较快。

另外就这个问题而言，我觉得直接遍历一下字符串也行，复杂度是 O(n)。因为 JS 里也是没有 counter 方法的，哈哈。

Answer 2

如果只是对ASCII字符串（甚至是所有unicode字符串）的话，使用堆真不比直接排序来的快（堆的插入操作也是logn，n个元素同样需要nlogn的时间。）。

python使用堆来实现是为了在不确定目标范围的情况下（比如并不限定为字符串，其可能的对象范围可以非常大），这时候大顶堆的优势就提现出来了。

Answer 3

JS 原生库里面没有priority queue， 这个得自己实现。说着找library。