是否有更好的方法来查找列表中最常见的单词(仅限Python)

Question

考虑到问题的一个简单实现,我正在寻找一种更快的方法来找到Python列表中最常见的单词.作为Python访谈的一部分,我收到的反馈是,这种实现效率很低,基本上都是失败的.后来,我尝试了很多我发现的算法,只有一些基于堆栈的解决方案速度稍微快一些,但不是绝大多数(当缩放到数千万个项目时,heapsearch的速度提高了大约30%;在千万倍的长度上,它几乎是相同;使用timeit).

def stupid(words):
    freqs = {}
    for w in words:
        freqs[w] = freqs.get(w, 0) + 1
    return max(freqs, key=freqs.get)

由于这是一个简单的问题而且我有一些经验(虽然我无处算法大师或竞争编码器)我很惊讶.

当然,我想提高我的技能并学习解决问题的更好方法,所以你的意见将得到赞赏.

澄清重复状态:我的观点是找出实际上是否有更多(渐近)更好的解决方案,其他类似的问题已经选择了一个不太好的答案.如果这还不足以使问题变得独一无二,那么当然要关闭这个问题.

更新

谢谢大家的意见.关于访谈情况,我仍然认为手写搜索算法是预期的(可能更有效)和/或审阅者从另一种语言的角度评估代码,具有不同的常数因素.当然,每个人都可以拥有自己的标准.

对我来说重要的是验证我是否完全无能为力(我的印象是我不是)或者通常只写不是最好的代码.仍然有可能存在更好的算法,但如果它在这里为社区隐藏了几天,我就可以了.

我正在选择最受欢迎的答案 - 这样做似乎是公平的,尽管不止一个人提供有用的反馈意见.

次要更新

看起来使用defaultdict比使用'get'方法有明显的优势,即使它是静态别名的.

Answer 1

这听起来像是一个糟糕的面试问题，可能是面试官期望得到某个答案的情况。听起来她/他确实没有清楚地解释她/他在问什么。

您的解决方案是O(n)(where n = len(words))，并且使用堆不会改变这一点。

有更快的近似解...