有没有更好的方法来查找列表中最常见的单词（仅限于Python）

Question

考虑到这个问题的一个简单实现，我正在寻找一种在Python列表中查找最常见单词的显著更快的方法。作为Python访谈的一部分，我收到了这样的反馈：这个实现效率太低，基本上是失败的。后来，我尝试了许多我发现的算法，只有一些基于heapsearch的解决方案更快一些，但并不是非常快（当扩展到数千万个项目时，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)（其中n = len(words)），使用堆不会改变这一点。在

有更快的近似解。。。在

Answer 2

函数调用和全局命名空间搜索的开销更大。在

您的stupid函数对单词列表中的每个元素进行2次函数调用。您的max调用中的第二个是完全可以避免的，即迭代dict的键，然后对于每个键使用dict.get查找值，当您可以迭代键值对时，这是一个明显的低效率。在

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

def most_frequent(words):
  ## Build the frequency dict
  freqs = {}
  for w in words:
    if w in freqs:
      freqs[w] += 1
    else:
      freqs[w] = 1
  ## Search the frequency dict
  m_k = None
  m_v = 0
  for k, v in freqs.iteritems():
    if v > m_v:
      m_k, m_v = k, v
  return m_k, m_v

---

使用user1952500的单通建议，这在您的大型样本集上表现如何？在

^{pr2}$

对于多个最常见的值来说，这有一个小小的优点，即稳定。在

---

使用cd4{生成所有建议的样本：

def word_frequency_version1(words):
  """Petar's initial"""
  freqs = {}
  for w in words:
    freqs[w] = freqs.get(w, 0) + 1
  return max(freqs, key=freqs.get)

def word_frequency_version2(words):
  """Matt's initial"""
  ## Build the frequency dict
  freqs = {}
  for w in words:
    if w in freqs:
      freqs[w] += 1
    else:
      freqs[w] = 1
  ## Search the frequency dict
  m_k = None
  m_v = 0
  for k, v in freqs.iteritems():
    if v > m_v:
      m_k, m_v = k, v
  return m_k, m_v

def word_frequency_version3(words):
  """Noting max as we go"""
  freq = {}
  m_k = None
  m_v = 0
  for w in words:
    if w in freq:
      v = freq[w] + 1
    else:
      v = 1
    freq[w] = v
    if v > m_v:
      m_k = w
      m_v = v
  return m_k, m_v

from collections import Counter
def word_frequency_version4(words):
  """Built-in Counter"""
  c = Counter(words)
  return c.most_common()[0]


from multiprocessing import Pool
def chunked(seq,count):
  v = len(seq) / count
  for i in range(count):
    yield seq[i*v:v+i*v]

def frequency_map(words):
  freq = {}
  for w in words:
    if w in freq:
      freq[w] += 1
    else:
      freq[w] = 1
  return freq

def frequency_reduce(results):
  freq = {}
  for result in results:
    for k, v in result.iteritems():
      if k in freq:
        freq[k] += v
      else:
        freq[k] = v
  m_k = None
  m_v = None
  for k, v in freq.iteritems():
      if v > m_v:
        m_k = k
        m_v = v
  return m_k, m_v

# def word_frequency_version5(words,chunks=5,pool_size=5):
#   pool = Pool(processes=pool_size)
#   result = frequency_reduce(pool.map(frequency_map,chunked(words,chunks)))
#   pool.close()
#   return result

def word_frequency_version5(words,chunks=5,pool=Pool(processes=5)):
  """multiprocessing Matt's initial suggestion"""
  return frequency_reduce(pool.map(frequency_map,chunked(words,chunks)))

def word_frequency_version6(words):
  """Petar's one-liner"""
  return max(set(words),key=words.count)


import timeit
freq1 = timeit.Timer('func(words)','from __main__ import words, word_frequency_version1 as func; print func.__doc__')
freq2 = timeit.Timer('func(words)','from __main__ import words, word_frequency_version2 as func; print func.__doc__')
freq3 = timeit.Timer('func(words)','from __main__ import words, word_frequency_version3 as func; print func.__doc__')
freq4 = timeit.Timer('func(words)','from __main__ import words, word_frequency_version4 as func; print func.__doc__')
freq5 = timeit.Timer('func(words,chunks=chunks)','from __main__ import words, word_frequency_version5 as func; print func.__doc__; chunks=10')
freq6 = timeit.Timer('func(words)','from __main__ import words, word_frequency_version6 as func; print func.__doc__')

结果：

>>> print "n={n}, m={m}".format(n=len(words),m=len(set(words)))
n=692766, m=34464
>>> freq1.timeit(10)
"Petar's initial"
3.914874792098999
>>> freq2.timeit(10)
"Matt's initial"
3.8329160213470459
>>> freq3.timeit(10)
"Noting max as we go"
4.1247420310974121
>>> freq4.timeit(10)
"Built-in Counter"
6.1084718704223633
>>> freq5.timeit(10)
"multiprocessing Matt's initial suggestion"
9.7867341041564941

注意事项：

• 我用multiprocessing.Pool实例作为kwarg进行作弊，以达到计时目的，因为我想避免池的启动成本，timeit不允许您指定清理代码。这是在一个“四”cpu虚拟机上运行的，我确信对于输入数据和cpu计数的某些值，多处理将更快。在
• 大多数情况下，返回频率最高的单词，如果第一名出现平局，这可能是随机的。在
• 最高频率的近似值可能更快（使用采样），但将是近似值。在
• 对于n*m的大值，应忽略版本6（一行程序）。在

Answer 3

from collections import Counter

word_counter = Counter(words)

word_counter是一个以单词为键、频率为值的字典，还有一个most_common()方法。在