大文本另类去重多种解法

大文本另类去重多种解法

今天分析数据的时候刚好碰到一个小问题,因为本身文件较大一开始想不出比较好的解决方法,睡个午觉醒来突然有了灵感,自认为目前解决的还算巧妙。

问题

一个 3 列 3,741,430 行的文本(行数比较多),第一列是字符,第二列是字符,第三列是数值,tab 分割。数据格式如下:

A23    B66    1234
C56 D34 2334
B66 A23 1234
D34 C56 2334
E78 F88 1234

这个文本虽然是3,741,430 行,但是其有效信息只有一半。因为A23 B66 1234B66 A23 1234 只是第二列和第一列互换了下位置。

需求

如何尽可能快的处理这个 3 列 3,741,430 行的文本,当某一行的第一列和另一行的第二列相同同时它的第二列又和那一行的第一列相同时,就只保留这两行中的一行即可(具体留哪行没有要求)。简单说就是如下的4行只保留2行:

A23    B66    1234
C56 D34 2334
B66 A23 1234 # 同第一行
D34 C56 2334 # 同第二行

要修改为

A23    B66    1234
D34 C56 2334

讨论

不知道各位读到文章朋友有什么妙招,可以快准狠的解决这个大文本的另类去重问题。不限制使用语言可以是shell,可以是R,python ,也可以是 C 甚至是 PHP,不限制代码行数,可以多CPU。
如果做不到云测试写代码,可以下载这个好多好多行的文件进行测试,文件有170MB,云盘下载链接 https://share.weiyun.com/5iFEju3

对了,我目前的运行时间是:real 0m29.131s;user 0m30.316s;sys 0m0.824s


文章发出后收到了不少回复,以下摘录一些不同的解法。

先说下我当时的解决思路,因为我自己用的最熟的是 awk(写代码的弱鸡),所以我当时的想法是如何用 awk 和 uniq 来解决这个问题,既然只有第一列和第二列被互换位置且第三列一样,那我只要把其中一半数据的第一列和第二列给它颠倒过来就可以用uniq去重了。

位置颠倒这个事情说起来容易,上篇文章的评论区也有很多小伙伴提到了,但是难点在于怎么只颠倒一半的数据。在awk里其实用一下字符串比较比较就可以解决这个问题,因为字符串本身也是可以比较大小的,所以在测试数据中,有一半的数据$1>$2,另一半的数据$2>$1,那么只要我用这个判断条件把一半的数据挑出来就可以进行排序了。因此写出了如下一行命令:

awk 'BEGIN{OFS="\t"}{if($1>$2){print $2,$1,$3} else {print $0} }' howtouniq.txt \
|sort -k1,1 -k2,2 |uniq

这行代码在我的机器上跑了接近30s,在另一个人的机器上跑了20s,大概就是这么一个水平。这次讨论的高票答案,其实也是用了awk,但是他的一行代码只有2s不到,为什么呢?因为我上面的分析思路还是被sort和uniq限制住了,忘了自己当初的需求到底是什么。我的需求其实只是筛除我要的那一半数据就好了,既然利用字符串比较就已经可以区分出来,为什么还要在uniq一次呢?于是上面的代码就被简化为:

箫山茔

time awk '$1>$2' howtouniq.txt > uniq.txt

# real 0m2.259s
# user 0m1.968s
# sys 0m0.265s

所以,这个讨论就是想说:会写代码很重要,能把自己的想法提炼成最简单的需求也很重要,尤其对于不怎么会写代码的人来说(比如我)。顺便多说一句,上篇文章发布以后意外得到了爪哥的关注(seqkit 作者),他也提供了一种方法,即便被 uniq 禁锢了思路,也可以非常快的解决问题。那就是用他的另一个牛逼工具csvtk进行无需 sort 的去重。在csvtk中有一个命令也叫做 uniq,但是它的特点就在于:unique data without sorting。这也给了我们一个启发,自己不行的时候就要多认真学习大佬的工具。

爪哥

time awk 'OFS="\t" { if($1>$2){print $2,$1,$3} else {print} }' howtouniq.txt \
| csvtk uniq -H -t -f 1,2 > howtouniq.txt.awk-csvtk

