前端小魔女

V1

2022/11/01阅读:24主题:蔷薇紫

计算机底层知识之内存

渔夫出海前,并不知道鱼在哪里,可是他们还是选择出发, 因为他们相信,一定会满载而归。人生很多时候,是选择了才有机会,是相信了才有可能
-- 稻盛和夫

大家好,我是柒八九

今天,我们继续计算机底层知识的探索。我们来谈谈关于小数运算的相关知识点。

如果,想了解该系列的文章,可以参考我们已经发布的文章。如下是往期文章。

文章list

  1. 计算机底层知识之CPU
  2. 计算机底层知识之二进制
  3. 计算机底层知识之处理小数

你能所学到的知识点

  1. 内存的物理机制 推荐阅读指数 ⭐️⭐️⭐️⭐️⭐️
  2. 内存的逻辑模型是楼房 推荐阅读指数 ⭐️⭐️⭐️
  3. 数组是高效使用内存的基础 推荐阅读指数 ⭐️⭐️⭐️
  4. 栈、队列以及环形缓冲区 推荐阅读指数 ⭐️⭐️⭐️
  5. 链表 推荐阅读指数 ⭐️⭐️⭐️
  6. 二叉树 推荐阅读指数 ⭐️⭐️⭐️

好了,天不早了,干点正事哇。


计算机是进行数据处理的设备,而程序表示的就是处理顺序和数据结构。由于处理对象(数据)是存储在内存磁盘上的,因此我们今天来聊聊内存和磁盘。


内存的物理机制

内存实际上是一种名为内存IC的电子元件。

内存IC中有电源地址信号数据信号控制信号等用于输入输出的大量引脚(IC的引脚),通过为其指定地址,来进行数据的读写。

下图是内存IC的引脚配置示例。

  • VCCGND电源
  • A0~A9地址信号的引脚
  • D0~D7数据信号的引脚
  • RDWR控制信号的引脚

将电源连接到VCCGND后,就可以给其他引脚传递比如01这样的信号。大部分情况下,+5V直流电压表示1,0V表示0

  • 数据信号引脚有D0~D7共8个,表示一次可以输入输出8位(=1字节)的数据。
  • 地址信号引脚有A0~A9共10个,表示可以指定0000000000~11111111111024个地址

由于地址用来表示数据的存储场所,因此我们可以得出这个内存IC可以存储1024个1字节的数据。又因为1024=1K,所以内存IC的容量就是1KB

向内存IC读写数据

写入数据

假设我们往内存IC中写入1字节的数据。

  • 可以给VCC接入+5V,给GND接入0V的电源
  • 并使用A0~A9地址信号来指定数据的存储场所
  • 然后把数据的值输入给D0~D7的数据信号
  • WR(write的缩写)信号设定为1

执行完这些操作,就可以在内存IC内部写入数据了。

读取数据

在读取数据时,只需要通过A0~A9的地址信号指定数据的存储场所,然后再RD(read的缩写)信号设成1即可。执行完这些操作,指定地址中存储的数据就会被输出到D0~D7的数据信号引脚中。

WRRD这样可以让IC运行的信号称为控制信号

内存IC内部有大量可以存储8位数据的地方,通过地址指定这些场所,之后即可进行数据的读写。


内存的逻辑模型

内存的逻辑模型是楼房

上图表示的是,内存为1KB时,有1024层的楼房,每层都有1字节的数据。并且地址的值是从上往下逐渐变大的。

不过,在实际的编程环境下,还包含着物理内存中不存在的概念,那就是数据类型。在编程语言中的数据类型表示存储的是何种类型的数据。从内存来看,就是占用的内存大小(占有的楼层数)的意思。

即使是物理上以1个字节位单位来逐一读取数据的内存,在程序中,通过指定其类型,也能实现以特定字节数为单位来进行读写

我们通过一个具体示例来进行说明。

下面是一个往abc这三个变量中写入数据123C语言程序,

// 定义变量
char a;
short b;
long c;

// 给变量赋值
a = 123;
b = 123;
c = 123;

这3个变量表示的是内存的特定区域。

通过使用变量,即便不指定物理地址,也可以在程序中对内存进行读写。

这是因为,在程序运行时候,操作系统会自动决定变量的物理地址。

在3个变量的数据类型分别是

  • char:1字节长度
  • short:2字节长度
  • long:4字节长度

因此,虽然同样是数据123,存储时其占据的内存大小是不一样的。

上面的示例图中,采用的是将数据低位存储在内存低位地址低字节序 Little Endian方式。

由此,我们可以得出一个结论:根据程序中所指定的变量的数据类型的不同,读写的物理内存大小也会随之发生变化


数组是高效使用内存的基础

数组是指多个同样数据类型的数据在内存中连续排列的形式。

作为数组元素的各个数据会通过连续的编号被区分开来,这个编号称为索引指定索引后,就可以对该索引对应地址的内存进行读写操作

如下用C语言定义char类型、short类型、long类型三个数组。

