总数据量大概有 20G ，内存只有 8G ，无法一次载入内存。
查了下 pandas 的 read_csv 方法可以分块地读入数据，同时 DataFrame 对象有一个 unique 方法可以去重。但是好像只能对每一块已载入内存的数据去重，如何整体去重呢？
查了下 pandas 的 read_csv 方法可以分块地读入数据，同时 DataFrame 对象有一个 unique 方法可以去重。但是好像只能对每一块已载入内存的数据去重，如何整体去重呢？
推荐学习书目
› 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
This topic created in 3714 days ago, the information mentioned may be changed or developed.
 |
F281M6Dh8DXpD1g2Sep 7, 2016
1
装个数据库，弄到数据库里，让数据库帮你做这些事
数据库发展了二三十年了，对于这种操作优化的很好,比自己写算法实现轻松多了 |
 |
xuqdSep 7, 2016
2
外排序
|
 |
xderamSep 7, 2016
4
呃，来个运维思维。用 uniq 和 awk 是否也可以？当然没考虑过效率。。
|
 |
helloworld2010Sep 7, 2016
5
分区段去重不就可以了，一块去重完，再合并到相邻块去重……不知道这思路可行么
|
 |
LayneSep 7, 2016
6
@helloworld2010 只要最终去重后的数据量还是无法一次载入内存，应该还是达不到效果吧
|
 |
7
|
1 |
Magic347Sep 7, 2016
9
自己实现的话，显然采用 2 楼的方法，
1. 把原文件分块，分成 n 个小文件依次 load 进内存进行内存排序，并输出 n 个有序小文件 2. 对 n 个有序小文件执行 merge 操作，生成 1 个合并后的有序大文件 3. 逐行扫描该有序大文件，去除重复行数据即可 注意几点： 1. 分块以后的小文件大小要保证可以全量 load 进机器内存 2. merge 时，内存仅需维护一个 n 元素的二叉堆即可，开销大头在于磁盘 IO （因为要反复进行文件读写操作） 这应该是一道很经典的有关海量数据去重的面试题， 扩展到分布式计算领域，可以借鉴 Map-Reduce 的思想（如果楼主有兴趣进一步了解）。 |
 |
hanzhichao2000Sep 7, 2016 via Android
11
blaze 或 dask ，语法类似 pandas ，比数据库和 Hadoop 都轻
|
 |
matrix67Sep 7, 2016 via Android
12
又不是整天去，效率没关系。逃，
|
 |
lll9pSep 7, 2016
13
推荐用数据库，比 Pandas 效率高
|
 |
dl2kSep 7, 2016 via iPhone
14
其实本质上都会考虑用摘要方法来减少用于去重比较的数据量 不过摘要总归会遇到碰撞问题
而且如果数据规模极端点 摘要数据依然可能过大的可能 其实最通用的方法是先轮询一遍数据 根据一种可以避免把相同数据分在不同组的分组算法 比如 md5 后取模 把数据分成 n 个文件 每个文件小于内存大小 然后轮询这些文件进行单独去重 最后合并数据 这个方法大概需要和数据等量的磁盘空间 |
 |
ooonmeSep 7, 2016 via iPhone
15
会 python 的话 pyspark 一行代码搞定
|
 |
zhangchioulinSep 7, 2016
16
@Layne 哈哈哈 ... 你的头像
|
 |
renzhnSep 7, 2016 via iPhone
17
你可以:
1. 进对数据进行排序，此操作不需要大量内存，可以用 sort 命令 2. 过滤掉重复出现的行，可以只直接用 uniq -d |
 |
toleranceSep 7, 2016
18
Bloom Filter ， bitmap
|
|
renzhnSep 7, 2016
19
第二步应该是 uniq -u
这两步操作都不需要把所有的数据读入内存 |
|
renzhnSep 7, 2016
20
不对 应该是无参数的 uniq
|
 |
incompatibleSep 7, 2016
21
@vinceguo 你这就好比面试时别人让你写代码实现快排，你却直接找了个现成的库函数调用了一下。工具的奴隶。
|
 |
ming2050Sep 7, 2016 via Android
22
估算下去重的数据量
|
 |
necomancerSep 7, 2016
24
试试布隆表。。。 pandas 直接是够呛了吧
|
 |
zmj1316Sep 7, 2016 via Android
25
同意上面说的，先用摘要算法分块再做
|
 |
vinceguoSep 7, 2016 via Android
26
@incompatible 煞笔，你从硅提纯开始做起吧
|
 |
gladuoSep 7, 2016
28
解决问题的话用数据库或者 spark ；
面试的话 hash 或者 分块进行 merge 再合并； 如果预计去重之后内存还是放不下，该升级内存了 ：） |
|
LayneSep 8, 2016
29
@zhangchioulin 哈哈哈哈，你的头像自己改了字母？
|
|
9hillsSep 8, 2016
30
地图炮下，假如这是一个面试题目，凡是说排序的，统统不得分
做个简单的测试，首先生成 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 ？ |
|
zhangchioulinSep 8, 2016
31
@Layne 改了~
|
|
Magic347Sep 8, 2016
32
@9hills
这个应用场景下，题主的痛点显然是资源的受限（现有机器的内存资源不足以 1 次完成全量数据的加载和去重）， 对于执行时限上显然不必要求如此苛刻。 而事实上，基于外排序的思想，这一类问题往往易于扩展到海量数据的分布式并行处理上。 而所谓的海量数据就不仅仅是 1 亿条数据那么多了，可能是 TB 量级甚至 PB 量级的， 到那时你还指望你那玩具命令可以跑出结果吗？自己体会一下吧。 |
|
9hillsSep 8, 2016
33
@Magic347 Talk is cheap ， show me your code 。
别 TB ， PB ，你就写个 3000w 行排序去重给我看看，呵呵 事实上，你以为 hash 不能分布式扩展？去重一定要排序？呵呵 |
|
9hillsSep 8, 2016
34
@Magic347 再说资源， lz 不过 1 亿条未去重数据，按照 hash 来说 8G 足够了。这个就是一个正确的解决方法
你说有其他解决办法， OK ， code 拿出来 看看，在 8G 内存条件下，看谁更快 |
|
9hillsSep 8, 2016
35
恰好前不久用 13 台机器+Spark 做了一个排序
100G 的原始数据，需要接近 40min 但是如果用 分布式去重算法的话， 1min 以内 有的时候不能盲目 MR ，盲目 Spark ，不先自己思考下 |
|
Magic347Sep 8, 2016
36
@9hills 见 9 楼，如果你连外排序的思想都没有建立起来过的话，我只能说基本功未必扎实。
你想一下，当年 google 是怎么利用几百兆内存的低配机器搭起来大规模分布式集群的。 不要总纠结在要怎么利用 8G 内存把程序跑得更快这件事情上了。 |
Select Language