代码性能提升

下面给出一版面向执行速度和内存占用的优化方案，并解释各处的性能收益。原代码的主要问题：线性去重导致 O(n^2)、基于红黑树的 map 统计常数大、字符串逐次拼接造成反复分配与拷贝。

一、改进版实现（通用、无需已排序输入，平均 O(n) 计数） 说明：

• 去除无用的线性去重循环（原 uniq 完全未被使用，直接删掉）。
• 用 unordered_map 做频率统计，并提前 reserve，减少rehash与节点分配。
• 将计数结果搬到 vector 后排序（按频次降序，频次相同按键升序保证确定性）。
• 为输出字符串一次性 reserve 精确容量，避免反复扩容；避免 to_string 的临时分配，使用无分配的整数拼接。

代码： #include #include #include <unordered_map> #include #include using namespace std;

static inline int digits10_ll(long long x) { if (x == 0) return 1; if (x < 0) x = -x; int d = 0; while (x) { x /= 10; ++d; } return d; }

static inline void append_int(string& s, long long x) { if (x == 0) { s.push_back('0'); return; } if (x < 0) { s.push_back('-'); x = -x; } char buf[20]; // 足够容纳 64 位整数 int i = 0; while (x) { buf[i++] = char('0' + (x % 10)); x /= 10; } s.append(buf + (i - 1), buf + i); // 反向追加 }

string summarize(const vector& xs) { // 1) 频率统计：哈希表 + 预留容量 unordered_map<int, int> freq; freq.reserve(xs.size()); for (int v : xs) ++freq[v];

// 2) 搬到 vector 并排序（频次降序，键升序保证稳定输出）
vector<pair<int,int>> items;
items.reserve(freq.size());
for (auto& kv : freq) items.emplace_back(kv.first, kv.second);
sort(items.begin(), items.end(),
     [](const auto& a, const auto& b) {
         if (a.second != b.second) return a.second > b.second;
         return a.first < b.first;
     });

// 3) 预估输出容量并一次性 reserve，避免拼接时多次扩容
size_t cap = 0;
for (const auto& p : items) {
    cap += digits10_ll(p.first) + (p.first < 0 ? 1 : 0); // 可能有负号
    cap += 1;  // ':'
    cap += digits10_ll(p.second); // 计数非负
    cap += 1;  // '\n'
}

string out;
out.reserve(cap);
for (const auto& p : items) {
    append_int(out, p.first);
    out.push_back(':');
    append_int(out, p.second);
    out.push_back('\n');
}
return out;

}

二、为什么更快/更省内存

• 删除 O(n^2) 去重：原 uniq 的线性查找完全不必要（而且结果没被使用），移除即省时省内存。
• unordered_map 替换 map：
  • map 基于红黑树，插入/查找 O(log n) 且每个节点分配独立内存，分支预测差、缓存命中率低。
  • unordered_map 平均 O(1)，并且 reserve(xs.size()) 显著降低rehash与额外分配；整数键的哈希/比较开销极低，通常可达 2–5 倍速度提升。
• 构造输出的内存优化：
  • 预先计算最终字符串长度并一次 reserve，避免多次扩容与拷贝（原先每次 += 可能导致多次重新分配）。
  • 避免每次 to_string 带来的临时字符串分配，使用 append_int 在栈上转换整数并直接 append 到目标字符串。
• 更好的排序步骤：
  • 先转为向量再排序仅对“唯一键数量”U 执行 O(U log U)；相比在 map 上排序/遍历，少了树节点的间接访问与指针跳转，缓存友好。

三、复杂度与典型收益

• 时间：统计阶段平均 O(n)，整理输出 O(U log U)，U 为唯一值数目，整体通常远优于原 map 方案的 O(n log U)。
• 空间：unordered_map 以桶方式分配，reserve 后减少扩容；去掉无用 uniq 临时容器；输出字符串一次性分配。
• 典型整数分布下，与原代码相比，整体加速通常 2–10 倍（取决于 n、U、平台与编译器），内存分配次数显著减少。

四、可选方案：若允许排序输入副本，尝试“排序+线性扫描”法

• 思路：复制 xs 到本地，排序后一次线性扫描计数，省掉哈希表。
• 复杂度：O(n log n) 排序 + O(n) 扫描 + O(U log U) 频次排序。对于大整数域、哈希表现一般或内存紧张场景，这种方法的常数更好、缓存友好，实际表现可能接近甚至优于哈希法。
• 代码要点：vector ys(xs); sort(ys.begin(), ys.end()); 然后对连续相同值做计数，填充 items，后续字符串构造与上面一致。

五、进一步微调（按需）

• 若已知值域很小（例如 0..K）：可用 vector 直接做计数，省去哈希与排序的哈希常数，性能最佳。
• 若数据量极大：可使用更高质量的哈希策略（如 robin_hood hashing 库）或自定义分配器/pmr 降低分配开销。
• 若输出版式可变：批量写入到缓冲区或使用 writev/缓冲文件流，减少一次性构建超大字符串的内存峰值。