实现一个高效的单词频率统计工具

题目

实现一个高效的单词频率统计工具

信息

• 类型：问答
• 难度：⭐⭐

考点

STL容器选择,迭代器使用,算法应用,性能分析

快速回答

实现高效单词频率统计的关键步骤：

• 使用std::unordered_map存储单词和频率（O(1)平均访问）
• 用std::istringstream分割字符串
• 遍历时使用const auto&避免拷贝
• 输出前用std::vector和std::sort按频率排序

核心代码示例：
unordered_map<string, size_t> wordCount;
for (const auto& word : words) ++wordCount[word];

解析

问题场景

处理大量文本时（如日志分析），需要统计不同单词的出现频率并按频率降序输出。要求时间复杂度O(n)统计，O(m log m)排序（m为唯一单词数）。

解决方案

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <sstream>

void countWords(const std::string& text) {
    // 1. 使用unordered_map统计频率
    std::unordered_map<std::string, size_t> wordCount;

    // 2. 分割字符串
    std::istringstream iss(text);
    std::string word;
    while (iss >> word) {
        // 3. 移除标点（可选）
        if (!word.empty() && ispunct(word.back())) 
            word.pop_back();

        // 4. 统一小写（可选）
        std::transform(word.begin(), word.end(), word.begin(), ::tolower);

        ++wordCount[word]; // O(1)操作
    }

    // 5. 转移到vector排序
    std::vector<std::pair<std::string, size_t>> sortedWords(wordCount.begin(), wordCount.end());
    std::sort(sortedWords.begin(), sortedWords.end(), 
        [](const auto& a, const auto& b) {
            return a.second > b.second; // 按频率降序
        });

    // 6. 输出结果
    for (const auto& [word, count] : sortedWords) {
        std::cout << word << ": " << count << "\n";
    }
}

关键原理

• 容器选择：unordered_map基于哈希表（平均O(1)插入/查找），比map（红黑树，O(log n)）更适合频率统计
• 排序优化：直接对map排序效率低，转移到vector后利用随机访问迭代器进行快速排序
• 内存管理：使用移动语义（C++11）转移数据到vector，避免字符串拷贝

最佳实践

• 文本预处理：统一大小写、处理标点，避免"word"和"word,"被识别为不同单词
• 范围循环：使用for (const auto& pair : wordCount)避免不必要的拷贝
• 自定义哈希：若需统计自定义对象，需特化std::hash

常见错误

• 误用map导致O(n log n)统计时间
• 未处理大小写/标点导致统计偏差
• 直接对map排序（map本身按键排序，无法按值排序）
• 循环中频繁调用map::find()（++wordCount[word]已自动处理缺失键）

性能对比

扩展知识

• 并行优化：使用tbb::concurrent_unordered_map（Intel TBB）实现多线程统计
• 内存控制：对于海量数据，可用std::string_view避免字符串拷贝（需注意生命周期）
• C++20改进：范围库（Ranges）简化操作：
  auto words = text | std::views::split(' ') | std::views::transform(cleanWord);