char g[100];
short h[100];
long i[100];

数组的定义中所指定的数据类型,表示一次能够读取的内存大小。

数组是使用内存的基本,因为其他的内存使用技能,每一种都需要以数组为基础


栈、队列以及环形缓冲区

栈和队列,都可以不通过指定地址和索引来对数组的元素进行读写。

栈和队列的区别在于数据出入的顺序是不同的。在对内存数据进行读写时,用的LIFO(Last Input First Out,后入先出)方式,而队列用的是FIFO(First Input First Out,先进先出)方式。

在内存中预留出栈和队列所需要的空间,并确定好写入和读出的顺序,就不用再指定地址和索引了

我们假定往栈中写入数据的函数名为Push,把栈中读出数据的函数名为Pop

使用栈

// 往栈中写入数据
Push(123);  // 写入123
Push(456);  // 写入456
Push(789);  // 写入789

// 从栈中读出数据
j = Pop();  // 读出789
k = Pop();  // 读出456
l = Pop();  // 读出123

当我们需要暂时舍弃当前的数据,随后再恢复原貌时候,优先选用栈

使用队列

假定往队列中写入数据的函数名为EnQueue,把栈中读出数据的函数名为DeQueue

// 往栈中写入数据
EnQueue(123);  // 写入123
EnQueue(456);  // 写入456
EnQueue(789);  // 写入789

// 从栈中读出数据
m = DeQueue();  // 读出123
n = DeQueue();  // 读出456
o = DeQueue();  // 读出789

当我们需要处理通讯中发送的数据时,或由同时运行的多个程序所发送过来的数据时,会用到这种队列中存储的不规则数据进行处理的方法

队列一般是以环形缓冲区Ring Buffer的方式来实现的。

假设我们要有6个元素的数组来实现一个队列。这时可以从数组的起始位置开始有序地存储数据,然后再按照存储时的顺序数据读出。在数组的末尾写入数据后,后一个数据就会被写入数据的起始位置(此时数据已经被读出所以该位置是空的)

环形缓冲区的模型
环形缓冲区的模型

链表

通过使用链表,可以更加高效地对数组数据(元素)进行追加删除处理

在数组的各个元素中,除了数据的值之外,通过为其附带上下一个元素的索引,即可实现链表。数据的值和下一个元素的索引组合在一起,就构成了数组的一个元素。

由于链表末尾的元素没有后续的数据,因此就需要用别的值(这里是-1)来填充。

在需要追加或删除数据的情况下,使用链表是很高效的。

这里,我们把之前我们针对JS链表相关算法的一些技巧直接迁移过来了。这里使用哨兵节点来对链表操作进行简化处理。

哨兵节点是为了简化处理链表边界条件而引入的附加链表节点

哨兵节点通常位于链表的头部,它的值没有任何意义。在一个有哨兵节点的链表中,从第二个节点开始才真正的保存有意义的信息

追加数据

function append(head,value{
  // 哨兵节点 
  let dumy = new ListNode(0);
  dumy.next = head;
  
  // 遍历链表,直到链表尾部
  let node = dumy;
  while(node.next!=null){
    node = node.next;
  }

  node.next = new ListNode(value);
  return dumy.next;
}

首先,创建一个哨兵节点(该节点的没有意义 -即ListNode(0)参数为啥不重要),并把该节点当做链表的头节点,把原始的链表添加到哨兵节点的后面dumy.next = head)。

然后,返回真正的头节点(哨兵节点的下一个节点)node.next

这里有一个小的注意点,就是在遍历链表的时候,并不是直接对dumy进行处理,而是用了一个零时游标节点(node)。这样做的好处就是,在append操作完成以后,还可以通过dumy节点来,直接返回链表的头节点dumy.next。 因为,dumy一直没参与遍历过程。

删除数据

为了删除一个节点,需要找到被删除节点的前一个节点,然后把该节点的next指针指向它下一个节点的下一个节点

哨兵节点,在删除指定节点

function delete(head ,value){
  let dumy = new ListNode(0);
  dumy.next = head;
  
  let node = dumy;
  while(node.next!=null){
    if(node.next.value==value){
      node.next = node.next.next;
      barek;
    }
    node = node.next;
  }
  return dumy.next;
}

通过哨兵节点(dumy)直接将链表为空被删除节点是头节点的两种特殊情况,直接囊括了。用最少的代码,处理最多的情况


二叉树

二叉树查找树是指在链表的基础上往数组中追加元素时,考虑到数据的大小关系,将其分成左右两个方向的表现形式。

二叉查找树使数据搜索更有效。


我们这里不对具体的数据结构进行详细的介绍。如果了解更多关于数据结构的和对应的算法的东西,可以移步到我们之前的文章中。 总有一款适合你。

后记

分享是一种态度

参考资料:《程序是怎样跑起来的》

全文完,既然看到这里了,如果觉得不错,随手点个赞和“在看”吧。

分类:

前端

标签:

JavaScript

作者介绍

前端小魔女
V1

微信公众号:前端柒八九