chapter_array_and_linkedlist/ram_and_cache/

[giscus[bot]]

chapter_array_and_linkedlist/ram_and_cache/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_array_and_linkedlist/ram_and_cache/

[SKRaua]

这是新的吗

[krahets]

是的，更新啦

[UselessWater]

这怎还加*符号呢，这种不应该是必须掌握的吗？

[krahets]

@UselessWater 这部分知识确实非常重要，但不是（做题）必需的

[5710xIa]

那么问题来了，未来的数字生命是存在哪种介质中的呢？
存硬盘会不会太慢了🤣

[superfeimao]

存在"未来的存储介质"中

[ColorfulLu]

当然要存硬盘了，存内存里面万一出事故断电了，那可就害人命了🤣😊😊

[FrierenGreatDemonLord]

世界安得双全法，既要容量、又要速度的事恐怕很不经济也很难实现。所以未来（特别是未来可能一切皆数据，对存储容量的需求更离谱）可能不一定是“硬盘”，但还是很有可能有类似的设备或设计专门用来存储不常用且对访问速度要求不高的海量数据。

[tonyljx]

Quote: 内存是有限的，且同一块内存不能被多个程序共享
内存不是可以通过映射的方式被多个进程共享吗？

[11kx]

这里说的是物理内存吧。

[krahets]

是的，共享内存主要用于当多个进程需要访问和修改同一数据集时。

这里想表达的意思是：当多个程序是独立的，它们拥有不同的数据，则每个程序会在自己的进程空间中独立管理自己的数据，而不能共享一块内存。

[wtl1996]

算法是如此奇妙

[Tmaof]

数组的存储空间是连续 指的是在 虚拟内存上，然而，在物理内存中，数组可能并不连续。虚拟内存到物理内存的映射涉及到分页（paging）技术。
因此在从物理内存的角度看，数组和链表的存储空间都不是连续的。
而缓存的数据加载机制，如“空间局部性”，针对的是物理内存，对于原文中这段话：“数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。”我持有疑问，我觉得数组和链表的存储空间在物理内存上都不是连续的，所以在访问数组和链表时，缓存的优化机制“空间局部性”都不能提高缓存命中率。

[krahets]

Hi，“数组在物理内存中可能不连续”是正确的。当操作系统使用分页技术将虚拟内存映射到物理内存时，虚拟内存中连续的页面可能不会映射到物理内存中连续的位置。但通常，操作系统会尽量保持相邻的虚拟页面映射到相邻的物理页面上。

数组元素在虚拟内存中是连续的，这通常导致它们在物理内存中也倾向于比较集中。由于数组的这种存储特性，当访问一个数组元素时，其相邻元素（在物理内存中相对集中）很可能已经被加载到缓存中，这就是“空间局部性”原理。即使物理内存中不完全连续，由于数组的顺序访问特性，它仍然能较好地利用缓存。

本书没有展开介绍“虚拟内存”和“物理内存”两者的关系（更适合在“操作系统”课程中学习）。在算法层面上，我们需要理解的是：尽管数组在物理内存中可能不是完全连续的，但由于其顺序存储和访问特性，仍然能相对更好地利用“空间局部性”优化缓存性能。相比之下，链表由于其非连续的物理存储特性，对“空间局部性”的利用率较低。

[deyu9999]

有操作系统教程吗

[zjt666666zjt]

请问一下 手机缓存也会断电后数据会丢失吗？

[krahets]

计算机（电脑、手机等）的缓存，断电后数据都会丢失

[qksuki]

太喜欢整本书的绘图了，比如这里的图 4-10，请问这是什么风格？这都是自己绘制的吗？

[jiuerya7]

markdown

[1sunzichen]

可以增加个 lru 缓存 楼主大大 用链表的那种，我可以给你复制上去 😁

[krahets]

谢谢建议！LRU cache 适合在哈希表那边讲，我先 mark 住

[resteven]

非常好的解释了为什么数组的效率会高很多，谢谢，之前一直不知道为什么C语言就快速，应该是因为C操作数组的能力很强（缓存命中率会高和内存中的memory碎片化），现在从这方面理解，Python的数组都是list，实际上是动态数组，会比C慢，当然C快应该还有很多其他的因素。

[wqc18737346950]

我是新手，我刚学的计算机组成原理，说是C系语言是编译语言，一次性把所有代码编译成机器语言后再进行指令集操作，而python是解释性语言，运行一段编译一段，所以相对慢，就像翻译文章和同声传译一样

[nfrjyrymccan]

太厉害了, 语言组织能力好强, 终于懂了大一没学明白的内存

[shiyi-0x7f]

该章节涉及计算机系统和计算机组成原理，推荐《深入理解计算机系统》。

[wtl1996]

好的加油

[ouyangyipeng]

经典csapp

[lin3187]

各位道友好：
对于4.4.2小节中，“在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高，从而导致内存的利用效率降低。”，释放内存会导致碎片化更高何解？是指在申请释放后导致存储地址更加“零散”的意思吗？

[777XjX777]

我看这篇文章提到，free函数释放内存会释放“由动态分配内存函数返回的指针对应的内存空间”，但是存链表指针的内存没释放，没法解决内存里的指针内存。如果指针的地址是随机分配的，那就会让内存碎片化，而且数组因为指针比链表少，碎片化的程度更轻（我猜的，指针地址分配规则不清楚）。https://blog.csdn.net/wangxiaokunno1/article/details/106797446

[lin3187]

