堆栈和队列是两个错误的范例,对此可以做什么

任何程序员都知道两种数据结构,这些数据结构被视为公理,因此没有人甚至试图分析它们是否需要,是否从中获得任何好处以及这种危害是否没有超出它们。



首先,我们将讨论队列。 队列的含义是什么? 队列是缓冲区。 什么时候需要缓冲区? 当我们没有时间按照到达事件的速度处理传入事件时。
关于上述内容,出现了一个问题:为什么? 答案是我们希望某些事情会发生,并且系统突然间将允许我们处理事件。


首先,让我们处理第一段。 系统会发生什么突然突然停止制动并开始更快地消化数据的情况? 最有可能的是,一些资源密集型过程将简单地结束并释放资源。 但是,如果这没有发生怎么办? 如何处理数据? 众所周知:要么我们只是重置它们,要么整个系统由于资源不足而挂起。


鸭子,有两个问题:


  1. 如果我们知道我们没有资源来处理数据,为什么不能立即删除数据呢? 这就是为什么不可能从一个元素开始排队?
  2. 或相反的问题。 为什么我们有幻想,却没有为系统提供必要的资源来按接收速度处理数据?

这些问题的答案实际上是显而易见的。 我们根本不知道如何设计软件和硬件系统。 因为如果我们知道如何设计它们,那么我们将知道我们有多少输入数据,它们的接收率,需要多少处理它们,因此,我们可以计算对资源的实际需求。 但是,除了部分技术系统(绝不是全部)之外,ICT开发工具和方法的当前状态不允许我们对资源需求进行客观的计算。


并且我们用各种缓冲区(尤其是以队列的形式)来弥补这些缺点。 结果,我们甚至在基坑的水平处都在建筑物的基础上安放了一颗炸弹,因为这些拐杖是各种可鄙且难以把握的问题的来源,这些问题涉及可靠性,安全性以及工作质量。


但是,让我们继续,在我们前面是我最“喜欢的”结构-堆栈!


叠放


可以肯定的是,正如Hoar曾经对Null所说的那样,这是一个十亿美元的错误,因此对于堆栈也可以这么说。


这是ICT中使用的最成问题的结构之一,非常需要在创建硬件和软件的实践中最大程度地避免,直到完全消除。


那么堆栈问题到底是什么呢? 是的,与队列完全相同。 堆栈基本上是不可能排列的。 一旦有人准确地预测了任意程序的堆栈需要多少内存,我个人道歉并写了一篇我错了并请求宽恕的文章。


但是有件事告诉我,在可预见的将来这不太可能发生。


让我们分析为什么需要堆栈? 是的,队列完全相同。 这是一个缓冲区。 也就是说,这些是懒惰的拐杖,他们不想正确地设计软件和硬件系统。


因此,教训是:在有明显的迭代解决方案的情况下,应避免递归。 但是,这并不意味着应不惜一切代价处置递归。 有很多使用递归的好例子,我们将在随后的章节中进行演示。 实际上在非递归机器上都有递归过程的实现这一事实证明,出于实际目的,任何递归程序都可以转换为纯迭代程序。 但是,这需要使用递归堆栈进行显式工作,并且这些操作经常使程序的本质难以理解,因此可能难以理解。 结论:本质上是递归的而不是迭代的算法,需要制定为递归过程。
尼克劳斯·沃思。 算法和数据结构

我同意大师关于转换选项的观点,我不同意他使用堆栈的软方法。


我提出了一个定理:任何堆栈算法都可以转换成循环,而那些不能转换的算法则很糟糕。


应该停止通过堆栈传递参数来调用子程序的实践,并且不扩展到循环中的递归和其他广泛使用的实践也应该在那里进行。


在以下情况下,我们可以更换堆栈:


  1. 递归,以将堆栈算法扩展为一个循环的形式实现,该循环具有在循环执行期间更改的数据块。
  2. 如果需要传输参数,则将通过消息组织固件系统。 关于消息传递,我们转到本文第一部分中描述的内容。 如果您真的想要一个堆栈,那么显然您不应该在其中压入数十万和数百千字节的对象,但是通常需要在堆上为此分配内存。

同时,在顶层,程序员可以使用任何数据结构,并且编译器需要对其进行转换以排除使用堆栈。


当然,某些机会可能会丢失,但是,如果详细考虑,这不是事实。


封锁


1995年,我和同学一起制定了构建排除这两个范式的操作系统的原则。


原则如下:


  1. 软件-交互过程的网络。
  2. 进程的交互是通过交换消息来进行的。
  3. 交互过程的网络组织如下:这种网络中的主要消息的来源是设备提供的来自外部世界的事件,消息的最终使用者是在外部执行操作的设备。 即,网络始于现实世界,并终止于现实世界。
  4. 流程不能具有优先级。 优先级只能有一个流程网络。
  5. 网络从不缓冲消息。 硬件-软件复合体的组织方式应使其能够按照从外部接收消息的速度来处理消息。
  6. 硬件联合体是通过通信通道连接的计算节点网络。
  7. 每个节点都有一个“成本”,这取决于其处理能力,内存大小,负载和权重因素,并考虑到其创建和维护的成本。
  8. 每个通信信道都有一个“成本”,这取决于其带宽,拥塞和权重系数,并考虑了其创建和维护的成本。
  9. 操作系统提供进程启动以响应传入消息和消息路由。
  10. 操作系统确保了进程和消息在计算节点之间的分布,并考虑了将过程代码和消息传输到节点的成本,从而优化了网络拓扑上的函数f(cpu,mem)。
  11. 根据系统的结构,您始终可以准确计算出该过程所需的内存量。 可以根据算法分析准确计算所需的计数时间。

BIND处理器


在他的教学生涯中,他与学生一起参加了IEEE CPU仿真器竞赛。 使用类似于早期ARM的命令系统开发了哈佛架构的通用无堆栈处理器。 另外,将被遗忘的传输器概念整合到CPU中,并且该处理器配备了16个8位收发通道。


因此,处理器中没有调用/返回操作。 仅有条件/无条件过渡是可能的。 鉴于目前几乎没有人用汇编器编写程序,所有有关用机器代码生成程序的问题都应该分配给编译器。


该处理器的主要目标是通过在本地计算节点中创建处理器网络,在硬件级别上无缝地支持Blockout OS的原理,该处理器网络由已在其上分布了进程的通信通道连接。


结论


文本显示了队列和堆栈数据结构的致命缺陷。 给出了设计软件和硬件系统的原则,该原则允许将这些结构排除在应用程序实践之外。


确切地说,本文是在IT整个职业生涯中所发生的思想的汇编,可以说是将一切缩减为一个地方。

Source: https://habr.com/ru/post/zh-CN430070/


All Articles