替换list为deque后仍报超时？按输入顺序统计词频的超时问题排查

• 超时问题完全不是list的append方法导致的，换成deque也解决不了问题：list.append是均摊O(1)时间复杂度的操作，deque的两端增删同样是O(1)，这类操作的开销根本达不到触发测试用例超时的量级。
• 真正的性能瓶颈来自两段嵌套的线性遍历操作，把整体时间复杂度拖到了O(n²)，在大n的测试用例下必然超时：
  1. 循环内判断i not in u_list：普通列表的成员检查是从头遍历匹配的线性操作，单次判断时间复杂度O(k)（k为当前已存入的不重复单词数）
  2. 遇到不重复单词时调用的ar.count(i)：该方法本身需要把整个输入列表从头到尾扫一遍统计匹配次数，单次操作的时间复杂度就是O(n)
     举个极端场景：如果测试用例输入10万条完全不重复的单词，光count操作的总遍历量就能达到100亿次量级，不管你用什么结构存单词，这部分计算量都不可能在时限内跑完。

• 替换核心逻辑为O(n)时间复杂度的有序哈希实现
  Python 3.7及以上版本内置的dict已经是插入有序的结构，天然满足“按输入出现顺序记录频次”的要求，同时哈希表的成员查找是O(1)复杂度，可以彻底消掉之前的两次线性遍历开销。
  可直接运行的实现代码：

  import sys
  # 批量读取输入，避免逐行input的IO开销
  lines = sys.stdin.read().split()
  n = int(lines[0])
  freq = {}
  for i in range(1, n+1):
      word = lines[i]
      freq[word] = freq.get(word, 0) + 1
  print(len(freq))
  print(*freq.values())
  

• 别忽略IO层面的隐性开销
  逐行调用原生input()在超大输入规模下本身就是主要超时诱因：每次input调用都会触发一次用户态到内核态的IO切换，批量一次性读完全部输入、再拆分内容的方式，能把IO开销压到最低，是算法题场景下的通用优化手段。
• 为什么替换为deque没有效果
  deque仅优化了序列两端的增删操作，没有改变成员查找的线性时间复杂度，也没有替代掉list.count()这个O(n)的方法，只优化了无足轻重的环节，自然解决不了超时问题。

内容的提问来源于stack exchange，提问作者Jerin06