#real 0m2.674s
#user 0m5.660s
#sys 0m0.482s

以下是其它一些朋友给出的代码,供大家学习和参考,谢谢参与的每一个人。感恩。

贾石石石


open FH_IN, "$ARGV[0]";
open FH_OUT, ">filtered_$ARGV[0]";

my %saved;
while(fh_in){
my @tmp = split/\t/;
if($saved{"$tmp[1]_$tmp[0]"} == 1){
next;
}else{
print FH_OUT $_;
$saved{"$tmp[0]_$tmp[1]"} = 1;
}
}

#时间统计如下:
#real 0m8.136s
#user 0m7.880s
#sys 0m0.258s

黯蓝

#!/usr/bin/perl -w
use strict;

open my $fh, "howtouniq.txt" or die;
my %repeat;
while ($fh){
chomp;
my @array = split "\t", $_;
next if ($repeat{$array[0].$array[1]} || $repeat{$array[1].$array[0]});
$repeat{$array[0].$array[1]} = 1;
print "$_\n";
}
close $fh;

李志锦

library(data.table)
DT <- fread('howtouniq.txt')
n<- nrow(DT)
DT[,identifier := 1:n]
DT1 = melt(DT, id.vars = c("identifier",'V3'),
measure.vars = c("V1", "V2"),
variable.name = 'columns')
DT2 <- DT1[order(identifier,value)]
DT2[,columns := rep(c("newV1","newV2"),n)]
DT3=dcast(DT2, identifier+V3 ~ columns)
DT4=DT3[,.(newV1,newV2,V3)]
fwrite(DT4,"uniqued.txt",sep = "\t")

DT <- fread('howtouniq.txt',stringsAsFactors = T)
DT1<- DT[,.(V2,V1,V3)]
colnames(DT1) <- colnames(DT)
DT2<- rbind(DT,DT1)
DT3 - as.integer(DT2[,V2]) ]
fwrite(DT3,"uniqued3.txt",sep = "\t")

欧哎的人

import time
time1=time.time()
fl=open('howtouniq.txt')
fo=open('uniq.txt','w')
dict={}
for line in fl:
seq=line.split('\t')
key1=seq[0]+'\t'+seq[1]
key2=seq[1]+'\t'+seq[0]
value=seq[2]
try:
dict[key1]
except:
try:
dict[key2]
except:
dict[key1]=value
for key,value in dict.items():
fo.write(key+'\t'+value)
fl.close()
fo.close()
time2=time.time()
print('time:'+str(time2-time1))
# time:6.823026418685913

kim


for each in open(“./howtouniq.txt”,”r”).readlines():
if each.split(“\t”)[0]>each.split(“\t”)[1]:print(each.strip())

FaDIng

#include stdio.h
#include string.h

int main () {
FILE *fp = NULL;
fp = fopen("howtouniq.txt", "r");
char token1[32];
char token2[32];
char token3[32];
while(!feof(fp)) {
fscanf(fp, "%s", token1);
fscanf(fp, "%s", token2);
fscanf(fp, "%s", token3);
if(strcmp(token1, token2) > 0) {
printf("%s\t%s\t%s\n", token1, token2, token3);
}
}
fclose(fp);
return(0);
}

// 0.80s user 0.23s system 99% cpu 1.038 total

华中医想吃涮羊肉

自己写的:
import time
start = time.perf_counter()
d = dict()
with open(file) as f:
for line in f:
a, b, c = line.strip().split("\t")
if a > b:
a, b = b, a
if str(a+"\t"+b) in d.keys():
continue
else:
d[str(a+"\t"+b)] = c
f2 = open(file2, "w")
for key, value in d.items():
f2.write(str(key)+"\t"+str(value))
end = time.perf_counter()
print("Running time:%s seconds"%(end-start))
# 运行时间:8.962766784 seconds

本文作者:思考问题的熊

版权声明:本博客所有文章除特别声明外,均采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 (CC BY-NC-ND 4.0) 进行许可。

扫码即刻沟通

# Python, R, linux

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×