论坛徽章:: 0

发表于 2006-07-31 10:53 |显示全部楼层

洗牌的技巧
洗牌问题：
洗一副扑克，有什么好办法？既能洗得均匀，又能洗得快？即相对于一个文件来说怎样
高效率的实现乱序排列？
关于洗牌问题，其实已经有了一个很好的shell解法，这里另外给三个基于AWK的方法，
有错误之处还请不吝指出。
方法一穷举：
类似于穷举法，构造一个散列来记录已经打印行出现行的次数，如果出现次数多于一
次则不进行处理，这样可以防止重复，但缺点是加大了系统的开销。
awk -v N=`sed -n '$=' data` '
BEGIN{
FS="\n";
RS=""
}
{
srand();
while(t!=N){
x=int(N*rand()+1);
a[x]++;
if(a[x]==1)
{
print $x;t++
}
}
}
' data
方法二变换：
基于数组下标变换的办法，即用数组储存每行的内容，通过数组下标的变换
交换数组的内容，效率好于方法一。
#! /usr/awk
BEGIN{
srand();
}
{
b[NR]=$0;
}
END{
C(b,NR);
for(x in b)
{
print b[x];
}
}
function C(arr,len,i,j,t,x){
for(x in arr)
{
i=int(len*rand())+1;
j=int(len*rand())+1;
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
}
方法三散列：
三个方法中最好的。
利用AWK中散列的特性(详细请看：info gawk 中的7.x ),只要构造一个
随机不重复的散列函数即可，因为一个文件每行的linenumber是独一无二的，所
以用：
随机数＋每行linenumber ------对应------> 那一行的内容
即为所构造的随机函数。
从而有：
awk 'BEGIN{srand()}{b[rand()NR]=$0}END{for(x in b)print b[x]}' data
其实大家担心的使用内存过大的问题不必太在意，可以做一个测试：
测试环境：
PM 1.4GHz CPU,40G硬盘，内存256M的LAPTOP
SUSE 9.3 GNU bash version 3.00.16 GNU Awk 3.1.4
产生一个五十几万行的随机文件,大约有38M：
od /dev/urandom |dd count=75000 >data
拿效率较低的方法一来说:
洗牌一次所用时间:
time awk -v N=`sed -n '$=' data` '
BEGIN{
FS="\n";
RS=""
}
{
srand();
while(t!=N){
x=int(N*rand()+1);
a[x]++;
if(a[x]==1)
{
print $x;t++
}
}
}
' data
结果（文件内容省略）：
real 3m41.864s
user 0m34.224s
sys 0m2.102s
所以效率还是勉强可以接受的。
方法二的测试:
time awk -f awkfile datafile
结果（文件内容省略）：
real 2m26.487s
user 0m7.044s
sys 0m1.371s
效率明显好于第一个。
接着考察一下方法三的效率：
time awk 'BEGIN{srand()}{b[rand()NR]=$0}END{for(x in b)print b[x]}' data
结果（文件内容省略）：
real 0m49.195s
user 0m5.318s
sys 0m1.301s
对于一个38M的文件来说已经相当不错了。
玩的愉快！

复制代码

评分

参与人数 1	可用积分 +3	收起理由
r2007	+ 3	精品文章

查看全部评分

文库|博客

寂寞烈火

家境小康

论坛徽章:: 1

发表于 2006-07-31 10:55 |显示全部楼层

楼主莫非是dbcat的马甲？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

waker

富甲一方

论坛徽章:: 8

发表于 2006-07-31 10:57 |显示全部楼层

dbcat是楼主的马甲

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

寂寞烈火

家境小康

论坛徽章:: 1

发表于 2006-07-31 10:58 |显示全部楼层

原帖由 waker 于 2006-7-31 10:57 发表
dbcat是楼主的马甲

很像很像，dbcatMM很久没露面了，~

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

waker

富甲一方

论坛徽章:: 8

发表于 2006-07-31 11:02 |显示全部楼层

随机不重复的散列函数即可，因为一个文件每行的linenumber是独一无二的，所
以用：

随机数＋每行linenumber ------对应------> 那一行的内容

即为所构造的随机函数。

b[rand()NR]
机率非常小，但不能排除重复可能
用 b[rand()" "NR]如何?

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

r2007

广告杀手

论坛徽章:: 7

发表于 2006-07-31 11:07 |显示全部楼层

原帖由 waker 于 2006-7-31 11:02 发表
随机不重复的散列函数即可，因为一个文件每行的linenumber是独一无二的，所
以用：

随机数＋每行linenumber ------对应------> 那一行的内容

即为所构造的随机函数。

b[rand()NR]
机率非 ...

同楼上观点一样
也可用逗号b[rand(),NR]，默认是\034字符
散列的思路真棒，赞！

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

苏蓉蓉

稍有积蓄

论坛徽章:: 0

发表于 2006-07-31 11:10 |显示全部楼层

原帖由 waker 于 2006-7-31 11:02 发表
随机不重复的散列函数即可，因为一个文件每行的linenumber是独一无二的，所
以用：

随机数＋每行linenumber ------对应------> 那一行的内容

即为所构造的随机函数。

b[rand()NR]
机率非 ...

问世间此山是否最高？天若有情天亦老，爱你爱到忘不了