Zeal Blog - 泽欧里
梦想 就像鸡蛋
要么孵化 要么臭掉
WWW Zeal Blog

[存] 如何乱序排列文件内容

zeal 2006-09-26 11:10 于 开发/理论 , 3323 字 |  + 0 - 0   English
标签 ( Tags ):  ,  , 
洗牌问题:洗一副扑克,有什么好办法?既能洗得均匀,又能洗得快?即相对于一个文件来说怎样高效率的实现乱序排列?

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


对于一个38M的文件来说已经相当不错了。
--------------------------------------------------------------------

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

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

This Entry was Last Modified on 2007-05-28 14:36
引用本文(TrackBack): 此功能无限期关闭ing ... 如有引用请在文中标明出处并提供超链接  
没有评论.
对于这篇日志您有什么想法?我想听听您的高见。
如果您不是没有思想的机器Spammer,请告诉我 4 + 8 =
然后任选以下两种方式之一告诉我您的身份:
1. 使用您的 OpenID
2. 使用传统留言格式
(必填) 名字
如何称呼您?
(选填) URL
在此填写您的 Blog / Homepage 的地址,我将非常乐于访问
(选填) Email
Email地址将在经过防SPAM处理后显示在页面。如果您不希望公开自己的Email,请略过此栏
并写下您的见解:
(由于需要进行SPAM过滤,如果评论提交速度慢请耐心等待)
记住我?

  如何进行评论                   当有新回复时给我发送邮件通知
除了 <b> 和 <i> 之外,其他的HTML标签都将从您的评论中去除. URL 或 Email 地址会被自动加上链接.
当您点击发表或者预览之后,系统会自动保存您此次评论的内容,以便当网络原因发表失败时直接按Ctrl-V重新粘贴上次评论内容。
注意:快捷键及自动拷贝功能仅对IE浏览器有效。
发贴统计

Tot 610/1314

日志存档
2008年
2007年
2006年
本 Blog 原创内容
遵循以下授权:

Creative Commons
(创作共用) CC

署名-非商业性
-相同方式分享
Zeal Blog 基于
Powered byPivot - 1.24.1: 'Arcee'
Pivot1.24.1
开发
Launched @
2005-04-27
 里,居也。——《说文》    里,邑也。——《尔雅》。李注:“居之邑也。”沪ICP备05024379号 Back To Home All Links Loading