数据结构和算法的基本介绍(二)|学习笔记

简介: 快速学习数据结构和算法的基本介绍(二)

开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法的基本介绍(二)】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9827


数据结构和算法的基本介绍(二)


二、数据结构和算法的关系

(1)什么是算法

算法首先是程序的灵魂。什么叫算法?

举个例子,比如将来做 go web 方面的开发,那么都知道 go Web 开发一定要解决几个大的问题,就是一个高并发、海量吞吐,这些问题看 web 服务器, Web 服务器现在最厉害的是 NGKS ,就是比较厉害,写的比较坚如磐石,那么可能会说网站使用服务器集群、数据库读写分离和缓存技术,比如 readys 就可以跑得很快,就可以支撑大并发、高高并发和大流量,用的这些东西肯定是可以的,但是要深入的再问一句,这些优化技术又是怎么搞出来的?它的底层是什么?

最底层的还是算法,就是它之所以去做一个集群、做一个读写分离、做了一个缓存,它依靠算法,最简单例子读写分离,核心是什么?

当是 select 语句时,就去认为是读,当是其他操作,就认为是写这一个东西,就有很多算法在里面,难道仅仅靠一个 select 的一个关键词来判断吗?

肯定有些优化的东西,;再比如集群,集群完了之后,同时跑了16个或者32个后台,跑了那么多服务器,那么用什么样的算法,让各个服务器能够充分发挥它的最大效率,而且保证没问题,;再比如有些服务器,它为了防止死机,它一般都会有一个备用服务器,发现有一个服务器宕机了,它立马就冲上去了。

这些东西肯定要用网络,它同时还有算法,比如张三有一堆好友,那么这些对好友,它的状态,是每隔五分钟要把所有的好友全部放上去,问服务器要,不过不是一起要,他是分波要的,它怎么分波?

它先每次发十个过去,发十个过去过后,若果发现这十个几次都没有它,它应该是这样的,刚开始它要的人很多,比如现在有100个好友,可能第一次把100个全部发给你,突然他妻子就回国了,回国时它肯定用一个标识来标志它状态到了第二次,发现其中有些状态是稳定的,就要把这100个里面比较稳的塞出去,下次不要了,过后,再去要一个经常变化的人,等到有一段时间还得算一下,以前没有要的东西,用一个算法再把它提出来,里面有很复杂的东西,而且要的时候不是每次都像顶级服务器中间做一个缓存,而是它自己有。比如客户端做一个缓存的时候,这个地方每隔一天时间自动去客户端,去定时的要下服务器数据,所以它里面有很多算法在里边。

(2)算法结构

为什么不同的人写出来的代码,从功能上看是一样的,但是从效率上却有天壤之别,这句话只有去跟一些大工问,即真正做过核心开发的人,就会有感受,那么感受是最深是哪个地方?

那么走服务器数据库有什么问题?走数据库本身是没问题的,但是当量大时,数据库根本就支撑不了,我的瓶颈就在程序和数据库之间,就是数据的吞吐量在这挡不住,他说可以扩带宽,其实外部这一层可以用集群来解决,那么现在最难的地方还是程序跟数据库的交互,它很难去解决,同步怎么解决?

光一个数据库这么多并发都来了,会全部都卡在数据库,跑不动,全部堵在住了,然后他说现在你可以加宽带,一家流量没问题,大流量可以解决,大并发其实也不是问题,因为大并发有很多负载均衡也能解决,现在大型网站最难的地方还是在于程序和数据库,数据库启不起来一般都用读写分离,可是一写读写分离又出现很多问题,读写分离还有同步的问题,而且问题是数据表特别大的时候还要分表,分完表了过后,数据量再大,所有的优化最终还是要落实在代码的算法上,那这时能不能设计一种方案,减少对数据库的查询,同时还能够让程序正常运行,这就是他的一个设计理念。

