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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 3009 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

pandas

载入

内存

分块

41 条回复 • 2016-09-08 20:52:12 +08:00

liprais

2016-09-07 15:35:19 +08:00

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

xuqd

2016-09-07 15:39:44 +08:00

外排序

zmrenwu

2016-09-07 15:42:02 +08:00

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

xderam

2016-09-07 18:00:23 +08:00

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

helloworld2010

2016-09-07 18:02:30 +08:00

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

Layne

2016-09-07 18:14:27 +08:00

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

9hills

2016-09-07 18:17:09 +08:00

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

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

9hills

2016-09-07 18:18:20 +08:00

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

Magic347

2016-09-07 18:18:54 +08:00

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

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

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

vinceguo

2016-09-07 18:26:18 +08:00 via Android

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

hanzhichao2000

2016-09-07 18:37:20 +08:00 via Android

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

matrix67

2016-09-07 18:39:24 +08:00 via Android

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

lll9p

2016-09-07 18:45:25 +08:00

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

dl2k

2016-09-07 18:46:52 +08:00 via iPhone

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

ooonme

2016-09-07 18:54:19 +08:00 via iPhone

会 python 的话 pyspark 一行代码搞定

zhangchioulin

2016-09-07 19:15:13 +08:00

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

renzhn

2016-09-07 19:32:49 +08:00 via iPhone

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

tolerance

2016-09-07 19:37:53 +08:00

Bloom Filter ， bitmap

renzhn

2016-09-07 19:41:08 +08:00

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

renzhn

2016-09-07 19:45:49 +08:00

不对应该是无参数的 uniq

incompatible

2016-09-07 19:53:00 +08:00

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

mringg

2016-09-07 19:54:14 +08:00 via Android

估算下去重的数据量

mringg

2016-09-07 19:55:11 +08:00 via Android

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

necomancer

2016-09-07 19:56:11 +08:00

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

zmj1316

2016-09-07 20:26:46 +08:00 via Android

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

vinceguo

2016-09-07 20:35:04 +08:00 via Android

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

pynix

2016-09-07 21:08:28 +08:00 via Android

@vinceguo

吃瓜

gladuo

2016-09-07 21:30:06 +08:00

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

Layne

2016-09-08 00:47:11 +08:00

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

9hills

2016-09-08 07:58:18 +08:00

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

做个简单的测试，首先生成 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

2016-09-08 09:52:08 +08:00

@Layne 改了~

Magic347

2016-09-08 10:27:02 +08:00

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

9hills

2016-09-08 11:44:30 +08:00

@Magic347 Talk is cheap ， show me your code 。

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

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

9hills

2016-09-08 11:46:24 +08:00

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

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

9hills

2016-09-08 12:03:31 +08:00

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

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

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

Magic347

2016-09-08 14:22:58 +08:00

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

9hills

2016-09-08 14:51:58 +08:00

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

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

9hills

2016-09-08 14:53:46 +08:00

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

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

9hills

2016-09-08 15:02:40 +08:00

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

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

zmrenwu

2016-09-08 18:42:41 +08:00

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

9hills

2016-09-08 20:52:12 +08:00

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