wenmo8 发布的文章

大家好,我是苏三,又跟大家见面了。

前言

最近有位小伙伴在我的技术群里,问了我一个问题:服务down机了,线程池中如何保证不丢失数据?

这个问题挺有意思的,今天通过这篇文章,拿出来跟大家一起探讨一下。

1 什么是线程池?

之前没有线程池的时候,我们在代码中,创建一个线程有两种方式:

  1. 继承Thread类
  2. 实现Runnable接口

虽说通过这两种方式创建一个线程,非常方便。

但也带来了下面的问题:

  1. 创建和销毁一个线程,都是比较耗时,频繁的创建和销毁线程,非常影响系统的性能。
  2. 无限制的创建线程,会导致内存不足。
  3. 有新任务过来时,必须要先创建好线程才能执行,不能直接复用线程。

为了解决上面的这些问题,Java中引入了:
线程池

它相当于一个存放线程的池子。

使用线程池带来了下面3个好处:

  1. 降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。
  2. 提高响应速度。当任务到达时,可以直接使用已有空闲的线程,不需要的等到线程创建就能立即执行。
  3. 提高线程的可管理性。线程是稀缺资源,如果无限制的创建,不仅会消耗系统资源,还会降低系统的稳定性。而如果我们使用线程池,可以对线程进行统一的分配、管理和监控。

2 线程池原理

先看看线程池的构造器:

public ThreadPoolExecutor(
    int corePoolSize,
    int maximumPoolSize,
    long keepAliveTime,
    TimeUnit unit,
    BlockingQueue<Runnable> workQueue,
    ThreadFactory threadFactory,
    RejectedExecutionHandler handler)
  • corePoolSize:核心线程数,线程池维护的最少线程数。
  • maximumPoolSize:最大线程数,线程池允许创建的最大线程数。
  • keepAliveTime:线程存活时间,当线程数超过核心线程数时,多余的空闲线程的存活时间。
  • unit:时间单位。
  • workQueue:任务队列,用于保存等待执行的任务。
  • threadFactory:线程工厂,用于创建新线程。
  • handler:拒绝策略,当任务无法执行时的处理策略。

线程池的核心流程图如下:

线程池的工作过程如下:

  1. 线程池初始化:根据corePoolSize初始化核心线程。
  2. 任务提交:当任务提交到线程池时,根据当前线程数判断:
  • 若当前线程数小于corePoolSize,创建新的线程执行任务。
  • 若当前线程数大于或等于corePoolSize,任务被加入workQueue队列。
  1. 任务处理:当有空闲线程时,从workQueue中取出任务执行。
  2. 线程扩展:若队列已满且当前线程数小于maximumPoolSize,创建新的线程处理任务。
  3. 线程回收:当线程空闲时间超过keepAliveTime,多余的线程会被回收,直到线程数不超过corePoolSize。
  4. 拒绝策略:若队列已满且当前线程数达到maximumPoolSize,则根据拒绝策略处理新任务。

说白了在线程池中,多余的任务会被放到workQueue任务队列中。

这个任务队列的数据保存在内存中。

这样就会出现一些问题。

接下来,看看线程池有哪些问题。

3 线程池有哪些问题?

在JDK中为了方便大家创建线程池,专门提供了Executors这个工具类。

3.1 队列过大

Executors.newFixedThreadPool,它可以创建固定线程数量的线程池,任务队列使用的是LinkedBlockingQueue,默认最大容量是Integer.MAX_VALUE。

public static ExecutorService newFixedThreadPool(int nThreads, ThreadFactory threadFactory) {
    return new ThreadPoolExecutor(nThreads, 
                               nThreads,
                                     0L, 
                  TimeUnit.MILLISECONDS,
     new LinkedBlockingQueue<Runnable>(),
                          threadFactory);
}

如果向newFixedThreadPool线程池中提交的任务太多,可能会导致LinkedBlockingQueue非常大,从而出现OOM问题。

3.2 线程太多

Executors.newCachedThreadPool,它可以创建可缓冲的线程池,最大线程数量是Integer.MAX_VALUE,任务队列使用的是SynchronousQueue。

public static ExecutorService newCachedThreadPool() {
  return new ThreadPoolExecutor(0, 
                Integer.MAX_VALUE,
                               60L, 
                  TimeUnit.SECONDS,
    new SynchronousQueue<Runnable>());
}

