Chinaunix

标题: 去重复<转> [打印本页]

作者: yinyuemi 时间: 2011-09-01 12:55
标题: 去重复<转>
本帖最后由 yinyuemi 于 2011-09-02 01:28 编辑

文本：

02,10,11,18,27,30
06,09,11,14,20,31
02,10,11,18,27,33
01,03,04,16,18,22
07,14,22,27,28,32
02,10,11,16,18,27
04,05,09,15,21,30
12,13,17,20,22,23
04,05,09,15,21,30

去重复的规则：

02,10,11,18,27,30
06,09,11,14,20,31
02,10,11,18,27,33(和第1条重复5个,去掉)
01,03,04,16,18,22
07,14,22,27,28,32
02,10,11,16,18,27(和第1条重复5个,去掉)
04,05,09,15,21,30
12,13,17,20,22,23
04,05,09,15,21,30(和倒数3条重复6个,去掉)

输出结果：

02,10,11,18,27,30
06,09,11,14,20,31
01,03,04,16,18,22
07,14,22,27,28,32
04,05,09,15,21,30
12,13,17,20,22,23

作者: liion631818 时间: 2011-09-01 13:29
没看明白怎么办，每一行都是跟他前面的行比较，重复5个或者以上就去掉？

作者: yinyuemi 时间: 2011-09-01 13:31
回复 2# liion631818

恩，是这个意思

作者: waker 时间: 2011-09-01 13:48

awk -F, '{s=0;m=1;for(i=1;i<=NF;i++)s+=$i^3;for(i=1;i<=NF;i++)m*=(!a[s-$i^3]++);if(m)print}'

复制代码

作者: waker 时间: 2011-09-01 13:49
如果每个域都是正整数，好象是可以的

作者: mpstat 时间: 2011-09-01 13:55

回复 liion631818

恩，是这个意思
yinyuemi 发表于 2011-09-01 13:31

顺序要不要考虑？比如

02,10,11,18,27,30
02,10,27,11,18,30

是不是重复

作者: yinyuemi 时间: 2011-09-01 13:56
回复 6# mpstat

应该是排好序的，每行都是从小到大的

作者: yinyuemi 时间: 2011-09-01 13:58
回复 4# waker

老大，这个太猛了！

作者: mpstat 时间: 2011-09-01 14:15

waker 发表于 2011-09-01 13:48

。。。没看懂，解释一下

作者: jason680 时间: 2011-09-01 14:22

文本：

02,10,11,18,27,30
06,09,11,14,20,31
02,10,11,18,27,33
01,03,04,16,18,22
07,14,22,27,28 ...
yinyuemi 发表于 2011-09-01 12:55

