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]

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

[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]

好的加油

[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]

确实，受教了！