如果向newCachedThreadPool线程池中提交的任务太多,可能会导致创建大量的线程,也会出现OOM问题。

3.3 数据丢失

如果线程池在执行过程中,服务突然被重启了,可能会导致线程池中的数据丢失。

上面的OOM问题,我们在日常开发中,可以通过自定义线程池的方式解决。

比如创建这样的线程池:

new ThreadPoolExecutor(8, 
                       10,
                       30L, 
     TimeUnit.MILLISECONDS,
    new ArrayBlockingQueue<Runnable>(300),
            threadFactory);

自定义了一个最大线程数量和任务队列都在可控范围内线程池。

这样做基本上不会出现OOM问题。

但线程池的数据丢失问题,光靠自身的功能很难解决。

4 如何保证数据不丢失?

线程池中的数据,是保存到内存中的,一旦遇到服务器重启了,数据就会丢失。

之前的系统流程是这样的:

用户请求过来之后,先处理业务逻辑1,它是系统的核心功能。

然后再将任务提交到线程池,由它处理业务逻辑2,它是系统的非核心功能。

但如果线程池在处理的过程中,服务down机了,此时,业务逻辑2的数据就会丢失。

那么,如何保证数据不丢失呢?

答:需要
提前做持久化

我们优化的系统流程如下:

用户请求过来之后,先处理业务逻辑1,紧接着向DB中写入一条任务数据,状态是:待执行。

处理业务逻辑1和向DB写任务数据,可以在同一个事务中,方便出现异常时回滚。

然后有一个专门的定时任务,每个一段时间,按添加时间升序,分页查询状态是待执行的任务。

最早的任务,最先被查出来。

然后将查出的任务提交到线程池中,由它处理业务逻辑2。

处理成功之后,修改任务的待执行状态为:已执行。

需要注意的是:业务逻辑2的处理过程,要做幂等性设计,同一个请求允许被执行多次,其结果不会有影响。

如果此时,线程池在处理的过程中,服务down机了,业务逻辑2的数据会丢失。

但此时DB中保存了任务的数据,并且丢失那些任务的状态还是:待执行。

在下一次定时任务周期开始执行时,又会将那些任务数据重新查询出来,重新提交到线程池中。

业务逻辑2丢失的数据,又自动回来了。

如果要考虑失败的情况,还需要在任务表中增加一个
失败次数
字段。

在定时任务的线程池中执行业务逻辑2失败了,在下定时任务执行时可以自动重试。

但不可能无限制的一直重试下去。

当失败超过了一定的次数,可以将任务状态改成:失败。

这样后续可以人工处理。

最后说一句(求关注,别白嫖我)
如果这篇文章对您有所帮助,或者有所启发的话,帮忙扫描下发二维码关注一下,您的支持是我坚持写作最大的动力。

求一键三连:点赞、转发、在看。
关注公众号:【苏三说技术】,在公众号中回复:面试、代码神器、开发手册、时间管理有超赞的粉丝福利,另外回复:加群,可以跟很多BAT大厂的前辈交流和学习。

AirPlay
协议是苹果开发、广泛应用于iPhone、iPad和Mac设备,可以通过WiFi将iPhone、iPad等iOS设备上的图片、音频、视频通过无线的方式传输到支持AirPlay 设备。即移动终端显示什么电视大屏就显示什么。随着AirPlay协议逐步普及,国内越来越多网络机顶盒,智能电视都集成了AirPlay协议。AirPlay的镜像效果是所有投屏方式中效果最佳的。

如有需要对接AirPlay,接收和发送都有开源代码可以参考:

接收端
SteeBono/airplayreceiver: Open source implementation of AirPlay 2 Mirroring / Audio protocol. (github.com)
,接收兼容场景会更多点,自研投屏协议需要考虑兼容外部原生投屏协议、提升用户体验。

发送端
openairplay/AirPlayer: AirPlayer is a .NET project for streaming photos, video and music to airplay devices. (github.com)

