“通俗易懂的文字”+“经典案例”让你顺利入门“递归算法”

(大佬请绕行,比较基础!)递归是非常常见的一种算法,非常经典,可以解决非常多的问题。但我估计虽然大部分人知道递归,也能看得懂递归,但在实际运用中,很容易被递归给搞晕(数据,变量,函数等来回的出栈入栈)。今天写篇文章分享下,或许,能够给你带来一些帮助。

递归是一种解决问题的方法,将问题分解成规模更小的问题,不断地调用自身,解决小问题,直至问题不可再分,递归一般都是从结束条件一步一步往回计算

  1. 递归必须有一个可以结束的条件,不然会陷入无限递归的噩梦中。而且,我们必须能根据当前参数的值,能够直接知道函数的返回结果是什么
  2. 递归算法必须能改变状态向基本结束条件演进(必须能够有个最小规模的情况最为结束条件)
  3. 递归算法必须调用自身

当一个函数被调用的时候,系统会把调用时的现场数据押入到系统调用栈(某段内存空间)

  • 现场数据就是指函数变量名,函数所包含的参数,局部变量等
  • 每次调用,压入栈的现场数据称为栈帧
  • 当函数返回时,从调用栈的栈顶取得返回地址,恢复现场,弹出栈,按内存地址返回

一般来讲,系统调用栈容量有限,当递归的层数太多,超过递归最大层数,会报错,目前python支持最高1000层的调用

查看python的最大递归层数

其实递归的理解从语言上讲,基本上就这么多。下面开始分析一些代码实现

该数列由0和1开始,后面的每一项数字都是前面两项数字的和,数列的规律呈现为这个样子:[0,1,1,2,3,5,8,13,21···],我们根据上述的递归三大定律分析来看:

  1. 首先确认递归结束的条件,那么就是0,1,2这三个值,是定死的值
  2. 对于大于2的索引值,有如下规律,f(n) = f(n – 1) + f(n – 2),于是就可以构造如下递归函数求得计算结果
  3. 因为要保存每一次的计算结果,最后累加,所以要有return值,将每一次递归的结果记录

代码实现如下

将十进制数转换为2/8/16进制的字符串形式

  1. 递归的结束条件为:当前数值小于要转换的进制大小了
  2. 比如说转换为2进制,那么就始终除以2取余数,那么就可以利用递归的算法拿到每次的结果,将问题规模一次次的减小

代码如下

要做这么个事情:“abcdefg” ->“gfedcba”(当然有很多方法,这里主要讲递归实现)

  1. 递归结束条件为:原字符串只剩下最后一个的时候,这时候就不需要反转了
  2. 每次收集当前字符串的s[0]的字符作为反转,减小问题规模

代码如下

本文主要分享了递归相关的概念和理解,并提供了几个最最基础的利用递归思想解决问题的代码(可能你会觉得本篇中的代码很简单,主要是不想给刚接触递归的那些人弄昏),下一篇会分享几个稍微复杂一点点的案例(但整体还是递归问题中比较简单的那种)。我觉得,最开始接触递归,懵逼是正常的,只有不断的练习,不断的思考,才有可能用好这种牛逼的方法。

我是一名奋战在编程界的pythoner,工作中既要和数据打交道,也要和erp系统,web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧,在实际应用中遇到的问题以及解决方案,或者源码的阅读等等,欢迎大家一起来讨论!如果觉得写得还不错,欢迎关注点赞,谢谢。

怎么通俗的理解Netty呢?

目录

有了Netty,你可以实现自己的HTTP服务器,FTP服务器,UDP服务器,RPC服务器,WebSocket服务器,Redis的Proxy服务器,MySQL的Proxy服务器等等。

如果你想知道Nginx是怎么写出来的,如果你想知道Tomcat和Jetty是如何实现的,如果你也想实现一个简单的Redis服务器,那都应该好好理解一下Netty,它们高性能的原理都是类似的。

看一下传统的HTTP服务器的原理:

  1. 创建一个ServerSocket,监听并绑定一个端口
  2. 一系列客户端来请求这个端口
  3. 服务器使用Accept,获得一个来自客户端的Socket连接对象
  4. 启动一个新线程处理连接
    1. 读Socket,得到字节流
    2. 解码协议,得到Http请求对象
    3. 处理Http请求,得到一个结果,封装成一个HttpResponse对象
    4. 编码协议,将结果序列化字节流
    5. 写Socket,将字节流发给客户端
  5. 继续循环步骤3

HTTP服务器之所以称为 HTTP 服务器,是因为编码解码协议是HTTP协议,如果协议是Redis协议,那它就成了Redis服务器,如果协议是WebSocket,那它就成了WebSocket服务器,等等。

使用Netty你就可以定制编解码协议,实现自己的特定协议的服务器。

上面我们说的是一个传统的多线程服务器,这个也是Apache处理请求的模式。在高并发环境下,线程数量可能会创建太多,操作系统的任务调度压力大,系统负载也会比较高。那怎么办呢?

