Shell脚本实现乱序排列文件内容的多种方法（洗牌问题）

洗牌问题：洗一副扑克，有什么好办法？既能洗得均匀，又能洗得快？即相对于一个文件来说怎样高效率的实现乱序排列？

ChinaUnix 确实是 Shell 高手云集的地方，只要你想得到的问题，到那里基本上都能找到答案。r2007 给出了一个取巧的方法，利用 Shell 的 $RANDOM 变量给原文件的每一行加上随机的行号然后根据这个随机行号进行排序，再把临时加上去的行号给过滤掉，这样操作之后得到的新文件就相当于被随机“洗”了一次：

while read i;do echo "$i $RANDOM";done<file|sort -k2n|cut -d" " -f1

另外一篇来自苏蓉蓉的用 awk 来实现洗牌效果的随机文件排序代码分析（原贴在这里，以及对此帖的一个后续讨论，如果你没有登录帐号的话可以到这里查看精华区文章）则写的更为详细：
--------------------------------------------------------------------
关于洗牌问题，其实已经有了一个很好的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

附带存一个来自 flyfly 写的 python 版本乱序代码：

#coding:gb2312 

import sys 

import random

def usage(): 

print "usage:program srcfilename dstfilename" 

global filename 

filename = "" 

try: 

filename = sys.argv[1] 

except: 

usage() 

raise() 

#open the phonebook file
f = open(filename, 'r') 

phonebook = f.readlines() 

print phonebook 

f.close()
#write to file randomly 

try: 

filename = sys.argv[2] 

except: 

usage() 

raise()
f = open(filename, 'w') 

random.shuffle(phonebook) 

f.writelines(phonebook) 

f.close()