Miracast
协议是由Wi-Fi联盟于2012年所制定,以WiFi直连为基础的无线投屏协议。Miracast采用的技术都来自Wi-Fi联盟的电子制造商和芯片制造商的团队研发,其兼容性和广泛应用性无可厚非,英伟达、英特尔、德州仪器包括国内联发科等芯片制造商都已支持Miracast协议。Miracast无线投屏是兼容性最广的投屏协议,国内大多数Android手机、智能电视都支持Miracast投屏协议。它仅需要手机和电视支持Miracast投屏协议,并且手机和电视处于同一局域网内,即可通过Miracast将视频或照片直接在电视或其他设备播放。Miracast 不是设备或软件,而是 Wi-Fi Alliance 规范下的一项技术的名称。以上两项技术,是应用最广的。

UWP应用可以使用Windows.Media.Casting命名空间下CastingDevicePicker类接受Miracast数据:
Windows.Media.Casting 命名空间 - Windows UWP applications | Microsoft Learn
,WPF也可以使用WindowsXamlHost承载画面

详细的可参考某个大佬的文章:
一文带你详尽剖析Miracast投屏开发和调试_android miracast 开发-CSDN博客

以上这俩个协议是应用最多的,私有投屏协议考虑兼容的话,笔记本、手机投过来接收端兼容这俩个就够了。

DLNA
协议是索尼、英特尔、微软等发起的一套 PC、移动设备、消费电器之间互联互通的协议,这是一个早期的标准。支持在家庭网络中共享多媒体内容,许多智能电视和家庭影院系统支持DLNA,DLNA与苹果的AirPlay比较相似,都可以让你手机中的媒体内容投放到电视屏幕里。不同的是手机上的DLNA 并没有类似AirPlay或Miracast的投屏镜像功能。而是相当于从一个设备的本地存储中拿内容到另外一个设备上去display(展示),并且不影响当前设备的其他操作。目前DLNA只支持将手机的照片和视频投送到大屏幕中。

Google Cast (Chromecast)
协议是谷歌开发的无线投屏技术。通过Google Cast,可以将多媒体内容从移动设备或PC传输到电视或音响设备。与AirPlay相比,Chromecast体验却大不相同。相比镜像投屏,Chromecast体验更接近于DLNA。

WiDi(Wireless Display)
由Intel开发,是一种支持Windows10笔记本无线投屏方式,无需安装软件,即可无线投屏。

HDMI
协议是HDMI传输解决方案,也叫有线投屏,能够实现无损传输,但成本较高,发射端需要独立供电,并且需要无障碍传输。HDMI线一般是几米长,也有15米的线。10米以上传输稳定性可能有一定风险,超长线建议与设备高压验证后再导入。我这边对接的京东,他们自己研发软件投屏用于内部员工投屏,访客采用有线HDMI方式,场景基本就覆盖了。

私有投屏协议
是各公司自有的解决方案,种类繁多,产品形态以安装软件为主,手机需要安装APP,网络通即可投屏

我了解到在自研投屏的公司就有:CVTE、宜享、海信

宜享 -- 海信、华为、H3C大屏都是OEM贴牌宜享的产品,宜享也有公版产品,京东可以买到

海信,应该是2023年(时间我不确定哈、但2021年确定还是OEM的)开始自研投屏了,2024年初招聘网站上有招聘传屏专家岗位。

毕竟投屏是大屏最核心的功能场景,稳定性以及用户体验还是要抓在自己手里,还能省成本不是,基于wifi6的typec投屏器也要200以上人民币

当然投屏还是比较复杂的,要做软件还要做硬件投屏器,整个链路有采集、编解码、传输、显示,目前主流最新技术要支持,如BYOM最大化利用大屏设备、超声波自动完成设备配对,软件要支持安卓、Windows、Linux信创以及未来确定的鸿蒙。开发成本比较大

Mac上HomeBrew安装及换源教程

Mac的Mac OS系统来源于Unix系统,得益于此Mac系统的使用类似于Linux,因此Linux系统中的包管理概念也适用于Mac,而HomeBrew便是其中的一个优秀的包管理工具,而包管理工具是什么呢?软件包管理工具,拥有安装、卸载、更新、查看、搜索等功能,在终端中通过简单的指令可以实现各类功能包的管理,而不用关心各种依赖和文件路径情况。因此无论是什么驱动?开发工具?都可以在HomeBrew中进行快捷下载而不像Win下有着繁杂的环境管理。

安装教程

想要快速的检查电脑中有无HomeBrew只需要一行命令

brew -v #检查电脑是否存在HomeBrew

如果终端打印了版本信息的话证明电脑中存在HomeBrew,如果打印未知命令的话代表电脑中没有HomeBrew环境。

