网站首页  汉语字词  英语词汇  考试资料  写作素材  旧版资料

请输入您要查询的考试资料：

　

标题 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
    对于一个38M的文件来说已经相当不错了。
    --------------------------------------------------------------------
    附带存一个来自 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()
随便看

　

在线学习网考试资料包含高考、自考、专升本考试、人事考试、公务员考试、大学生村官考试、特岗教师招聘考试、事业单位招聘考试、企业人才招聘、银行招聘、教师招聘、农村信用社招聘、各类资格证书考试等各类考试资料。

　

Copyright © 2002-2024 cuapp.net All Rights Reserved
更新时间：2025/5/14 3:41:54