递归火山软件开发平台

标题: 【大厂面试题】火山如何能实现位图数据bitmap处理文本？ [打印本页]

作者: abcfox 时间: 2025-10-1 22:03
标题: 【大厂面试题】火山如何能实现位图数据bitmap处理文本？
本帖最后由 abcfox 于 2025-10-1 22:18 编辑

因为项目需要处理重复文本，只会使用分割文本或正则匹配再查找去重复，文件大了处理起来非常慢，于是到网上查找发现处理文本占内存少速度又快基本都推荐用位图数据bitmap，找到易语言的方法，还有C/C++的方法，还有AI全自动生成的python代码，但是都不会翻译成火山代码，论坛哪位会易语言或C++的看看能翻译成火山代码分享吗？应该有不少人也会用到，谢谢！！

大厂第三轮面试问题如下：
A文件有40亿个QQ号码，B文件有40万个QQ号码，所有QQ号码都是无符号整数，求A和B的交集，可用内存限定不超600M.

附件是源码文件：
(, 下载次数: 67)

(, 下载次数: 6)

作者: abcfox 时间: 2025-10-1 22:16
(, 下载次数: 15)

这是易语言源码截图

作者: gzylove 时间: 2025-10-1 23:15
使用哈希表不就可以了

作者: weilai 时间: 2025-10-2 08:11
用火山处理这种问题最简单了

作者: weilai 时间: 2025-10-2 08:24
文本去重复一般哈希表就可以了，整数去重使用标准逻辑数组类，一个不行的话使用两个逻辑标准数组类（这个逻辑标准数组类就是bitmap），或者自己简单实现个，自己实现的可能稍微性能差一点点

作者: weilai 时间: 2025-10-2 10:15
整数去重不是几十亿的数据哈希表足矣

作者: abcfox 时间: 2025-10-2 23:41

weilai 发表于 2025-10-2 08:24
文本去重复一般哈希表就可以了，整数去重使用标准逻辑数组类，一个不行的话使用两个逻辑标准数组类（这个逻 ...

大佬，能不能写个简单例子，不会的问题真的没有参考完全没有思路

假设有两个文件：a.txt 大小100M，50万行文本；b.txt 大小60M，30万行文本；
功能1：a.txt 文件去掉 b.txt 文件中存在的重复行后输出到新文件 c.txt
功能2：取 a.txt 和 b.txt 的相同文本行（即面试题的取交集）后输出到新文件 d.txt

作者: abcfox 时间: 2025-10-2 23:50
本帖最后由 abcfox 于 2025-10-2 23:53 编辑

下载源码的人挺多的，说明很多人也想找这种方法，只是真能用火山处理可能没有几个，主流的英语编程借助AI轻易就能写出来了，python、C++的豆包和通义都能写出来测试能直接运行，只是刚接触python还看不懂，连aardio借助AI也能写出来，只是没测试实际效果。英语差点，将就用了，再等个5年可能AI也能完美写中文程序了。

作者: weilai 时间: 2025-10-3 00:28
本帖最后由 weilai 于 2025-10-3 00:31 编辑

abcfox 发表于 2025-10-2 23:41
大佬，能不能写个简单例子，不会的问题真的没有参考完全没有思路

假设有两个文件：a.txt 大小100M，50万 ...

下面这就是示例，我没测试，你试试看速度如何（编译后），如果还慢再优化
(, 下载次数: 142) (, 下载次数: 137)
文本数组合成一个文本

作者: weilai 时间: 2025-10-3 00:33
(, 下载次数: 140) (, 下载次数: 137)

作者: abcfox 时间: 2025-10-3 09:38

weilai 发表于 2025-10-3 00:33

谢谢分享，给打80分，因为没有用到bitmap数据结构

作者: abcfox 时间: 2025-10-3 09:58
Bitmap（位图）原理
Bitmap 是一种用 “位（bit）” 标识数据存在性的高效数据结构，核心优势是极致的空间效率（用 1 个 bit 代表 1 个数据的 “存在 / 不存在” 状态），时间复杂度为 O (n)（遍历一次即可完成去重）。

1. 位与数据的映射逻辑
每个 “位” 仅需两种状态：0（数据不存在）、1（数据存在）。通过基础数据类型的 “多位数” 特性，可批量管理多个数据的状态：
1 个 unsigned char（1 字节 = 8bit）：可标识 0~7 共 8 个整数的存在性；
1 个 unsigned int（4 字节 = 32bit）：可标识 0~31 共 32 个整数的存在性；
以此类推：k 个字节的空间，可标识 k×8 个整数的存在性。

2. 关键计算：Bitmap 空间需求
对于 QQ 号最大值 2^32 - 1（需覆盖 0~2^32-1 共 2^32 个数值），所需空间换算如下：
总位数需求：2^32 bit（每个 QQ 号对应 1 位）；
总字节需求：2^32 bit ÷ 8 bit/字节 = 512 MB；
结论：仅需 512MB 空间，即可容纳所有 QQ 号的存在性标识。

3. 方案步骤
初始化 Bitmap 数组：
用 unsigned int 数组实现 Bitmap（每个元素 32bit），数组长度为 2^32 ÷ 32 = 2^28（即 268435456 个元素），总占用空间 512MB。
遍历 QQ 号，标记存在性：
对文件中每个 QQ 号 x，通过位运算定位其在 Bitmap 中的位置，并将对应位设为 1（重复 QQ 号会多次设 1，但结果不变，自动去重）：
计算数组索引：index = x ÷ 32（确定 x 落在哪个 unsigned int 元素上）；
计算位偏移：offset = x % 32（确定 x 在该元素的第几位）；
位运算设 1：bitmap[index] |= (1 << offset)（用 “或操作” 确保该位为 1）。
遍历 Bitmap，输出去重结果：
从小到大遍历 0~2^32-1 的所有数值，检查 Bitmap 中对应位是否为 1：
若为 1：该数值是去重后的 QQ 号，输出；
若为 0：该数值未出现，跳过。

作者: weilai 时间: 2025-10-3 10:12

abcfox 发表于 2025-10-3 09:38
谢谢分享，给打80分，因为没有用到bitmap数据结构

这样写效率不错还简单，处理大数据整数使用bit合理些，当然了这样写效率不算最高，稍微优化下（原理一样）100m估计毫秒级（10毫秒以内）

作者: abcfox 时间: 2025-10-3 11:44

weilai 发表于 2025-10-3 10:12
这样写效率不错还简单，处理大数据整数使用bit合理些，当然了这样写效率不算最高，稍微优化下（原理一样 ...

是的，目前算是最优解方案了

作者: weilai 时间: 2025-10-3 14:02

abcfox 发表于 2025-10-3 11:44
是的，目前算是最优解方案了

其实使用bitmap 和使用哈希表处理整数的话写法上没有区别没测试对不对，不过应该差不多

(, 下载次数: 114)

(, 下载次数: 117)

作者: 秋天的童话 时间: 2025-10-3 14:13
支持火山高质量算法代码分享，用户感谢大佬！

作者: abcfox 时间: 2025-10-3 20:43

weilai 发表于 2025-10-3 14:02
其实使用bitmap 和使用哈希表处理整数的话写法上没有区别没测试对不对，不过应该差不多

再次感谢，能给提供多种参考思路，优秀，100分！
希望对其他人也有参考帮助。

欢迎光临递归火山软件开发平台 (https://bbs.voldp.com/)