类似于机器人开发中的鱼香ROS可以一键安装需要的环境,HomeBrew也提供了一键安装的脚本以供用户一键进行安装:

· 如果需要重新安装请先卸载HomeBrew:

/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/uninstall.sh)"

· 一键安装的命令(可能需要Science On The Net):

/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

如果遇到这个报错:curl: (7) Failed to connect to raw.githubusercontent.com port 443: Connection refused则代表网络无法访问需要Science On The Net,一般来说XXX网后这个安装和下载的速度非常的迅速

附上常用的HomeBrew指令

· 想要查找HomeBrew的用户帮助界面可以输入

brew -h 
brew help

· 查看HomeBrew的版本

brew -v

· 更新HomeBrew

brew update

HomeBrew换源命令

HomeBrew默认的源在国外,平时正常使用非常的慢因此我们可以将其替换为国内源

· 查看当前源

cd "$(brew --repo)" && git remote -v

替换为清华源

# 替换各个源
$ git -C "$(brew --repo)" remote set-url origin https://mirrors.tuna.tsinghua.edu.cn/git/homebrew/brew.git
$ git -C "$(brew --repo homebrew/core)" remote set-url origin https://mirrors.tuna.tsinghua.edu.cn/git/homebrew/homebrew-core.git
$ git -C "$(brew --repo homebrew/cask)" remote set-url origin https://mirrors.tuna.tsinghua.edu.cn/git/homebrew/homebrew-cask.git

# zsh 替换 brew bintray 镜像
$ echo 'export HOMEBREW_BOTTLE_DOMAIN=https://mirrors.tuna.tsinghua.edu.cn/homebrew-bottles' >> ~/.zshrc
$ source ~/.zshrc

# bash 替换 brew bintray 镜像
$ echo 'export HOMEBREW_BOTTLE_DOMAIN=https://mirrors.tuna.tsinghua.edu.cn/homebrew-bottles' >> ~/.bash_profile
$ source ~/.bash_profile

# 刷新源
$ brew update

替换为中科大源

# 替换各个源
$ git -C "$(brew --repo)" remote set-url origin https://mirrors.ustc.edu.cn/brew.git
$ git -C "$(brew --repo homebrew/core)" remote set-url origin https://mirrors.ustc.edu.cn/homebrew-core.git
$ git -C "$(brew --repo homebrew/cask)" remote set-url origin https://mirrors.ustc.edu.cn/homebrew-cask.git

# zsh 替换 brew bintray 镜像
$ echo 'export HOMEBREW_BOTTLE_DOMAIN=https://mirrors.ustc.edu.cn/homebrew-bottles' >> ~/.zshrc
$ source ~/.zshrc

# bash 替换 brew bintray 镜像
$ echo 'export HOMEBREW_BOTTLE_DOMAIN=https://mirrors.ustc.edu.cn/homebrew-bottles' >> ~/.bash_profile
$ source ~/.bash_profile

# 刷新源
$ brew update

Ubuntu 16.04.4 通过docker安装单机fastdfs

前言

很久没有写技术播客了,这是一件很不应该的事情,做完了事情应该有沉淀的。

我先说一点前情提要,公司的fastdfs突然就挂了,做过的操作就是日志文件太大了,所以把日志文件给删了,理论上这个动作应该不影响程序运行才对。

然后tracker怎么都启动不起来了。会报下面这个错误。

file: tracker_service.c, line: 2079, client ip: 47.xxx.xxx.52, group_name: group1, new ip address 172.xxx.xxx.217 != client ip address 47.xxx.xxx.52

我的tracker和storage都部署在同一台服务器上,其中47开头的是同一台服务器的公网IP,172开头的是这台服务器的内网IP。

然后tracker、storage和client的配置文件,我都改过一遍,都改成内网、都改成公网、一个是公网、一个是内网。反正就是不行。

不过我后来在搜索后续答案的过程中有受到一点启发,就是直接改一下host文件,给ip随便分配一个域名,这样后期的配置都用域名,有可能可以解决这个问题。

因为存储的数据都是从其他地方拉取过来的,只是过一个临时的中转,所以,里面的数据丢了也无所谓,于是,我就想,我索性重新再装一个fastdfs好了。

但是fastdfs并不能通过一个命令直接卸载,所以,我直接删除了它相关的各种文件。