对于频繁的申请会导致更加内存碎片化，我理解的是，用一个不太恰当的比喻就像有一个白色的多方格，每次申请都是在多方格上随机不重复的出现一个黑点，从而导致空间被黑点分隔开，形成多个碎片段。如果我们需要分配一块较大的连续内存空间时，因为碎片化导致现有的空闲内存块太小或太分散，无法满足这个需求，那么即使总体上空闲内存的总量足够，程序也可能因为找不到合适的连续空间而失败。
而free就是释放内存，相当于消除黑点，使空间内存块变大，emm，我是这样理解的。在C#和java等一些编程语言都由垃圾回收器自动完成的，当程序不再需要某个对象时，垃圾回收器会识别并回收该对象占用的内存。
我又查了一下对于free是否能够修复内存碎片化：
碎片化不能通过简单的回收恢复。回收内存（无论是通过手动调用free/delete还是由垃圾回收器自动完成）只是将内存块标记为可用，以便后续可以被重新分配。但是，回收操作本身并不会改变内存碎片化的状态。要减少碎片化，需要采取更复杂的策略，如内存紧缩（这通常是不切实际的，因为它会导致性能问题）、使用更高效的内存分配器、优化程序的内存使用模式（例如，减少动态内存分配的次数和大小），或者使用内存池等技术来预先管理内存。
合并空闲块（可选）：在某些情况下，如果刚刚被释放的内存块旁边有其他的空闲内存块，内存分配器可能会尝试将这些块合并成一个更大的空闲块。这种合并操作可以减少内存碎片，但并非总是发生，因为它可能涉及额外的开销。
下面是一个故事例子来比较生动解释malloc和free:
在一个繁忙的计算机世界里，有一个小镇叫做“内存镇”。这个小镇由一块块紧密相连的土地（内存块）组成，每块土地都可以用来建造房屋（存储数据）。镇上的居民（程序）需要不断地扩建和拆除房屋来满足他们的居住需求。
故事开始：
有一天，一个新来的居民“小明”想要建造一座房子。他向镇长（操作系统）申请了一块土地（调用malloc），镇长从镇上的空闲土地中划出了一块给小明。小明高兴地建起了他的小屋，并开始了他的生活。
不久之后，另一个居民“小红”也来到了镇上，并申请了另一块土地。镇长同样满足了她的需求，又划出了一块土地给小红。
随着时间的推移，越来越多的居民来到了内存镇，他们不断地申请和释放土地来建造和拆除房屋。有些居民在搬走后，他们的房屋被拆除了，但留下的空地（被free的内存块）可能并不与周围的空地相连，而是形成了许多小块的碎片。
内存碎片化的产生：
想象一下，如果每个居民都根据自己的需求随意地申请和释放土地，那么随着时间的推移，内存镇上就会遍布着大小不一的空地碎片。这些碎片可能太小，无法满足新来居民建造大房子的需求，但整体上却有很多空闲的土地没有得到有效利用。
这就是内存碎片化的一个简单例子。在编程中，频繁的malloc和free调用（特别是当它们涉及小内存块时）很容易导致内存碎片化。碎片化会降低内存的利用率，因为程序可能无法找到足够大的连续内存块来满足其需求，即使总体上还有足够的空闲内存。

在内存镇里，每当一个居民（比如“小明”）不再需要他之前建造的房子时，他会向镇长（操作系统）申请拆除这座房子，并将土地归还给镇上的空闲土地池。这个过程在编程中就相当于调用了free函数。
free标记为可用的含义：
释放资源：当小明调用free函数并传入指向他房子所在土地的指针时，他实际上是在告诉镇长：“我不再需要这块土地了，请将它标记为可用，以便其他人可以使用。”
更新记录：镇长（操作系统）会记录下这一变化，将这块土地从“已分配”状态更改为“可用”状态。这意味着在镇上的空闲土地记录表中，这块土地现在被标记为可以被新来的居民申请使用。
避免浪费：通过free函数将不再需要的内存块标记为可用，可以避免这些内存块被永久占用，从而浪费宝贵的资源。在内存镇中，这就像是将不再有人居住的房子拆除，让土地回归空闲状态，等待新的居民来建造新的房屋。
准备重用：一旦内存块被free标记为可用，它就可以被后续的malloc、calloc或realloc等内存分配请求所重用。这就像是在内存镇上，当新居民需要土地时，他们可以从空闲土地池中选择一块合适的土地来建造新的房屋。

我感觉这样对于内存碎片化理解更加深刻了。

[777XjX777]

确实，受教了！

[krahets]

简单来想，根据熵增定律，孤立系統（内存）会自发地走向无序（碎片化）状态。

生活中也有很多例子：口袋里的线团会自发地打结、不主动整理的桌面会逐渐变乱、电脑里的文件会越来越杂乱。

[Alexury]

day3

[luoyaocray]

day2

[Durantttttttttttttt]

day1

[Zhaopudark]

这里介绍的是 CPU缓存的数据加载机制，不能完全等价于那种程序运行时在硬盘中缓存计算中间结果的机制。

[hanzhe-one]

continue

[Zero-JC]

4.4.1 章节 “如图 4-10 所示，在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。缓存可以看作 CPU 的一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取，从而显著提升程序的执行效率，减少对较慢的内存的依赖。” 这句话中的“智能地”不太理解，是特有的概念？还是书写错误？

[GeeekerK]

这里的“智能地”是缓存的数据加载机制的体现。它会按照一套算法逻辑从内存中有选择性的智能加载

[Linyuqiz]

“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好？？？