1 亿条数据如何使用 Pandas 去重？

[zmrenwu]

总数据量大概有 20G ，内存只有 8G ，无法一次载入内存。
查了下 pandas 的 read_csv 方法可以分块地读入数据，同时 DataFrame 对象有一个 unique 方法可以去重。但是好像只能对每一块已载入内存的数据去重，如何整体去重呢？

[liprais]

装个数据库，弄到数据库里，让数据库帮你做这些事
数据库发展了二三十年了，对于这种操作优化的很好,比自己写算法实现轻松多了

[xuqd]

外排序

[zmrenwu]

@liprais 看来唯有如此，暂时找不到 pandas 下的解决方案。

[xderam]

呃，来个运维思维。用 uniq 和 awk 是否也可以？当然没考虑过效率。。

[helloworld2010]

分区段去重不就可以了，一块去重完，再合并到相邻块去重……不知道这思路可行么

[Layne]

@helloworld2010 只要最终去重后的数据量还是无法一次载入内存，应该还是达不到效果吧

[9hills]

@xderam 用 awk 就行了，不需要 uniq 。因为原理是 hash 表

1 亿条数据（和大小无关，和条数有关）， 8G 内存应该差不多。 80B 一条，可能刚刚好

[9hills]

@9hills 这里有个错误， hash 表的大小是和最终去重后的条目有关的，和原始数据条目无关

[Magic347]

自己实现的话，显然采用 2 楼的方法，
1. 把原文件分块，分成 n 个小文件依次 load 进内存进行内存排序，并输出 n 个有序小文件
2. 对 n 个有序小文件执行 merge 操作，生成 1 个合并后的有序大文件
3. 逐行扫描该有序大文件，去除重复行数据即可

注意几点：
1. 分块以后的小文件大小要保证可以全量 load 进机器内存
2. merge 时，内存仅需维护一个 n 元素的二叉堆即可，开销大头在于磁盘 IO （因为要反复进行文件读写操作）

这应该是一道很经典的有关海量数据去重的面试题，
扩展到分布式计算领域，可以借鉴 Map-Reduce 的思想（如果楼主有兴趣进一步了解）。

[vinceguo]

@Magic347 MR 有什么好面试的，去重一条 PIG 就能做掉

[hanzhichao2000]

blaze 或 dask ，语法类似 pandas ，比数据库和 Hadoop 都轻

[matrix67]

又不是整天去，效率没关系。逃，

[lll9p]

推荐用数据库，比 Pandas 效率高

[dl2k]

其实本质上都会考虑用摘要方法来减少用于去重比较的数据量 不过摘要总归会遇到碰撞问题
而且如果数据规模极端点 摘要数据依然可能过大的可能 其实最通用的方法是先轮询一遍数据 根据一种可以避免把相同数据分在不同组的分组算法 比如 md5 后取模 把数据分成 n 个文件 每个文件小于内存大小 然后轮询这些文件进行单独去重 最后合并数据 这个方法大概需要和数据等量的磁盘空间

[ooonme]

会 python 的话 pyspark 一行代码搞定

[zhangchioulin]

@Layne 哈哈哈 ... 你的头像

[renzhn]

你可以:
1. 进对数据进行排序，此操作不需要大量内存，可以用 sort 命令
2. 过滤掉重复出现的行，可以只直接用 uniq -d

[tolerance]

Bloom Filter ， bitmap

[renzhn]

第二步应该是 uniq -u
这两步操作都不需要把所有的数据读入内存

[renzhn]

不对 应该是无参数的 uniq

[incompatible]

@vinceguo 你这就好比面试时别人让你写代码实现快排，你却直接找了个现成的库函数调用了一下。工具的奴隶。

[mringg]

估算下去重的数据量

[mringg]

@mringg 去重后的数据量，如果不大，用 hash 去重吧

[necomancer]

试试布隆表。。。 pandas 直接是够呛了吧

[zmj1316]

同意上面说的，先用摘要算法分块再做

[vinceguo]

@incompatible 煞笔，你从硅提纯开始做起吧

[pynix]

@vinceguo


吃瓜

[gladuo]

解决问题的话用数据库或者 spark ；
面试的话 hash 或者 分块进行 merge 再合并；
如果预计去重之后内存还是放不下，该升级内存了 ：）

[Layne]

@zhangchioulin 哈哈哈哈，你的头像自己改了字母？

[9hills]

地图炮下，假如这是一个面试题目，凡是说排序的，统统不得分

做个简单的测试，首先生成 3000w 行随机数，去重后是 1000w
seq 1 10000000 > 1000w
cat 1000w 1000w 1000w > 3000w
shuf 3000w > 3000w.shuf

然后用 awk hash 的方法去做去重。结果如下

资源占用： 1G 内存， E5-2650 v3 @ 2.30GHz 一个核
时间消耗： 35s

$ time awk '{if($1 in a){}else{a[$1];print $1}}' 3000w.shuf > 1000w.out
awk '{if($1 in a){}else{a[$1];print $1}}' 3000w.shuf > 1000w.out 34.12s user 0.95s system 99% cpu 35.107 total


说排序的，谁能用单机排序去重做到 35s ？

[zhangchioulin]

@Layne 改了~

[Magic347]

@9hills
这个应用场景下，题主的痛点显然是资源的受限（现有机器的内存资源不足以 1 次完成全量数据的加载和去重），
对于执行时限上显然不必要求如此苛刻。
而事实上，基于外排序的思想，这一类问题往往易于扩展到海量数据的分布式并行处理上。
而所谓的海量数据就不仅仅是 1 亿条数据那么多了，可能是 TB 量级甚至 PB 量级的，
到那时你还指望你那玩具命令可以跑出结果吗？自己体会一下吧。

[9hills]

@Magic347 Talk is cheap ， show me your code 。

别 TB ， PB ，你就写个 3000w 行排序去重给我看看，呵呵

事实上，你以为 hash 不能分布式扩展？去重一定要排序？呵呵

[9hills]

@Magic347 再说资源， lz 不过 1 亿条未去重数据，按照 hash 来说 8G 足够了。这个就是一个正确的解决方法

你说有其他解决办法， OK ， code 拿出来 看看，在 8G 内存条件下，看谁更快

[9hills]

恰好前不久用 13 台机器+Spark 做了一个排序

100G 的原始数据，需要接近 40min
但是如果用 分布式去重算法的话， 1min 以内

有的时候不能盲目 MR ，盲目 Spark ，不先自己思考下

[Magic347]

@9hills 见 9 楼，如果你连外排序的思想都没有建立起来过的话，我只能说基本功未必扎实。
你想一下，当年 google 是怎么利用几百兆内存的低配机器搭起来大规模分布式集群的。
不要总纠结在要怎么利用 8G 内存把程序跑得更快这件事情上了。

[9hills]

@Magic347 知道什么是 Terasort 比赛么，参加过么

你就知道你自己有多么的坐井观天

[9hills]

@Magic347 另外你的 9 楼里面有一行代码？

拿出 code 来才是王道，而不是说说思想，思想不值钱。 benchmark 才是硬道理

[9hills]

@Magic347 另外大规模分布式集群，你见过多大的？

恰好负责运维一个 6 位数机器的分布式集群，不知道比起您见过的集群是大呢，还是小呢

[zmrenwu]

@9hills 嗯，此法值得一试，不过由于我的数据重复率是十分低的，因此可能基于 hash 什么的算法内存依然还是装不下。

[9hills]

@zmrenwu 可以试试 disk-based hash ，把 hash 表放到磁盘中。不过性能我没测试