但是有可能我删的不是很干净,在我装最新版本fastdfs的时候,编译
libserverframe
的时候,报下面这个错。

Makefile:59: recipe for target 'fdfs_monitor' failed

搜索了一圈,提到这个问题的人并不多,然后我试了直接从git上clone代码的方式,去git上下载压缩包再解压的方式,都编译不过去。

初步判断是依赖库的版本冲突了,或者有缺失。

这里再提一个题外话,我们在使用
make intall
命令的时候,应该习惯性加上
--prefix
参数,配置文件的安装路径,如下:

make install --prefix=/opt/application

如果不配的话,安装后可执行文件默认放在
/usr/local/bin
,库文件默认放在
/usr/local/lib
,配置文件默认放在
/usr/local/etc
,其它的资源文件放在
/usr/local/share

安装一时爽,卸载火葬场。

因为可能原因是版本冲突,然后我现在也卸载不干净了,于是我就想到了docker,docker是另外开辟出来的一个独立的环境,不受当前主环境影响,而且服务器上还有其他正在跑的服务,我也不可能重置服务器。不得不说docker真是一个好东西啊,是哪个小天才发明的。

fastdfs镜像选择

fastdfs并没有提供官方的镜像,所以只能用网友们自主创建的。

https://hub.docker.com/search?q=fastdfs

收藏最多的是一个season的镜像,不过,我看它的版本很老了,好像才1.2版,更新时间也是9年前了。所以我没有用这个,我看到好几篇文章里都用的是delron的镜像,所以我也用的这一个。当然这个也挺老了,6年前更新的。

但我急于解决问题,也没有心思去好好研究和挑选了,总之,亲测它单机好使,使用起来也比较方便,集成了nginx,可以直接通过浏览器访问资源。

镜像的拉取

如果你的这台机器,之前没有用过docker的话,还是一个老生常谈的问题,你很有可能连接超时,然后拉取失败,所以要配置镜像。

如果你还没有安装过docker,也可以先安装一下:

apt install docker.io

修改镜像配置文件 :

 vim /etc/docker/daemon.json

把各种镜像的地址加上(没有缩进的那几个就是):

image-20240829094121066

下面是从网上搜到的镜像:

DaoCloud	https://docker.m.daocloud.io
阿里云	https://<your_code>.mirror.aliyuncs.com(阿里云提供了镜像源:https://cr.console.aliyun.com/cn-hangzhou/instances/mirrors 登录后你会获得一个专属的地址)
Docker镜像代理	https://dockerproxy.com
百度云	https://mirror.baidubce.com
南京大学	https://docker.nju.edu.cn
中科院	https://mirror.iscas.ac.cn

"https://yxzrazem.mirror.aliyuncs.com",
"http://hub-mirror.c.163.com",
"https://registry.docker-cn.com",
"http://hub-mirror.c.163.com",
"https://docker.mirrors.ustc.edu.cn"

来一份示例方便粘贴

{
    "registry-mirrors": [
        "https://do.nark.eu.org",
        "https://dc.j8.work",
        "https://docker.m.daocloud.io",
        "https://dockerproxy.com",
        "https://docker.mirrors.ustc.edu.cn",
        "https://docker.nju.edu.cn",
        "https://ustc-edu-cn.mirror.aliyuncs.com/",
        "https://hub-mirror.c.163.com",
        "https://mirror.baidubce.com"
    ]
}

重新加载配置,并重启docker:

systemctl daemon-reload
systemctl restart docker

运行docker的tracker服务:

# 先创建文件夹,文件夹随便定义,我这里是为了方便,直接延用了别人播客的定义(其中-p是可以直接创建多级目录)
mkdir -p /mydata/fastdfs/tracker
cd /mydata/fastdfs/tracker
# 执行docker命令
docker run -d --name tracker --network=host -v /mydata/fastdfs/tracker:/var/fdfs delron/fastdfs tracker
# 注意:tracker服务默认的端口为22122

运行docker的storage服务:

# 创建文件夹
mkdir -p /mydata/fastdfs/storage
cd /mydata/fastdfs/storage
# 执行命令
docker run -d --name storage --network=host  -e TRACKER_SERVER=x.x.x.x:22122 -v /mydata/fastdfs/storage:/var/fdfs -e GROUP_NAME=group1 delron/fastdfs storage
# 注意:其中TRACKER_SERVER中的ip要修改为你的Tracker服务所在的服务IP地址
# storage默认端口为23000