$ echo '02,10,11,18,27,30
06,09,11,14,20,31
02,10,11,18,27,33
01,03,04,16,18,22
07,14,22,27,28,32
02,10,11,16,18,27
04,05,09,15,21,30
12,13,17,20,22,23
04,05,09,15,21,30' | awk -F, '{T="";for(n=0;n++<NF

{T=T","a[$n];a[$n]=a[$n]","NR};split(T,t,","

;f=0;for(n in t){if(t[n]==""

continue;if(gsub(t[n],"",T)>=5)f=1};if(f==0)print $0}'
02,10,11,18,27,30
06,09,11,14,20,31
01,03,04,16,18,22
07,14,22,27,28,32
04,05,09,15,21,30
12,13,17,20,22,23

作者: ly5066113 时间: 2011-09-01 14:31
回复 9# mpstat

5个数的立方和能唯一确定这5个数

大概是这个意思，没有作过数学上的论证。

作者: ly5066113 时间: 2011-09-01 14:33
给个通俗点的解法，如果都是2位数

awk -F, '{for(i=1;i<=l;i++){s=0;for(j=1;j<=NF;j++)if(index(a[i],$j))s++;if(s>=5)next}a[++l]=$0}1' urfile

复制代码

作者: waker 时间: 2011-09-01 14:33

回复 mpstat

5个数的立方和能唯一确定这5个数

大概是这个意思，没有作过数学上的论证。
ly5066113 发表于 2011-09-01 14:31

不是有个什么费它妈的大定理么？我只是猜想一下，不保证总可行，可能是正好这个例子碰巧了

作者: mpstat 时间: 2011-09-01 14:37
回复 13# waker

费马大定理：当整数n > 2时，关于x, y, z的不定方程 x^n + y^n = z^n. 无正整数解。
你的定理是：当整数n > 2时，关于a,b,c,d,e的不定方程 a^n + b^n+c^n+d^n+e^n != a1^n+b1^n+c1^n+d1^n+e1^n

作者: ly5066113 时间: 2011-09-01 15:00
回复 14# mpstat

参考这个帖，情况应该类似：

http://bbs.chinaunix.net/thread-773690-1-1.html

作者: waker 时间: 2011-09-01 15:03

回复 waker

费马大定理：当整数n > 2时，关于x, y, z的不定方程 x^n + y^n = z^n. 无正整数解。 ...
mpstat 发表于 2011-09-01 14:37

都说了是猜一下嘛，我认为的最好算法就是
1.猜x=1是方程的解
2.代入方程，两边平衡，

这是就最好的算法

作者: mpstat 时间: 2011-09-01 15:08
回复 15# ly5066113

awk能支持的整型上限是多大?

作者: Single_GG 时间: 2011-09-01 16:32
{:3_183:}

作者: liion631818 时间: 2011-09-01 16:50
哦滴神啊

作者: xrzs1986 时间: 2011-09-02 01:57
本帖最后由 xrzs1986 于 2011-09-02 02:19 编辑

回复 10# jason680

思路新颖~

作者: yinyuemi 时间: 2011-09-02 02:47
本帖最后由 yinyuemi 于 2011-09-02 03:05 编辑

贴下我的吧，呵呵，

awk '
{e=0
{for(i=1;i<NR;i++)
if(split("#"gensub(",","##","g",a[i])"#",x,"#"gensub(",","#|#","g",$0)"#")>=6){e=1;break}
}
if(!e){a[NR]=$0;print $0}
}'
使用fucntion还可以简化下：
awk '
function f(a,b){return "#"gensub(",","#"b"#","g",a)"#";}
{e=0
{for(i=1;i<NR;i++)
if(split(f(a[i],""),x,f($0,"|"))>=6){e=1;break}
}
if(!e){a[NR]=$0;print $0}
}'

复制代码

作者: jason680 时间: 2011-09-02 08:28

回复 jason680

思路新颖~
xrzs1986 发表于 2011-09-02 01:57

是的!!

通用性与效能兼具.
(想说在10楼在最底了,
没人看了,没人理.... 效能也没A^3+B^3..好)

作者: waker 时间: 2011-09-02 08:33

是的!!

通用性与效能兼具.
(想说在10楼在最底了,
没人看了,没人理.... 效能也没A^3+B^3..好)
jason680 发表于 2011-09-02 08:28

如果数据量比较大重复多,好像也没12楼的效能好,也可能是我的数据样品没代表性

作者: jason680 时间: 2011-09-02 08:43
本帖最后由 jason680 于 2011-09-02 08:46 编辑

如果数据量比较大重复多,好像也没12楼的效能好,也可能是我的数据样品没代表性
waker 发表于 2011-09-02 08:33

不知,你如何评估效能....

12楼有两个for....
且 l (在第一个for中)会愈来愈大....
for(i=1;i<=l;i++){s=0;for(j=1;j<=NF;

注: 我没测试过....且尚可改善效能(如果有须要)......

作者: waker 时间: 2011-09-02 08:47
回复 24# jason680

time出来的

作者: waker 时间: 2011-09-02 08:48
稍等一会儿我帖一下

作者: waker 时间: 2011-09-02 09:06

[waker@proxy ~]$ time awk -F, '{s=0;m=1;for(i=1;i<=NF;i++)s+=$i^3;for(i=1;i<=NF;i++)m*=(!a[s-$i^3]++);if(m)print}' file >/dev/null
real 0m16.777s
user 0m13.445s
sys 0m0.471s
[waker@proxy ~]$ time awk -F, '{for(i=1;i<=l;i++){s=0;for(j=1;j<=NF;j++)if(index(a[i],$j))s++;if(s>=5)next}a[++l]=$0}1' file >/dev/null
real 0m25.130s
user 0m22.973s
sys 0m0.486s
[waker@proxy ~]$ time awk -F, '{T="";for(n=0;n++<NF;){T=T","a[$n];a[$n]=a[$n]","NR};split(T,t,",");f=0;for(n in t){if(t[n]=="")continue;if(gsub(t[n],"",T)>=5)f=1};if(f==0)print $0}' file >/dev/null
real 8m34.754s
user 7m46.657s
sys 0m9.780s
[waker@proxy ~]$ wc -l file
388800 file

复制代码

最后一种方法是我Ctrl-C出来的时间,还一直在算,等不急了

作者: yinyuemi 时间: 2011-09-02 09:18
本帖最后由 yinyuemi 于 2011-09-02 09:24 编辑

for((i=1;i<=1000;i++)); do echo '02,10,11,18,27,30
06,09,11,14,20,31
02,10,11,18,27,33
01,03,04,16,18,22
07,14,22,27,28,32
02,10,11,16,18,27
04,05,09,15,21,30
12,13,17,20,22,23
04,05,09,15,21,30' >>testfile; done
wc -l testfile
9000 testfile
4#：
time awk -F, '{s=0;m=1;for(i=1;i<=NF;i++)s+=$i^3;for(i=1;i<=NF;i++)m*=(!a[s-$i^3]++);if(m)print}' testfile
02,10,11,18,27,30
06,09,11,14,20,31
01,03,04,16,18,22
07,14,22,27,28,32
04,05,09,15,21,30
12,13,17,20,22,23
real 0m0.154s
user 0m0.154s
sys 0m0.000s
10#：（ctrl-c 终止程序）
time awk -F, '{T="";for(n=0;n++<NF;){T=T","a[$n];a[$n]=a[$n]","NR};split(T,t,",");f=0;for(n in t){if(t[n]=="")continue;if(gsub(t[n],"",T)>=5)f=1};if(f==0)print $0}' testfile
02,10,11,18,27,30
06,09,11,14,20,31
01,03,04,16,18,22
07,14,22,27,28,32
04,05,09,15,21,30
12,13,17,20,22,23
real 10m20.540s
user 10m18.173s
sys 0m0.982s
12#：
time awk -F, '{for(i=1;i<=l;i++){s=0;for(j=1;j<=NF;j++)if(index(a[i],$j))s++;if(s>=5)next}a[++l]=$0}1' testfile
02,10,11,18,27,30
06,09,11,14,20,31
01,03,04,16,18,22
07,14,22,27,28,32
04,05,09,15,21,30
12,13,17,20,22,23
real 0m0.128s
user 0m0.127s
sys 0m0.001s
21#：
time awk '
function f(a,b){return "#"gensub(",","#"b"#","g",a)"#";}
{e=0
{for(i=1;i<NR;i++)
if(split(f(a[i],""),x,f($0,"|"))>=6){e=1;break}
}
if(!e){a[NR]=$0;print $0}
}' testfile
02,10,11,18,27,30
06,09,11,14,20,31
01,03,04,16,18,22
07,14,22,27,28,32
04,05,09,15,21,30
12,13,17,20,22,23
real 0m0.841s
user 0m0.837s
sys 0m0.001s
4#waker兄的效率很高，不过适用于数值型数据
10# 通用性好，不过效率上要差
12# 如Tim兄所言，数值是2位的，效率很高
21# 通用性上稍差，如果是文本去重复的，且文本中包含正则符号或","或"#"，可能会有问题（10#的代码使用gsub可能也有类似问题，没测试），效率上比4#和12#的要差

复制代码

作者: xiaopan3322 时间: 2011-09-02 09:50
好贴留名，学习！

作者: jason680 时间: 2011-09-02 10:02
本帖最后由 jason680 于 2011-09-02 10:04 编辑

yinyuemi 发表于 2011-09-02 09:18

请问楼主何者正确....
$ cat repeat5a
01,02,03,04,05,06
01,02,03,04,05,07
01,02,03,04,07,09

$ awk -F, '{s=0;m=1;for(i=1;i<=NF;i++)s+=$i^3;for(i=1;i<=NF;i++)m*=(!a[s-$i^3]++);if(m)print}' repeat5a

复制代码

01,02,03,04,05,06

$ awk -F, '{for(i=1;i<=l;i++){s=0;for(j=1;j<=NF;j++)if(index(a[i],$j))s++;if(s>=5)next}a[++l]=$0}1' repeat5a

复制代码

01,02,03,04,05,06
01,02,03,04,07,09

作者: yinyuemi 时间: 2011-09-02 10:42
回复 30# jason680

好问题！
因为我是转贴，所以也并不完全明白去重复的规则，
我的理解，如果是你提供的那个数据，我觉得第二个是对的，

不过，如果数据的顺序不同，结果有可能也会不同，的确很纠缠，可以不去讨论细节了，
大家解决问题的思路都值得学习！

作者: expert1 时间: 2011-09-02 10:56
回复 17# mpstat

这个参考c语言的无符号long int吧，记不清了，之前专门试过

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)