一个关于skyline的文本处理问题

xidianyiming

现有一个文本内容如下：
0.39110 0.69382 0.61317 0.82071 0.37825
0.29711 0.06946 0.53172 0.23524 0.02451
0.37634 0.89398 0.75013 0.39690 0.39255
0.02410 0.78825 0.50206 0.94523 0.54708
0.36089 0.73496 0.10325 0.17214 0.24655
0.65100 0.61618 0.15599 0.51357 0.60178
0.25484 0.34376 0.18546 0.63792 0.64255
0.39518 0.60918 0.45812 0.58930 0.46120
0.95791 0.13845 0.77765 0.27272 0.07795
0.95407 0.62039 0.03752 0.01861 0.43648

文本中每条记录都有5个属性，现需要把此文本中的记录分开保存到两个文本sk和rest。其中sk文本中的记录为支配记录，rest文本中的记录为被支配记录。
所谓支配是指对于某条记录a，存在一个记录b，且b的每条属性都大于a记录对应的属性，则b记录支配a记录。如例子文本中，第二条记录就被第一条记录支配，而第一条记录不被任何记录支配，则第一条记录应保存在sk中，而第二条记录应保存到rest中。
对于大规模数据一般用C程序实现，但我想请教各位高人，用shell或者perl如何实现，同时用脚本实现来检测我的C语言实现结果是否正确。

附件中有用于测试的文件，望各位大神不吝赐教！！！
dataset.zip (409.32 KB, 下载次数: 78)

2011-05-29 12:47 上传

点击文件名下载附件

yinyuemi

回复 1# xidianyiming


    两行两行的比较，还是所有的数据合起来比较？

xidianyiming

仅对对应位置的属性进行比较，比如记录1：0.39110 0.69382 0.61317 0.82071 0.37825 记录2：
0.29711 0.06946 0.53172 0.23524 0.02451 其中记录1每个属性都比记录2中对应的属性值要大，则记录1支配记录2。如果对于剩下所有记录，都不存在一个记录可以支配记录1，则记录一被保存在sk文件中，也就是skyline点。

yinyuemi

回复 1# xidianyiming


    试试这个，不知效率如何：

1. awk '{for(i=1;i<=NF;i++) a[NR,i]=$i;c[NR]=$0}END{for(m=1;m<=NR;m++){for(n=m+1;n<=NR;n++) {for(l=1;l<=NF;l++){(a[n,l]-a[m,l]>0)?t++:t--};if(t=="5"){d[m]="s";d[n]="r";t=0;break};if(t=="-5"){d[n]="s";d[m]="r";t=0;};t=0;break}};for(y=1;y<=NR;y++) if(d[y]=="s"){print c[y]>"rest"}else{print c[y]>"sk"}}' dataset

复制代码

#:又加了个break

yinyuemi

回复 4# xidianyiming


    又改进了下程序，另外，你测试的时候，使用dos2unix转换下你的文件

xidianyiming

回复 5# yinyuemi


    你好，感谢你积极回应我的问题！但感觉你的程序重复比较的情况比较多，比如你每次处理到第N条记录时，都进行前面N-1条的比较(这点我AWK不熟悉，不晓得是不是我理解的这样)，这样就重复比较了；而且如果确定某条记录已经是被支配点了，之后的比较可以不考虑它了，你程序中的break只是在本次循环中跳过，之后仍会比较。

xidianyiming

额~~~不好意思，我漏看了END，在你程序基础上加个判断：如果已经是被支配点，就continue而不进行属性的比较，这样应该就行了。
=================================
刚又仔细看了下程序，并进行测试，程序有问题，不能正确找出支配点。你对每条记录的判断仅仅找到一条可支配的就被认为是支配点然后break了，这点肯定是不对的,被支配点只要属性低于某个点即可，但支配点的判断则必须对所有点而言；其次，比较有些重复哈！

yinyuemi

回复 8# xidianyiming


    恩，可以再加个判断

xidianyiming

回复 9# yinyuemi


    刚又仔细看了下程序，并进行测试，程序有问题，不能正确找出支配点。你对每条记录的判断仅仅找到一条可支配的就被认为是支配点然后break了，这点肯定是不对的,被支配点只要属性低于某个点即可，但支配点的判断则必须对所有点而言；其次，比较有些重复哈！