主頁(yè) > 知識(shí)庫(kù) > Shell腳本實(shí)現(xiàn)亂序排列文件內(nèi)容的多種方法(洗牌問(wèn)題)

Shell腳本實(shí)現(xiàn)亂序排列文件內(nèi)容的多種方法(洗牌問(wèn)題)

熱門標(biāo)簽:地圖標(biāo)注輻射圖案 安裝外呼系統(tǒng)費(fèi)用 電銷機(jī)器人 劍魚(yú) 衛(wèi)星地圖標(biāo)注地名 寧波智能外呼系統(tǒng)公司 聯(lián)通電話機(jī)器人怎么接 申請(qǐng)公司400電話要注意什么 曲阜400電話辦理 奧維互動(dòng)地圖標(biāo)注參數(shù)

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

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

復(fù)制代碼 代碼如下:

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

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

另外一篇來(lái)自蘇蓉蓉的用 awk 來(lái)實(shí)現(xiàn)洗牌效果的隨機(jī)文件排序代碼分析(原貼在這里,以及對(duì)此帖的一個(gè)后續(xù)討論,如果你沒(méi)有登錄帳號(hào)的話可以到這里查看精華區(qū)文章)則寫的更為詳細(xì):
--------------------------------------------------------------------
關(guān)于洗牌問(wèn)題,其實(shí)已經(jīng)有了一個(gè)很好的shell解法,這里另外給三個(gè)基于AWK的方法,有錯(cuò)誤之處還請(qǐng)不吝指出。

方法一:窮舉

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

復(fù)制代碼 代碼如下:

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)容,通過(guò)數(shù)組下標(biāo)的變換交換數(shù)組的內(nèi)容,效率好于方法一。

復(fù)制代碼 代碼如下:

#! /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ú)一無(wú)二的,所以用:

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

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

復(fù)制代碼 代碼如下:

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

    其實(shí)大家擔(dān)心的使用內(nèi)存過(guò)大的問(wèn)題不必太在意,可以做一個(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è)五十幾萬(wàn)行的隨機(jī)文件,大約有38M:

復(fù)制代碼 代碼如下:

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

拿效率較低的方法一來(lái)說(shuō):

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

復(fù)制代碼 代碼如下:

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)容省略):
復(fù)制代碼 代碼如下:

real    3m41.864s
user    0m34.224s
sys     0m2.102s

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

方法二的測(cè)試:

復(fù)制代碼 代碼如下:

time awk -f awkfile datafile

結(jié)果(文件內(nèi)容省略):
復(fù)制代碼 代碼如下:

real    2m26.487s
user    0m7.044s
sys     0m1.371s

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

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

復(fù)制代碼 代碼如下:

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

結(jié)果(文件內(nèi)容省略):
復(fù)制代碼 代碼如下:

real    0m49.195s
user    0m5.318s
sys     0m1.301s

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

附帶存一個(gè)來(lái)自 flyfly 寫的 python 版本亂序代碼:

復(fù)制代碼 代碼如下:

#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()

標(biāo)簽:安康 上饒 三門峽 江西 大慶 仙桃 大興安嶺 遵義

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《Shell腳本實(shí)現(xiàn)亂序排列文件內(nèi)容的多種方法(洗牌問(wèn)題)》,本文關(guān)鍵詞  Shell,腳本,實(shí)現(xiàn),亂序,排列,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題,煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《Shell腳本實(shí)現(xiàn)亂序排列文件內(nèi)容的多種方法(洗牌問(wèn)題)》相關(guān)的同類信息!
  • 本頁(yè)收集關(guān)于Shell腳本實(shí)現(xiàn)亂序排列文件內(nèi)容的多種方法(洗牌問(wèn)題)的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章