storage服务中默认安装了nginx,端口为8888

服务测试

1.在/mydata/fastdfs/storage下上传一张图片,1.png

2.进入storage容器,上传图片

# 进入storage容器
docker exec -it storage bash

# 进入容器内文件夹
cd /var/fdfs/

#执行上传命令
/usr/bin/fdfs_upload_file /etc/fdfs/client.conf 1.png

得到文件路径:
group1/M00/00/00/rBA12WbOG4OAW8SKAAM9zD7woDQ406.png

3.浏览器访问图片:

http://47.xxx.xxx.52:8888/group1/M00/00/00/rBA12WbOG4OAW8SKAAM9zD7woDQ406.png

能访问,说明上传下载一切正常。

参考(未必全)

https://rqsir.github.io/2019/04/13/linux-make-install的安装与卸载/

https://blog.csdn.net/weixin_50160384/article/details/139861337

https://www.cnblogs.com/likecoke/p/17495358.html

https://www.cnblogs.com/hequanbao/p/17035045.html

https://blog.csdn.net/zhouzaig/article/details/131412872

https://docs.tanmantang.com/docs/docker/FastDFS.html


递归和for循环(迭代法)很像,都是通过循环去完成一件事。


采用Top-Down思维去设计的递归结构,又会比for多一些不同的能力。
多什么能力?

递归的基础

先复习一下递归,递归的定义:递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。

image

递归的本质就在:
递去

归来
两个流程中。 初学者刚接触会有点抽象,下面通过一些案例来认识。

假设需要你实现一个阶乘的计算函数,
阶乘的定义:
5的阶乘是 5*4*3*2*1=120

def factorial(number):
    if number == 1:
        return 1
    else:
        return number * factorial(number - 1)

print(factorial(5))
// 120

递归需要考虑三个条件:

  1. 将问题拆分成一个重复使用的子问题;
  2. 注意,这个子问题和问题的规模无关;
  3. 必须包含终止条件 (终止条件即初始状态)。

递归的底层实现(不是重点)

递归的底层实现不是本文的重点,了解一下就行。

递归在编程语言的底层实现通常依赖于调用栈(call stack):

  • 调用栈


    • 每次函数调用时,程序会将函数的参数、局部变量和返回地址等信息压入栈帧。
    • 当递归函数调用自身时,会创建新的栈帧压入栈中。
    • 函数执行完毕后,栈帧被弹出,返回控制权给调用者。
  • 基线条件


    • 递归必须有终止条件,否则会导致栈溢出(stack overflow)。
    • 每次递归调用都应该向基线条件靠近。
  • 内存管理


    • 调用栈通常在内存的“栈区”分配。栈的大小有限制,过多的递归调用可能导致栈溢出。
    • 有些语言提供机制来增加栈的大小,但一般不推荐依赖深层递归。

总结:

  • 递归实现的效率和安全性与具体语言的特性和编译器的优化密切相关。

  • 递归的底层实现,就是把相关变量数据(缓存)处理后,一层一层的压入栈,等到了基准条件后,在逐层拿出处理。

计算机眼里的递归:
计算机使用栈来记录正在调用的函数,叫
调用栈

image

有个局部变量 number 记录当前值。

递归的应用场景

  • 处理任意多层事情的场景,都可以考虑用递归。

  • 当问题和子问题具有递推关系,比如杨辉三角、计算阶乘。

  • 具有递归性质的数据结构,比如链表、树、图。

  • 反向性问题,比如取反操作。

编程中 两种解决问题的思维

这个才是本文重点要学习的。

当面对未来未知的情况时,考虑使用使用自上而下解决问题的思维。

两种编写计算函数的方法:

  • 自下而上(Bottom - Up)
    类似循环
  • 自上而下 (Top - Down)
    递归思想

两者区别?
在计算函数时,自下而上和自上而下是两种不同的思维方式和实现策略:

在计算函数时,特别是像阶乘这样的递归函数,可以使用两种主要的实现方式来实现递归计算:
自下而上
(bottom-up)和
自上而下
(top-down)。这些方法各有优缺点,理解它们有助于选择适合的实现方式来解决特定的问题。以下是对这两种实现方式的解释:

自下而上(Bottom-Up)

