大文本另类去重多种解法

2019-06-03, 1859 words, 9 min read

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

问题

一个 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 1234 和 B66 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

本文作者：思考问题的熊

如果你对这篇文章感兴趣，欢迎通过邮箱或者微信订阅我的 「熊言熊语」会员通讯，我将第一时间与你分享肿瘤生物医药领域最新行业研究进展和我的所思所学所想，点此链接即可进行免费订阅。

· 分享链接 https://kaopubear.top/blog/2019-06-03-uniq-big-file/

R linux Python

大文本另类去重多种解法

问题

需求

讨论

如何快速找到自己需要的 R 包