高效统计文本单词频率并排序输出

题目

高效统计文本单词频率并排序输出

信息

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

考点

容器选择,迭代器使用,自定义排序,性能优化

快速回答

实现步骤：

1. 使用 unordered_map 存储单词频率（O(1)插入/查询）
2. 将 map 元素转移到 vector 中以便排序
3. 自定义排序函数：频率降序，相同频率按字典序升序
4. 使用 stable_sort 保持等价元素顺序
5. 输出结果时注意避免不必要的拷贝

关键点：

• 优先选择哈希容器提升性能
• 排序时考虑多条件组合
• 使用移动语义减少拷贝开销

问题场景

实现一个函数，输入字符串文本，输出按频率降序排列的单词列表（频率相同则按字典序升序）。例如输入 "apple banana apple orange"，输出：
apple:2
banana:1
orange:1

解决方案

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

using namespace std;

vector<pair<string, int>> wordFrequency(const string& text) {
    // 1. 使用unordered_map统计频率
    unordered_map<string, int> freqMap;
    istringstream iss(text);
    string word;

    while (iss >> word) {
        // 可选：转换为小写统一计数
        // transform(word.begin(), word.end(), word.begin(), ::tolower);
        ++freqMap[word];
    }

    // 2. 转移到vector进行排序
    vector<pair<string, int>> result;
    result.reserve(freqMap.size());
    for (auto&& entry : freqMap) {  // 使用移动语义减少拷贝
        result.emplace_back(move(entry.first), entry.second);
    }

    // 3. 自定义排序：频率降序，字典序升序
    stable_sort(result.begin(), result.end(), 
        [](const auto& a, const auto& b) {
            if (a.second != b.second) 
                return a.second > b.second;  // 频率降序
            return a.first < b.first;         // 字典序升序
        });

    return result;
}

// 示例用法
int main() {
    string text = "apple banana apple orange banana";
    auto result = wordFrequency(text);

    for (const auto& [word, count] : result) {
        cout << word << ": " << count << endl;
    }
    /* 输出：
        apple: 2
        banana: 2
        orange: 1
    */
    return 0;
}

原理说明

• 容器选择：unordered_map 基于哈希表，插入/查询平均 O(1) 时间复杂度，比 map（红黑树，O(log n)）更适合频率统计
• 排序策略：STL关联容器无法直接排序，需转移到线性容器。stable_sort 保证等价元素（如相同频率）保持原始顺序
• 移动语义：emplace_back + move 避免字符串拷贝，提升性能

最佳实践

1. 预处理文本：根据需求添加大小写转换或标点过滤
2. 预留空间：reserve() 避免 vector 扩容开销
3. 大文本优化：对于超大文本，可用 reserve() 预分配 map 桶空间
4. 输出控制：如需限制输出数量，使用 partial_sort

常见错误

扩展知识

• 性能对比：处理 100 万单词时，unordered_map 比 map 快 3-5 倍
• 并行优化：C++17 的 execution::par 可实现并行排序
• 替代方案：flat_map（排序后类似 vector）可减少内存碎片
• 实时处理：如需持续更新排名，可用 priority_queue 或跳表