Python实现有序单词频次统计超时，如何优化缩短运行时间？

你的代码超时以及不符合需求的核心问题有两个：

• 时间复杂度过高：list.count()的单次执行时间复杂度为O(n)，当你对近1e5个不同单词逐个调用该方法时，总时间复杂度会达到O(1e10)，远远超出了题目的时间限制。
• 逻辑不符合输出要求：set是无序集合，转换为列表后会丢失单词首次出现的顺序，且你最后对次数做了倒序排序，完全不符合题目要求的输出规则。

我们可以利用Python3.7+版本后字典默认保留插入顺序的特性，单次遍历单词列表即可完成频次统计，总时间复杂度为O(n)。同时大批量输入场景下，使用sys.stdin一次性读取所有输入的速度远快于循环调用input()。
优化后的代码如下：

import sys
from collections import Counter

def main():
    # 一次性读取所有输入，避免多次IO消耗
    all_lines = sys.stdin.read().splitlines()
    n = int(all_lines[0])
    words = all_lines[1: n+1]
    # Counter会按单词首次出现顺序统计频次
    count_dict = Counter(words)
    print(len(count_dict))
    print(' '.join(map(str, count_dict.values())))

if __name__ == "__main__":
    main()

如果需要兼容更早的Python版本，可以手动用普通字典实现统计，逻辑完全一致：

import sys

def main():
    all_lines = sys.stdin.read().splitlines()
    n = int(all_lines[0])
    count_dict = {}
    for i in range(1, n+1):
        word = all_lines[i]
        if word in count_dict:
            count_dict[word] += 1
        else:
            count_dict[word] = 1
    print(len(count_dict))
    print(' '.join(map(str, count_dict.values())))

if __name__ == "__main__":
    main()

内容的提问来源于stack exchange，提问作者Jeet B. Lahiri