当前位置： 首页 > news >正文

用awk写递归

news 来源：原创 2024/5/3 17:54:30 
　　版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址

　　http://www.cnblogs.com/Colin-Cai/p/7087128.html 

　　作者：窗户

　　QQ：6679072

　　E-mail：6679072@qq.com

看到自己很多年前写的一篇帖子，觉得有些意义，转录过来，稍加修改。

awk是一种脚本语言，语法接近C语言，我比较喜欢用，gawk甚至可以支持tcp/ip,用起来非常方便。

awk也支持递归，只是awk不支持局部变量，所有的变量都是全局的，于是写递归有些麻烦。本文说白了，也只是借awk说一种编程的思路罢了。

原文如下：

awk支持函数，也支持递归。但awk并不支持局部变量，于是看上去递归函数很不好实现，因为在某一级调用函数的时候，里面的变量在该级调用还没有退出前就可能会被别的调用给修改掉，于是得到的结果会与期望并不一致。
我们考虑C语言，它的局部变量放在硬件支持的栈（一般用栈指针）内。于是我们就去思考，为什么是栈呢？我们来考虑一个具体的函数调用顺序：
f1调用f2;
f2调用f3;
f3返回；
f2调用f4;
f4调用f5;
f5返回；
f4返回；
f2返回；
f1返回；
按照这个循序，我们来思考每个函数开辟的栈空间：
f1的栈空间开辟(f1进栈）
f2的栈空间开辟(f2进栈）
f3的栈空间开辟(f3进栈）
f3的栈空间消亡(f3出栈）
f4的栈空间开辟(f4进栈）
f5的栈空间开辟(f5进栈）
f5的栈空间消亡(f5出栈）
f4的栈空间消亡(f4出栈）
f2的栈空间消亡(f2出栈）
f1的栈空间消亡(f1出栈）
原来跟我们数据结构里的栈的先进后出是一回事情，所以叫栈。
而当前的我们取的变量的地址都是相对于栈指针来说的，这是相对，而不是像全局变量的那种绝对。
于是我们可以受到启发，可以扩展这里的栈指针和地址的概念，awk的递归函数就可以出来了。
以下是用递归来算一个数组中的最大值（每递归一级就把数组分为两段，每段求最大值），只是举一个例子，可以扩展到任意应用。

#!/bin/awk -f
func test1(a,start,len)
{
        if(len<=1)
                return a[start];
        x = test1(a,start,int(len/2));
        y = test1(a,start+int(len/2),len-int(len/2));
        return (x>y)?x:y;
}
func test2(a,start,len)
{
        if(len<=1)
                return a[start];
        testlen++;
        testa[testlen] = test2(a,start,int(len/2));
        testlen++;
        testa[testlen] = test2(a,start+int(len/2),len-int(len/2));
        testlen-=2;
        return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];
}
func test3(a,start,len)
{
        if(len<=1) {
                return a[start];
        }
        V = V";"test3(a,start,int(len/2));
        V = V";"test3(a,start+int(len/2),len-int(len/2));
        xx = V;
        sub(/.*;/,"",xx);
        sub(/;[^;]+$/,"",V);
        yy = V;
        sub(/.*;/,"",yy);
        sub(/;[^;]+$/,"",V);
        return int(xx)>int(yy)?int(xx):int(yy);
}
NR==1{
        way=$1;
        print $1
}
NR==2{
        max=$1;
        for(i=2;i<=NF;i++)
                if($i > max)
                        max = $i;
        print max;
        for(i=1;i<=NF;i++)
                a[i] = $i;
        if(way == 2)
                print test2(a,1,NF);
        else if(way == 3)
                print test3(a,1,NF);
        else
                print test1(a,1,NF);
        exit(0);
}

这里面实现了三个递归函数，第一个是测试全局变量的污染，它是得不到正确的答案的
第二个是用数组来模拟变量栈，testlen就是所谓的“栈顶指针”
第三个是用字符串来模拟变量栈，字符串末尾就是“栈顶指针”，每个“局部变量”之间是用分号隔开
用随机数据测试一下这个应用：

linux-0gt0:/tmp/test # for((i=0;i<10;i++));do  { echo $(($RANDOM % 3 + 1)); let count=$RANDOM%100+50; for((j=0;j<count;j++));do echo -n $(($RANDOM % 10000)) " "; done ; echo ; }|./1.awk ;done | sed -nr 'N;N;p;/\n(.*)\n\1$/{s/.*/right\n/p;d;};       /^[23]/s/(.).*/\1 SO STRANGE!!!!!!!!!!!!!!!!!!!!!/p; s/.*/wrong\n/p'
2
9981
9981
right

3
9391
9391
right

1
9919
5257
wrong

2
9860
9860
right

3
9967
9967
right

3
9940
9940
right

3
9828
9828
right

2
9752
9752
right

3
9996
9996
right

2
9930
9930
right

当然，栈的数目自然也可以不只维系一个，test2和test3维系的是一个栈。
现在来实现test4和test5，两个函数是test2和test3的变体，各自维系两个栈。

#!/bin/awk -f
#func test1(a,start,len)
#{
#       if(len<=1)
#               return a[start];
#       x = test1(a,start,int(len/2));
#       y = test1(a,start+int(len/2),len-int(len/2));
#       return (x>y)?x:y;
#}
func test2(a,start,len)
{
        if(len<=1)
                return a[start];
        testlen++;
        testa[testlen] = test2(a,start,int(len/2));
        testlen++;
        testa[testlen] = test2(a,start+int(len/2),len-int(len/2));
        testlen-=2;
        return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];
}
func test3(a,start,len)
{
        if(len<=1) {
                return a[start];
        }
        V = V";"test3(a,start,int(len/2));
        V = V";"test3(a,start+int(len/2),len-int(len/2));
        xx = V;
        sub(/.*;/,"",xx);
        sub(/;[^;]+$/,"",V);
        yy = V;
        sub(/.*;/,"",yy);
        sub(/;[^;]+$/,"",V);
        return int(xx)>int(yy)?int(xx):int(yy);
}
func test4(a,start,len)
{
        if(len<=1)
                return a[start];
        testlenx++;
        testleny++;
        testax[testlenx] = test4(a,start,int(len/2));
        testay[testleny] = test4(a,start+int(len/2),len-int(len/2));
        testlenx-=1;
        testleny-=1;
        return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
}
func test5(a,start,len)
{
        if(len<=1) {
                return a[start];
        }
        V1 = V1";"test5(a,start,int(len/2));
        V2 = V2";"test5(a,start+int(len/2),len-int(len/2));
        xx = V1;
        sub(/.*;/,"",xx);
        sub(/;[^;]+$/,"",V1);
        yy = V2;
        sub(/.*;/,"",yy);
        sub(/;[^;]+$/,"",V2);
        return int(xx)>int(yy)?int(xx):int(yy);
}
NR==1{
        way=$1;
        print $1
}
NR==2{
        max=$1;
        for(i=2;i<=NF;i++)
                if($i > max)
                        max = $i;
        print max;
        for(i=1;i<=NF;i++)
                a[i] = $i;
        if(way == 2)
                print test2(a,1,NF);
        else if(way == 3)
                print test3(a,1,NF);
        else if(way == 4)
                print test4(a,1,NF);
        else if(way == 5)
                print test5(a,1,NF);
        exit(0);
}

测试一下，

linux-0gt0:/tmp/test # for((i=0;i<10;i++));do  { echo $(($RANDOM % 2 + 4)); let count=$RANDOM%100+50; for((j=0;j<count;j++));do echo -n $(($RANDOM % 10000)) " "; done ; echo ; }|./1.awk ;done | sed -nr 'N;N;p;/\n(.*)\n\1$/{s/.*/right\n/p;d;};       /^[234]/s/(.).*/\1 SO STRANGE!!!!!!!!!!!!!!!!!!!!!/p; s/.*/wrong\n/p'
5
9904
9904
right

4
9823
9823
right

5
9975
9975
right

4
9966
9966
right

5
9683
9683
right

5
9981
9981
right

4
9983
9983
right

5
9966
9966
right

5
9967
9967
right

5
9870
9870
right

当然，test4和test5各自维系的两个栈其实差别和一个栈不大，因为两个栈是同时进栈同时出栈的。
其实，即使两个栈并非同时进出栈也是可以的，只是对于这里的例子来说写不出这么复杂。
实际上，任意多的栈，任意进出栈，都是可以的。
这样就可以做到更加灵活的应用。
软件的扩展性比硬件强，我想，这就是软件的用处吧。

还是这个取最大值,举个含有多个栈,每个栈入出并不完全一致的例子,这里的test6函数

#!/bin/awk -f
func test1(a,start,len)
{
        if(len<=1)
                return a[start];
        x = test1(a,start,int(len/2));
        y = test1(a,start+int(len/2),len-int(len/2));
        return (x>y)?x:y;
}
func test2(a,start,len)
{
        if(len<=1)
                return a[start];
        testlen++;
        testa[testlen] = test2(a,start,int(len/2));
        testlen++;
        testa[testlen] = test2(a,start+int(len/2),len-int(len/2));
        testlen-=2;
        return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];
}
func test3(a,start,len)
{
        if(len<=1) {
                return a[start];
        }
        V = V";"test3(a,start,int(len/2));
        V = V";"test3(a,start+int(len/2),len-int(len/2));
        xx = V;
        sub(/.*;/,"",xx);
        sub(/;[^;]+$/,"",V);
        yy = V;
        sub(/.*;/,"",yy);
        sub(/;[^;]+$/,"",V);
        return int(xx)>int(yy)?int(xx):int(yy);
}
func test4(a,start,len)
{
        if(len<=1)
                return a[start];
        testlenx++;
        testleny++;
        testax[testlenx] = test4(a,start,int(len/2));
        testay[testleny] = test4(a,start+int(len/2),len-int(len/2));
        testlenx-=1;
        testleny-=1;
        return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
}
func test5(a,start,len)
{
        if(len<=1) {
                return a[start];
        }
        V1 = V1";"test5(a,start,int(len/2));
        V2 = V2";"test5(a,start+int(len/2),len-int(len/2));
        xx = V1;
        sub(/.*;/,"",xx);
        sub(/;[^;]+$/,"",V1);
        yy = V2;
        sub(/.*;/,"",yy);
        sub(/;[^;]+$/,"",V2);
        return int(xx)>int(yy)?int(xx):int(yy);
}
func test6(a,start,len)
{
        if(len <= 1) {
                return a[start];
        } else if(len == 2) {
                return (a[start]>a[start+1])?a[start]:a[start+1];
        } else if(len == 3) {
                var1 = (a[start]>a[start+1])?a[start]:a[start+1];
                return (var1>a[start+2])?var1:a[start+2];
        }
        var2 = int(rand()*10000)%3+2;
        if(var2 == 2) {
                testlenx++;
                testleny++;
                testax[testlenx] = test6(a,start,int(len/2));
                testay[testleny] = test6(a,start+int(len/2),len-int(len/2));
                testlenx-=1;
                testleny-=1;
                return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
        } else if(var2 == 3) {
                testlenx++;
                testleny++;
                testlenz++;
                testax[testlenx] = test6(a,start,int(len/3));
                testay[testleny] = test6(a,start+int(len/3),int(len/3));
                testaz[testlenz] = test6(a,start+2*int(len/3),len-2*int(len/3));
                testlenx-=1;
                testleny-=1;
                testlenz-=1;
                var1 = (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
                return ((var1>testaz[testlenz+1])?var1:testaz[testlenz+1]);
        } else if(var2 == 4) {
                testlenx++;
                testleny++;
                testlenz++;
                testlenA++;
                testax[testlenx] = test6(a,start,int(len/4));
                testay[testleny] = test6(a,start+int(len/4),int(len/4));
                testaz[testlenz] = test6(a,start+2*int(len/4),int(len/4));
                testaA[testlenA] = test6(a,start+3*int(len/4),len-3*int(len/4));
                testlenx-=1;
                testleny-=1;
                testlenz-=1;
                testlenA-=1;
                var1 = (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
                var4 = (testaz[testlenz+1]>testaA[testlenA+1])?testaz[testlenz+1]:testaA[testlenA+1];
                return ((var1>var4)?var1:var4);
        }
}
BEGIN {
        srand(systime());
}
NR==1{
        way=$1;
        print $1
}
NR==2{
        max=$1;
        for(i=2;i<=NF;i++)
                if($i > max)
                        max = $i;
        print max;
        for(i=1;i<=NF;i++)
                a[i] = $i;
        if(way == 2)
                print test2(a,1,NF);
        else if(way == 3)
                print test3(a,1,NF);
        else if(way == 4)
                print test4(a,1,NF);
        else if(way == 5)
                print test5(a,1,NF);
        else if(way == 6)
                print test6(a,1,NF);
        else
                print test1(a,1,NF);
        exit(0);
}

　　

转载于:https://www.cnblogs.com/Colin-Cai/p/7087128.html

相关文章：

  • python if 语句，布尔运算
  • (cljs/run-at (JSVM. :browser) 搭建刚好可用的开发环境!)
  • IPv4 forwarding is disabled. Networking will not work.
  • 技术架构组工作职责
  • 第7章 高级分组
  • MySQL数据库的高可用方案总结
  • 一个扎心的错——Consider defining a bean of type 'java.lang.String' in your configuration.
  • Buffer源码深入分析
  • 以太坊共识机制
  • 浅析NSTimer CADisplayLink内存泄露
  • hdu 2227
  • ViewPager+RadioGroup实现标题栏切换,Fragment切换
  • 通过获取异步加载JS文件进度实现一个canvas环形loading图
  • PyTorch快速入门教程五(rnn)
  • 故障排查
  • (ckeditor+ckfinder用法)Jquery,js获取ckeditor值
  • 【跃迁之路】【463天】刻意练习系列222（2018.05.14）
  • Android组件 - 收藏集 - 掘金
  • CentOS 7 修改主机名
  • gcc介绍及安装
  • golang中接口赋值与方法集
  • jquery ajax学习笔记
  • js继承的实现方法
  • RxJS 实现摩斯密码(Morse) 【内附脑图】
  • vue数据传递--我有特殊的实现技巧
  • vue中实现单选
  • 测试如何在敏捷团队中工作？
  • 发布国内首个无服务器容器服务，运维效率从未如此高效
  • 开发了一款写作软件(OSX,Windows)，附带Electron开发指南
  • 跨域
  • 前端技术周刊 2019-01-14：客户端存储
  • 前端之Sass/Scss实战笔记
  • 算法之不定期更新（一）（2018-04-12）
  • 智能网联汽车信息安全
  • 自制字幕遮挡器
  • 最近的计划
  • 阿里云API、SDK和CLI应用实践方案
  • ​io --- 处理流的核心工具​
  • #{}和${}的区别？
  • #mysql 8.0 踩坑日记
  • $.extend({},旧的,新的)；合并对象，后面的覆盖前面的
  • (C#)Windows Shell 外壳编程系列4 - 上下文菜单(iContextMenu)（二）嵌入菜单和执行命令...
  • (MIT博士）林达华老师－概率模型与计算机视觉”
  • （SpringBoot）第二章：Spring创建和使用
  • （超详细）语音信号处理之特征提取
  • （二）c52学习之旅-简单了解单片机
  • （附源码）spring boot基于Java的电影院售票与管理系统毕业设计 011449
  • （附源码）springboot工单管理系统 毕业设计 964158
  • (一)kafka实战——kafka源码编译启动
  • (原創) X61用戶，小心你的上蓋!! (NB) (ThinkPad) (X61)
  • (转)Android学习系列(31)--App自动化之使用Ant编译项目多渠道打包
  • (轉貼) VS2005 快捷键 (初級) (.NET) (Visual Studio)
  • .NET Core 2.1路线图
  • .NET 设计一套高性能的弱事件机制
  • .NET 自定义中间件 判断是否存在 AllowAnonymousAttribute 特性 来判断是否需要身份验证