超大型文件比较,内存不足,只能分页读区再匹配,但头都秃了,也没想到优化的方式,朋友们帮帮忙啊。

查看 296|回复 23
ck65   
允许误差的情况下,布隆过滤器可以满足 12
leonshaw   
前阵子有个 1 billion row 挑战,OP 可以参考一下看有没有帮助
- https://1brc.dev
- https://mrkaran.dev/posts/1brc/
FeifeiJin
OP
  
那就用 sqlite
FeifeiJin
OP
  
@Nosub
@me1onsoda
谢谢,但是这边用的是 C#。
布隆过滤器我正在看,大概率是不允许误差。
FeifeiJin
OP
  
@ck65
我觉得有帮助,我看一看。
就算不能解决我的问题,也能从里面看到很多思路。
ipwx   
@leonshaw 宝,谢谢。但不能。
leonshaw   
大概有多少条数据。
数据条数不多(千万级别)但是每一行的列多的话,可以考虑先扫一遍两个 csv ,记录一下每一个 csv 里面 name 和 file byte offset 的对应关系。然后在内存里面根据 name 进行你的几个操作,最后根据记录下来的 offset 从 csv 里面重新读出来对应的 Person 。
geelaw   
@FeifeiJin 为什么不能?
Nosub   
第一个问题就是你是否有足够的磁盘空间,如果有的话,完全可以先排完序再说。
假设你使用 64 位操作系统,先分别排序两个 csv ,这样做:
1. 把 x.csv 映射到虚拟内存。
2. 扫描一次,计算行数 n 。
3. 建立一个长度是 8n 字节的文件 x.dat ,映射到内存,把它看成长度是 n 的 uint64 数组 index 。
4. 扫描 x.csv ,在 index[i] 放置第 (i-1) 行开始的位移。
5. 对 index 的元素 z 按 x.csv 从 z 处提取出的字符串升序排序。
6. 保存 x-sorted.csv 。
上述操作需要 O(n log n) 的时间。
然后同时把 a.csv, a.dat, b.csv, b.dat 映射到虚拟内存,并用有序合并算法计算需要的三个结果,这需要 O(n) 的时间。
额外的磁盘空间复杂度是 O(n),具体来说,显然不会超过 20 GB 。
LRJia   
@FeifeiJin 即便如此,我觉得 c#程序员去用这个库,也没有问题,建议你试试看,写个命令行程序就可以了,不试试怎么知道行不行,这个库肯定解决了你的读取问题了。
您需要登录后才可以回帖 登录 | 立即注册

返回顶部