自下而上
方法,也称为
迭代方法

动态规划方法
,是指从最小的子问题开始逐步构建解决方案,直到解决原始问题。这种方法通常用于动态规划算法中,但也可以用于一些简单的递归问题。

实现思路:

  1. 定义最小问题
    : 从问题的最小子问题开始解决。例如,在计算阶乘时,可以从
    0!

    1!
    开始。
  2. 逐步构建
    : 使用迭代或循环逐步计算更大的问题的解。
  3. 更新和存储
    : 将每个子问题的解存储起来,以便后续使用。

还是以计算阶乘的案例去介绍,自下而上实现方式:

def factorial_bottom_up(n):
    if n < 0:
        raise ValueError("Factorial is not defined for negative numbers")
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# 示例用法
print(factorial_bottom_up(5))  # 输出 120

解释:

  • 从 1 开始迭代计算 2 到 n 的阶乘。
  • 通过逐步乘以每个数字来更新结果,最终得到
    n!

自上而下(Top-Down)

自上而下
方法也称为
递归方法
,是指从解决问题的最上层开始,递归地解决较小的子问题。这种方法在处理递归问题时非常自然(但可能存在重复计算的子问题,有些可以优化)。

实现思路:

  1. 定义主问题
    : 从问题的最上层开始解决。
  2. 递归分解
    : 将主问题递归地分解为较小的子问题。
  3. 基本情况
    : 定义递归的基本情况,以停止递归。

还是以计算阶乘的案例,展示自上而下实现:

def factorial_top_down(n):
    if n < 0:
        raise ValueError("Factorial is not defined for negative numbers")
    if n == 0 or n == 1:
        return 1
    return n * factorial_top_down(n - 1)

# 示例用法
print(factorial_top_down(5))  # 输出 120

解释:


  • n
    开始,递归调用
    factorial_top_down(n - 1)
    ,直到达到基本情况。
  • 在基本情况时返回
    1
    ,逐层返回乘积结果。

总结

  • 自下而上
    :通常是迭代的方法,逐步构建解决方案,适用于动态规划和需要避免重复计算的情况。它通常较为高效,尤其是在解决子问题重复计算时。

  • 自上而下
    :通常是递归的方法,直观地解决问题,但可能会有较高的时间复杂度和空间复杂度,尤其在处理大规模问题时。(可以通过记忆化(Memoization)来优化性能)

自上而下的思考过程——求和案例

一般来说,自下而上的实现过程比较好理解,所以这里多列举一些自上而下的案例帮助思考,

自上而下的编程思考过程:

  1. 把你正在写的函数想象成是别人实现过的函数。
  2. 辨别子问题。
  3. 看看你在子问题上调用函数时会发生什么,然后以此为基础继续。

求和案例
假设我们要写一个 sum 函数,计算数组中所有数的和。如果给函数传入数组[1,2,3,4,5],那么它会返回这些数的和15。

我们需要做的第一件事就是
想象
已经有人实现了 sum 函数。(当然,你可能会有点难以接受,毕竟写函数是我们自己,怎么能假设别人写好了呢! 但可以试着忘掉这一点,先假装 sum 函数已经实现好了。)

接下来,来辨别子问题。
比起科学,这个过程更像是艺术,只要你多练习就能进步。
在这个例子中,可以认为子问题是数组[2,3,4,5],即原数组中除第一个数以外的元素。

最后,来看看在子问题上调用 sum 函数会发生什么 ?
如果 sum 函数“已被正确实现”并且子问题是 [2,3,4,5],那么调用 sum([2,3,4,5])时会发生什么呢?会得到2+3+4+5的和,也就是14。

而要求[1,2,3,4,5]的和,只需向 sum([2,3,4,5])的结果再加上1即可。

请使用编程语言实现一下:

mylist = [1, 2, 3, 4, 5]
def mysum(alist):

    if len(alist) == 1:
        return alist[0]
    else:
		# alist[-1] = alist[len(alist)-1]
        alist[0] += alist[-1]

    return mysum(alist[0:len(alist) - 1])

print(mysum(mylist))
# 15

台阶问题 案例

为什么需要用递归?
image

image

请写出代码:

todo

易位构词生成 案例

这个是一个很实用的案例,之前想将多个pyload 以不同位置组合成一个整体,就遇到这个难题。

image

请写出代码:

todo