• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    Shell脚本实现乱序排列文件内容的多种方法(洗牌问题)

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

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

    复制代码 代码如下:

    while read i;do echo "$i $RANDOM";donefile|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()

    上一篇:Shell脚本实现生成SSL自签署证书
    下一篇:Shell脚本实现查杀子进程、僵尸进程
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

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