洗牌問題：洗一副撲克，有什么好辦法？既能洗得均勻，又能洗得快？即相對(duì)于一個(gè)文件來說怎樣高效率的實(shí)現(xiàn)亂序排列？

ChinaUnix 確實(shí)是 Shell 高手云集的地方，只要你想得到的問題，到那里基本上都能找到答案。r2007 給出了一個(gè)取巧的方法，利用 Shell 的 $RANDOM 變量給原文件的每一行加上隨機(jī)的行號(hào)然后根據(jù)這個(gè)隨機(jī)行號(hào)進(jìn)行排序，再把臨時(shí)加上去的行號(hào)給過濾掉，這樣操作之后得到的新文件就相當(dāng)于被隨機(jī)“洗”了一次：

代碼如下:

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

當(dāng)然如果你的源文件每行的內(nèi)容比較復(fù)雜的話就必須對(duì)這段代碼進(jìn)行改寫，但只要知道了處理的關(guān)鍵技巧，剩下的問題都不難解決。

另外一篇來自蘇蓉蓉的用 awk 來實(shí)現(xiàn)洗牌效果的隨機(jī)文件排序代碼分析（原貼在這里，以及對(duì)此帖的一個(gè)后續(xù)討論，如果你沒有登錄帳號(hào)的話可以到這里查看精華區(qū)文章）則寫的更為詳細(xì)：

--------------------------------------------------------------------

關(guān)于洗牌問題，其實(shí)已經(jīng)有了一個(gè)很好的shell解法，這里另外給三個(gè)基于AWK的方法，有錯(cuò)誤之處還請(qǐng)不吝指出。

方法一：窮舉

類似于窮舉法，構(gòu)造一個(gè)散列來記錄已經(jīng)打印行出現(xiàn)行的次數(shù)，如果出現(xiàn)次數(shù)多于一次則不進(jìn)行處理，這樣可以防止重復(fù)，但缺點(diǎn)是加大了系統(tǒng)的開銷。

代碼如下:

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

方法二：變換

基于數(shù)組下標(biāo)變換的辦法，即用數(shù)組儲(chǔ)存每行的內(nèi)容，通過數(shù)組下標(biāo)的變換交換數(shù)組的內(nèi)容，效率好于方法一。

代碼如下:

#! /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;

}

}

方法三：散列

三個(gè)方法中最好的。

利用AWK中散列的特性(詳細(xì)請(qǐng)看：info gawk 中的7.x ),只要構(gòu)造一個(gè)隨機(jī)不重復(fù)的散列函數(shù)即可，因?yàn)橐粋€(gè)文件每行的linenumber是獨(dú)一無二的，所以用：

隨機(jī)數(shù)＋每行l(wèi)inenumber ------對(duì)應(yīng)------> 那一行的內(nèi)容

即為所構(gòu)造的隨機(jī)函數(shù)。

從而有：

代碼如下:

awk 'BEGIN{srand()}{b[rand()NR]=$0}END{for(x in b)print b[x]}' data

其實(shí)大家擔(dān)心的使用內(nèi)存過大的問題不必太在意，可以做一個(gè)測(cè)試：

測(cè)試環(huán)境：

PM 1.4GHz CPU,40G硬盤，內(nèi)存256M的LAPTOP

SUSE 9.3 GNU bash version 3.00.16 GNU Awk 3.1.4

產(chǎn)生一個(gè)五十幾萬行的隨機(jī)文件,大約有38M：

代碼如下:

od /dev/urandom |dd count=75000 >data

拿效率較低的方法一來說:

洗牌一次所用時(shí)間:

代碼如下:

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

結(jié)果（文件內(nèi)容省略）：

代碼如下:

real 3m41.864s

user 0m34.224s

sys 0m2.102s

所以效率還是勉強(qiáng)可以接受的。

方法二的測(cè)試:

代碼如下:

time awk -f awkfile datafile

結(jié)果（文件內(nèi)容省略）：

代碼如下:

real 2m26.487s

user 0m7.044s

sys 0m1.371s

效率明顯好于第一個(gè)。

接著考察一下方法三的效率：

代碼如下:

time awk 'BEGIN{srand()}{b[rand()NR]=$0}END{for(x in b)print b[x]}' data

結(jié)果（文件內(nèi)容省略）：

代碼如下:

real 0m49.195s

user 0m5.318s

sys 0m1.301s

對(duì)于一個(gè)38M的文件來說已經(jīng)相當(dāng)不錯(cuò)了。

--------------------------------------------------------------------

附帶存一個(gè)來自 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()

更多信息請(qǐng)查看IT技術(shù)專欄