客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
洗牌问题：洗一副扑克，有什么好办法？既能洗得均匀，又能洗得快？即相对于一个文件来说怎样高效率的实现乱序排列？ ChinaUnix 确实是 Shell 高手云集的地方，只要你想得到的问题，到那里基本上都能找到答案。r2007 给出了一个取巧的方法，利用 Shell 的 $RANDOM 变量给原文件的每一行加上随机的行号然后根据这个随机行号进行排序，再把临时加上去的行号给过滤掉，这样操作之后得到的新文件就相当于被随机“洗”了一次： 复制代码 代码如下: while read i;do echo "$i $RANDOM";done<file|sort -k2n|cut -d" " -f1 当然如果你的源文件每行的内容比较复杂的话就必须对这段代码进行改写，但只要知道了处理的关键技巧，剩下的问题都不难解决。 另外一篇来自苏蓉蓉的用 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{ { END{ C(b,NR); function C(arr,len,i,j,t,x){ for(x in arr) } 方法三：散列 三个方法中最好的。 随机数＋每行linenumber ------对应------> 那一行的内容 即为所构造的随机函数。 复制代码 代码如下: awk 'BEGIN{srand()}{b[rand()NR]=$0}END{for(x in b)print b[x]}' data 其实大家担心的使用内存过大的问题不必太在意，可以做一个测试： 测试环境： PM 1.4GHz CPU,40G硬盘，内存256M的LAPTOP 产生一个五十几万行的随机文件,大约有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的文件来说已经相当不错了。 -------------------------------------------------------------------- 附带存一个来自 flyfly 写的 python 版本乱序代码： 复制代码 代码如下: #coding:gb2312 import sys import random def usage(): f = open(filename, 'r') #write to file randomly f = open(filename, 'w') |
请发表评论