Dawn-K's Blog

「垃圾回收的算法和实现」第四章-GC 复制算法

GC 复制算法思路之前提到的标记清扫和引用计数法都不会更改对象的位置，并且利用了全部的内存。在此我们就打破这个限制。首先我们把内存分成两半，一半叫 from , 一半叫 to 。每次程序运行时只占用 from，当需要垃圾回收的时候，就先找到所有的活动对象，然后复制到 to 中，并且从 to 的低地址陆续摆放。然后交换 from 和 to 的名字。这个算法的关键是不仅要把对象搬...

Posted by Dawn-K's Blog on January 22, 2022

「垃圾回收的算法和实现」第三章-引用计数法

引用计数法思路引用计数法的思路也是比较简单。既然当空间不足时再从头找垃圾，不如就不使用标记，在每次指针的赋值过程中就把引用的数量给维护了。一个对象，当有一个新的指针指向它的时候，计数器加 1，如果一个指针不再指向它，计数器减 1. 当计数器减为 0 的瞬间，执行回收。回收的时候还要考虑到它所有发射出的指针指向的儿子对象都要计数减 1。这种思路看起来似乎正确，但是有一个致命的问题：...

Posted by Dawn-K's Blog on January 21, 2022

「垃圾回收的算法和实现」第二章-标记清扫法

标记-清除算法标记清除算法是一个经典的算法，思路也比较直接和简单。需要一个全局变量 free_list , 是一个链表，用来存储空闲的块申请空间在空闲列表中遍历，如果找到”合适”的，就把这一节摘下来，然后裁剪成 size 的大小，返回，然后将剩下的边角料给放回到列表里。如果没有合适的，就执行垃圾回收，然后再次尝试在空闲列表中寻找。找到了就返回，没找到就报错。关于“合适...

Posted by Dawn-K's Blog on January 20, 2022

「垃圾回收的算法和实现」第一章-背景介绍

背景最近看了一本书，《垃圾回收的算法和实现》，感觉挺有趣的，图示很多。很久没写笔记了，这本书看完了很多细节容易忘，而且有一些内容在书中描述的有些不太好理解，做笔记做备忘。垃圾回收 (gc) 是一种很久历史的功能。早在 lisp 上就已经实现了。但是关于它的研究却未停止过。部分语言比如 Java/Python/Go 已经内置了 gc，使用者无需关心内存管理，放心 new 就是了。但是在...

Posted by Dawn-K's Blog on January 17, 2022

「编程之外」给 PDF 增加目录

给 PDF 增加目录背景很多 pdf 电子书没有目录，在翻阅时非常不便。事实上在 windows 平台有个很好的解决方案，就是使用 FreePic2Pdf 工具进行对目录的修改。步骤提取目录首先下载 FreePic2Pdf . 打开后在程序的右下角选择”更改 PDF”. 然后在弹出框中选择”从 pdf 中取文件”, 设置好 pdf 路径，文件夹输出路径用默认即可。然后点...

Posted by Dawn-K's Blog on July 27, 2021

「编译原理」编译原理基础知识

编译原理基础知识哥德尔不完备定理对于一个形式系统，它能从基本的公理推导出其他结论。如果它能推出所有的结论，那么它就是完全性的。如果它推出的所有结论都是对的，那么它就是可靠的。可靠性的证明容易保证，只要保证公理是对的，推导过程是对的，那么就是可靠的。但是问题就在于完全性的证明。哥德尔证明出，如果一个系统能表达初等数学，那么存在一个公式，形式系统既不能推出它，也不能推出...

Posted by Dawn-K's Blog on March 13, 2021

「AI」人工智能基础知识

人工智能 P 和 NP P 类问题是指能够在多项式时间内解决的问题 NP 类问题是指能够在多项式时间内验证一个解对不对的问题，所有 P 问题都是 NP 问题。 NP-hard: 比 NP 还要难，任意一个 NP 问题都能在多项式时间规约为 NP-hard 问题 NPC: NP 完全问题，即是 NP 问题，又是 NP-hard 问题 SAT 问题（第一个 NPC 问题）. 该问题的基本意...

Posted by Dawn-K's Blog on March 11, 2021

「计算机网络」计算机网络基础知识

计算机网络 [toc] OSI 模型 OSI 具有七层，但是其太过理想化，并没有实际采用。物理层（界定连接器和网线的规格）数据链路层（相邻设备之间传送和识别数据帧）网络应用层（地址管理和路由选择）传输层（端到端的数据连接）会话层（负责建立和断开通信连接）表示层（数据格式的转换）应用层（针对特定应用） TCP/IP TCP/IP 是个协议...

Posted by Dawn-K's Blog on March 10, 2021

「CodeNote」红黑树

红黑树概述红黑树是在 AVL 的基础上发展来的. 红黑树也是一种平衡二叉树, 但是其没有 AVL这么严格. 从而避免了AVL的大量的翻转. 红黑树包含以下特性: 节点只有红黑两色根节点是黑色叶子节点(准确的说是空节点,是不真实存在的节点)是黑色红色节点的儿子是黑色对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点.(定义为黑高...

Posted by Dawn-K's Blog on March 9, 2021

「CodeNote」 AVL

概述 AVL是一种平衡二叉树. 其本身是一种BST(二叉搜索树), 但是它可以通过旋转自身来平衡左右子树, 让左右子树的高度差不超过1. 难点在于旋转和维护高度. 代码以下是PAT甲级1123的AC代码, 题中保证了插入树的所有元素均不相同. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2...

Posted by Dawn-K's Blog on March 8, 2021

Dawn-K's Blog

「垃圾回收的算法和实现」第四章-GC 复制算法

「垃圾回收的算法和实现」第三章-引用计数法

「垃圾回收的算法和实现」第二章-标记清扫法

「垃圾回收的算法和实现」第一章-背景介绍

「编程之外」给 PDF 增加目录

「编译原理」编译原理基础知识

「AI」人工智能基础知识

「计算机网络」计算机网络基础知识

「CodeNote」红黑树

「CodeNote」 AVL

FEATURED TAGS

ABOUT ME

FRIENDS

「垃圾回收的算法和实现」 第四章-GC 复制算法

「垃圾回收的算法和实现」 第三章-引用计数法

「垃圾回收的算法和实现」 第二章-标记清扫法

「垃圾回收的算法和实现」 第一章-背景介绍

「编程之外」 给 PDF 增加目录

「编译原理」 编译原理基础知识

「AI」 人工智能基础知识

「计算机网络」 计算机网络基础知识

「CodeNote」 红黑树

「CodeNote」 AVL

FEATURED TAGS

ABOUT ME

FRIENDS

「垃圾回收的算法和实现」第四章-GC 复制算法

「垃圾回收的算法和实现」第三章-引用计数法

「垃圾回收的算法和实现」第二章-标记清扫法

「垃圾回收的算法和实现」第一章-背景介绍

「编程之外」给 PDF 增加目录

「编译原理」编译原理基础知识

「AI」人工智能基础知识

「计算机网络」计算机网络基础知识

「CodeNote」红黑树