鍍金池/ 問答/人工智能  Java  Python  HTML/ 如何用JavaScript實現(xiàn)top n 問題？ 如python的most_co

如何用JavaScript實現(xiàn)top n 問題？ 如python的most_common()

我們知道python內建模塊的collections有很多好用的操作。
比如：

from collections import Counter
#統(tǒng)計字符串
# top n問題
user_counter = Counter("abbafafpskaag")
print(user_counter.most_common(3)) #[('a', 5), ('f', 2), ('b', 2)]
print(user_counter['a']) # 5

如果用js你會怎樣實現(xiàn)？或者有造好的輪子里面有這樣的操作？

python里面實現(xiàn)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 堆數(shù)據(jù)結構 也就是說它是堆來解決top n問題的，而不是遍歷。 js有哪些類似的輪子

｀另注：｀遍歷的方法可以通過str.split()實現(xiàn)

圖片描述

其實這個問題的實質是　使用堆實現(xiàn)Top K算法（JS實現(xiàn)）

回答
編輯回答
醉淸風

JS 原生庫里面沒有priority queue， 這個得自己實現(xiàn)。說著找library。

2018年5月11日 06:25
編輯回答
舊言

如果只是對ASCII字符串（甚至是所有unicode字符串）的話，使用堆真不比直接排序來的快（堆的插入操作也是logn，n個元素同樣需要nlogn的時間。）。

python使用堆來實現(xiàn)是為了在不確定目標范圍的情況下（比如并不限定為字符串，其可能的對象范圍可以非常大），這時候大頂堆的優(yōu)勢就提現(xiàn)出來了。

2018年2月25日 21:10
編輯回答
念初

我沒有用過，應該有，畢竟 npm 里那么多庫，不過沒檢索過就是了。

我覺得對于 JS 來說，最大的問題是你不好確定是

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

這樣比較快還是手寫一個堆排序比較快。

另外就這個問題而言，我覺得直接遍歷一下字符串也行，復雜度是 O(n)。因為 JS 里也是沒有 counter 方法的，哈哈。

2018年8月31日 01:03