用 C++ 写了个简单的词频统计,为啥比 DuckDB 还慢一半呢。。

@Ta 04-20 20:48 13144点击

步骤

  1. 生成 1亿 个长度为 15 的随机字符串(为了 SSO 优化)。内容是 1~1KW 的随机数字,并补足前导 0。
  2. DuckDB 统计前 1000 的高频词,用时 20 秒。
  3. 自己写个 C++ 程序,统计高频词,用时 30 秒。
  4. 改为生成长度为 16 的随机字符串,再用刚写的 C++ 程序统计,用时 40 秒。。

截图

截图_20240420202339.webp(59.29 KB)

C++ 代码

#include <queue>
#include <string>
#include <vector>
#include <iostream>
#include "ankerl/unordered_dense.h"

const auto TOP_NUM = 1000;

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::string word;
    ankerl::unordered_dense::map<std::string, size_t> dict;
    dict.reserve(10000000);

    // 逐词计算频次
    while (std::cin >> word)
        ++dict[word];

    using dict_item_type = decltype(dict)::value_type;
    auto comp = [](const auto* lhs, decltype(lhs) rhs) {
        return lhs->second > rhs->second;
    };

    std::priority_queue<
            const dict_item_type*,
            std::vector<const dict_item_type*>,
            decltype(comp)> words(comp);

    // 找出排名靠前的词频
    for (const auto& item: dict) {
        if (words.size() < TOP_NUM)
            words.push(&item);
        else if (item.second > words.top()->second) {
            words.pop();
            words.push(&item);
        }
    }

    // 并排序好这些高频词
    std::deque<const dict_item_type*> result;
    while (!words.empty()) {
        auto top = words.top();
        result.push_front(top);
        words.pop();
    }

    // 再逐一输出
    for (auto&& i: result)
        std::cout << i->second << '\t' << i->first << '\n';
}
回复列表(9|隐藏机器人聊天)
  • @Ta / 04-21 00:25 / /

    你充分利用多核CPU了吗?把任务分成多个部分跑在不同的CPU核心上,应该会比单线程快很多。就算各个部分得出结果之后还得合并再筛选一次,也应该比整体在单个CPU核心上运行更快。

  • @Ta / 04-21 02:01 / /

    @老虎会游泳DuckDB 也设成单线程的了。对比起来应该算公平的?

    DuckDB 双线程时 14 秒,3+线程爆(笔记本 8GB 板载)内存了。。

    老虎看这代码,有啥不合理的地方,才拖累性能,打不过 DuckDB 吗?

  • @Ta / 04-21 02:50 / /

    @无名啊std::cin >> word这个io可能比较慢,把文件mmap到内存然后使用char*指针直接访问每行的内容可能更快,跳转到下一行就是上一行的指针加上一行的字节数。

  • @Ta / 04-21 02:54 / /

    @无名啊,你可以自行统计一下分段用时,看看输入、计算和输出各占比多少。也许输入输出是大头(因为stdio是同步锁定的)。

  • @Ta / 04-21 07:25 / /
    被锁定
    层主 @艾木友尔尔巴 于 2024-04-21 07:25 删除了该楼层。
  • @Ta / 04-23 00:26 / /

    @老虎会游泳

    std::cin >> word这个io可能比较慢

    确实,我改成 std::getline(std::cin, word) 后,就由 28 秒 → 25 秒了。

    你可以自行统计一下分段用时,看看输入、计算和输出各占比多少。

    我简单测了测,读取 1 亿 15 长度字符串用时。

    • std::cin >> word:5.1 秒
    • std::getline(std::cin, word):2.2 秒
    • 手动开 64KB 缓冲区,每次 std::cin.read() 填充,std::memchr\nstr.append() 构造:1.4 秒

    感觉输入上,这速度也可以了。

    而且,我 strace 了一下 DuckDB,它也是要读到缓冲区里的,且缓冲区贼大,32MB。。且一定要填充完整 32MB,才干活。。

    怪不得我说,一边解压大文本/脚本实时生成内容,一边喂给 DuckDB,怎么耗时会变长。。明明 writer 产生内容的速度还挺快的呀。。

    也许输入输出是大头(因为stdio是同步锁定的)

    我取消与 stdio 同步了:std::ios::sync_with_stdio(false);

    这个确实很耗时间。不取消的话,总时间直接翻倍。。

    把文件mmap到内存然后使用char*指针直接访问

    如果想解压大文本,再通过管道喂给程序时,好像不能 mmap 了吧。。

  • @Ta / 04-23 00:26 / /

    @老虎会游泳,上一楼,想每段隔多几行回复来着。咋连续多行,被压缩成一行了。。

  • @Ta / 04-23 01:41 / /

    @无名啊,github的markdown解析器应该也是这样啊,用空行隔开的段落会被转换为<p></p>,无论中间有多少空行都只会生成一对<p></p>

    所以实际上根本没有生成换行,你在这里看到的隔行效果只是<p></p>的边距。

    如果你就是想要多个换行,可以使用[br]


    这是[br]叠加<p></p>的效果。

  • @Ta / 04-23 13:05 / /

    膜拜大佬!
    https://www.chengyao.xyz

添加新回复
回复需要登录