怎么优化这些东西,其实就是现在所谓的一些缓存产品,那个时候没有缓存产品,所以那个都是程序员自己在想办法,所以就说了一句话:认为程序是有灵魂的,是有算法的,如果不想永远是个代码工人,那么就花时间要研究算法,一定要去最终要突破这个问题,如果想在架构上、在效率优化上,肯定要去多看一些这样的东西,否则代码肯定不保证,就好像两个人一样,其中有个人什么都不懂,两个人看起来长得都是一样的,比如我们坐汽车,从外形上看都是奔驰,但是里面的发动机完全不是一个档次,别人只要一开启,能把你扔到十万八千里,但从外型看,它也是奔驰,我也是奔驰,但你没看见内核是什么,所以看程序时,对外行来说,看你的程序就看漂不漂亮,内行要看要干什么、测测性能,这是讲了一个算法结构。

 

三、几个实际编程中遇到的问题

(1)Golang 代码

比如现在有个字符串在进行 Replace ,如下:

func str main() {

var str string = go,go,hello,world!

str = string.Replace(str,go,尚硅谷,-1)

fmt.Println(str)

}

那么现在要求大家使用单链表来表示字符串内字符串节点类的定义,并依次实现它的构造函数、计算长度、串赋值、判断两串相不相等、求字串、两串的连接、求子串在串中位置等7个成员函数。这些函数本身是由 API 提供的,但是要自己去实现,当时在大学里面学的时候,也有很多的这个作业,当时主要是集中在 C 加加里,这个作业是在数据结构里面,其中一个链表,它就出了一个类似的题,大概是在第六题,这个用的是 C 加加来写的,这个东西看起来就吓人,当时给我们出了这样一个题:要用自己的数据结构来实现,是一堆;还让我们去做一个多项式,多项式要求写一个算法,计算两个多项式的乘积要用多项式来实现,这个还算是简单的,当然这个东西你要能写出来,肯定是需要好好去想一想的。

(2)一个五子棋程序

五子棋相对比较简单,也就判断输和赢,并可以完成存盘退出和继续上局的功能,如果去写一个算法,怎么判断输和赢,怎么效率更高一点。如下图是一个五子棋程序:

image.png

(3)约瑟夫问题(丢手帕问题)

约瑟夫问题是很经典的,如果这个东西用链表来完成,就特别简单,如果没有悬念表,只能用数组来解数组,解决起来就比较困难。就这速度解决约瑟夫问题,它的难度不小。他最经典问题也就是丢手帕问题,他设计一到一二到 N ,围成一圈,约定编号为K的这个人从K这个人开始报数,数到 M 的那个出列,然后下一个又从那个下一个人开始,又从一开始就数到 M 又出列,最后问哪个人出列最后留的是谁?这就是个算法,那么这个时候,可以用链表加上思想,形成一个算法,每个人的算法可能不一样,效率也会不一样。可以用一个不带头结点的循环链表来处理 Josephu 问题,先构成一个有 n 个结点的单循环链表,然后由 k 结点起从1开始计数,计到 m 时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。

(4)其他常见算法问题

如磁盘、公交车画图,邮差汉诺塔,那写完了之后就看到它,就能解决。汉诺塔为如下图:

image.png

(5)小结

把数据结构的一个需求,就记三句话:可以认为程序就是数据结构加算法,那么数据结构和算法又是什么关系?可以认为数据结构是算法的一个基础,就是说算法建立在数据结构基础之上,这个算法就会相对来说实现的更容易;

第二句话是:学完数据结构可以做什么事情?学完数据结构就可以解决这样的问题,当有一个实际需求摆在面前的时候,如果学了数据结构,相对比较容易把这个算法写出来,就是相对而言有工具了,就像有一天去盗墓,盗墓是不允许的,赤手空拳去盗墓,一进去 game over 了,有一天发现当你盗墓的时候,有很多秘籍,第一个要有秘籍,第二个有很多先进的工具,比如洛阳铲之类的,还有个罗盘,有一个曾经死去过大关皇帝的位置就能找到,

然后,洛阳铲一铲,然后,有一帮朋友帮你,就很容易把这个木盖弄起来,所以解决实际问题,如果没有工具,赤手空拳,这个事就很难做,就算数据结构只是算法的一个基础,但是离开这个数据结构,做一个算法很吃力。

相关文章
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
73 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
189 10
 算法系列之数据结构-二叉树
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
158 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
196 22
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
200 30
|
6天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
8天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
7天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
6天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
79 14