于是 NIO 诞生了,NIO并不是Java独有的概念,NIO代表的一个词汇叫着IO多路复用。它是由操作系统提供的系统调用,早期这个操作系统调用的名字是 select ,但是性能低下,后来渐渐演化成了Linux下的epoll和Mac里的kqueue。我们一般就说是epoll,因为没有人拿苹果电脑作为服务器使用对外提供服务。而Netty就是基于Java NIO技术封装的一套框架。为什么要封装,因为原生的Java NIO使用起来没那么方便,而且还有臭名昭著的bug,Netty把它封装之后,提供了一个易于操作的使用模式和接口,用户使用起来也就便捷多了。

那NIO究竟是什么东西呢?

NIO的全称是NoneBlocking IO,非阻塞IO,区别与BIO,BIO的全称是Blocking IO,阻塞IO。那这个阻塞是什么意思呢?

  1. Accept是阻塞的,只有新连接来了,Accept才会返回,主线程才能继
  2. Read是阻塞的,只有请求消息来了,Read才能返回,子线程才能继续处理
  3. Write是阻塞的,只有客户端把消息收了,Write才能返回,子线程才能继续读取下一个请求

所以传统的多线程服务器是BlockingIO模式的,从头到尾所有的线程都是阻塞的。这些线程就干等在哪里,占用了操作系统的调度资源,什么事也不干,是浪费。

那么NIO是怎么做到非阻塞的呢?

它用的是 事件机制 。它可以用一个线程把Accept,读写操作,请求处理的逻辑全干了。如果什么事都没得做,它也不会死循环,它会将线程休眠起来,直到下一个事件来了再继续干活,这样的一个线程称之为NIO线程。

Netty是建立在NIO基础之上,Netty在NIO之上又提供了更高层次的抽象。

在Netty里面,Accept连接可以使用单独的线程池去处理,读写操作又是另外的线程池来处理。

Accept连接和读写操作也可以使用同一个线程池来进行处理。而请求处理逻辑既可以使用单独的线程池进行处理,也可以跟放在读写线程一块处理。线程池中的每一个线程都是NIO线程。用户可以根据实际情况进行组装,构造出满足系统需求的并发模型。

Netty提供了内置的常用编解码器,包括行编解码器[一行一个请求],前缀长度编解码器[前N个字节定义请求的字节长度],可重放解码器[记录半包消息的状态],HTTP编解码器,WebSocket消息编解码器等等

Netty提供了一些列生命周期回调接口,当一个完整的请求到达时,当一个连接关闭时,当一个连接建立时,用户都会收到回调事件,然后进行逻辑处理。

Netty可以同时管理多个端口,可以使用NIO客户端模型,这些对于RPC服务是很有必要的。

Netty除了可以处理TCP Socket之外,还可以处理UDP Socket。

在消息读写过程中,需要大量使用ByteBuffer,Netty对ByteBuffer在性能和使用的便捷性上都进行了优化和抽象。

本质:

1)JBoss做的一个Jar包。

2)目的:快速开发高性能、高可靠性的网络服务器和客户端程序。

3)优点:提供异步的、事件驱动的网络应用程序框架和工具。

这里 EchoServerHandler 是其业务逻辑的实现者,大致代码如下:

看看 EchoServerHandler 的代码,其中的参数: public void messageReceived(ChannelHandlerContext ctx, MessageEvent e) ,MessageEvent就是一个事件。这个事件携带了一些信息,例如这里 e.getMessage() 就是消息的内容,而 EchoServerHandler 则描述了处理这种事件的方式。一旦某个事件触发,相应的Handler则会被调用,并进行处理。这种事件机制在UI编程里广泛应用,而Netty则将其应用到了网络编程领域。

在Netty里,所有事件都来自 ChannelEvent 接口,这些事件涵盖监听端口、建立连接、读写数据等网络通讯的各个阶段。而事件的处理者就是 ChannelHandler ,这样,不但是业务逻辑,连网络通讯流程中底层的处理,都可以通过实现 ChannelHandler 来完成了。事实上,Netty内部的连接处理、协议编解码、超时等机制,都是通过handler完成的。

下图描述了Netty进行事件处理的流程。 Channel 是连接的通道,是ChannelEvent的产生者,而 ChannelPipeline 可以理解为ChannelHandler的集合。

除了之前说到的事件驱动机制之外,Netty的核心功能还包括两部分:

  • Zero-Copy-Capable Rich Byte Buffer零拷贝的Buffer。为什么叫零拷贝?因为在数据传输时,最终处理的数据会需要对单个传输层的报文,进行组合或者拆分。NIO原生的ByteBuffer无法做到这件事,而Netty通过提供Composite(组合)和Slice(切分)两种Buffer来实现零拷贝。这部分代码在 org.jboss.netty.buffer 包中。这里需要额外注意,不要和操作系统级别的Zero-Copy混淆了, 操作系统中的零拷贝主要是用户空间和内核空间之间的数据拷贝, NIO中通过DirectBuffer做了实现.
  • Universal Communication API统一的通讯API。这个是针对Java的Old I/O和New I/O,使用了不同的API而言。Netty则提供了统一的API( org.jboss.netty.channel.Channel )来封装这两种I/O模型。这部分代码在 org.jboss.netty.channel 包中。

此外,Protocol Support功能通过handler机制实现。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com

点赞 0
收藏 0

文章为作者独立观点不代本网立场,未经允许不得转载。