- 博客(62)
- 收藏
- 关注
RSS订阅原创 跳跃列表（Skip List）详解
跳跃列表是一种概率性的数据结构，旨在提高链表的搜索、插入和删除效率。它通过在普通链表的基础上增加多个层次，以实现更快的访问速度。跳跃列表的设计灵感来源于跳跃图（Skip Graph）和多层索引的概念，适合需要频繁进行动态数据操作的场景。跳跃列表是一种高效的概率性数据结构，适合动态数据的处理。通过引入随机性，跳跃列表在搜索、插入和删除操作中都能实现平均 O(log n) 的时间复杂度，成为解决许多实际问题的优秀选择。如果你对跳跃列表有更多的疑问或想要进一步探讨的内容，欢迎在评论区留言！
2024-09-25 20:34:41
1002
原创 van Emde Boas 树的演进与实现
van Emde Boas 树是一种能在大范围内（例如，IPv4地址的范围）以近乎对数的复杂度进行查找、插入、删除操作的数据结构。与传统的平衡二叉树相比，van Emde Boas 树的时间复杂度为 (O(\log log u))，这使其在处理大型集合时效率极高。它通过递归划分数据集和分层存储的方式，大幅减少了查找、插入、删除操作的时间成本。van Emde Boas 树的演进展示了如何从一个简单的位向量，通过递归、分层和空间优化，逐步提升数据结构的效率。
2024-09-09 17:56:56
913
原创 快速傅里叶变换（FFT）及其在多项式乘法中的应用 —— 深入分析与 Python 实现
单位根是指在复平面上均匀分布在单位圆上的点，满足 x^n = 1 的复数点。它们可以表示为：这些点的对称性和周期性使得我们可以通过分治法高效计算傅里叶变换。通过本文，我们深入探讨了如何利用快速傅里叶变换FFT进行高效的多项式乘法。我们从最基本的多项式操作出发，介绍了如何通过单位根和分治法将乘法复杂度从 O(n^2) 降低到 O(n log n)。我们还通过 Python 代码展示了 FFT 和 IFFT 的具体实现，并进行了多项式乘法的示例。FFT 在多项式乘法中的应用只是其众多用途之一。
2024-09-06 16:54:11
2058
原创 分治算法与凸包问题
凸包问题是计算几何中的经典问题。给定二维平面上的点集，凸包是一个最小的凸多边形，它包含了点集中所有的点。你可以把凸包想象成一根松紧带将所有点紧紧包裹住的样子，凸包的边缘仅沿着最外面的点延伸。分治算法是解决复杂问题的强大策略，它的思想是将问题分解为多个子问题，分别解决这些子问题后再合并得到最终解。凸包问题可以通过分治算法高效地解决，时间复杂度可以达到 (O(n \log n))。分解（Divide）：将点集按 x 坐标排序，并递归地将点集分为左右两部分。求解（Conquer）
2024-09-05 18:24:54
1259
原创 深入理解区间调度问题：从贪心算法到动态规划的加权优化
贪心算法首先选择了结束时间最早的区间 (<s(i_1), f(i_1)>)，此时必有 (f(i_1) \leq f(j_1))。将这些不重叠区间与 (<s(i_1), f(i_1)>) 结合，即得到了原问题的最优解。在经典的区间调度问题中，贪心算法通过每次选择结束时间最早的请求，可以高效地找到不重叠请求的最大集合。贪心算法的时间复杂度为 (O(n \log n))，其中 (n) 是请求的数量，排序操作占据了主要的时间复杂度。的请求，这样可以为后续的请求留出更多的时间空间，保证能够选择尽可能多的不重叠请求。
2024-09-04 19:09:05
2377
1
原创 数据库缓存管理
缓存管理器是数据库管理系统（DBMS）中负责管理内存中page并处理文件和索引管理器的page请求的组件。由于内存空间有限，我们不能将所有page存储在缓存池中。因此，缓存管理器需要制定替换策略，当空间填满时选择哪些page进行替换。缓存管理器与磁盘空间管理器进行通信，执行所需的磁盘操作。缓存管理器提供了一种间接映射，将磁盘page ID映射到内存地址，确保每个请求的page在内存中被固定以进行操作，并在使用完成后解除固定。
2024-07-05 10:36:28
1135
原创 数据库索引
B+树是一种动态平衡的索引结构，能够高效地处理大量数据的插入、删除和查询操作。它通过内部节点的导航和叶节点的数据存储，确保了查询的高效性和数据的有序性。通过对B+树的深入理解，可以更好地设计和优化数据库索引结构，提高数据库系统的整体性能。
2024-07-03 12:49:56
760
原创 数据库管理系统中的磁盘、文件、页和记录管理
数据库管理系统中的数据存储和管理是一个复杂的过程。通过合理选择文件组织方式，可以优化数据库的性能。在设计和实现DBMS时，需要综合考虑数据的访问模式和操作成本，以选择最合适的文件类型和实现方式。堆文件适用于插入操作频繁且不需要快速搜索的场景，而排序文件则适用于需要高效搜索操作的场景。这篇笔记详细介绍了DBMS中关于磁盘、文件、页和记录的管理，提供了理论基础和实际指导，为数据库的高效管理提供了有力支持。
2024-07-03 12:23:53
1327
原创 SQL总结
SQL (Structured Query Language) 是一种标准的数据库查询语言，用于管理和操作关系数据库。SQL 包含两部分：数据定义语言 (DDL) 和数据操作语言 (DML)。DDL 用于定义和修改数据库结构，包括创建、修改和删除数据库对象。创建表CREATE TABLE 表名 (列名 数据类型 [约束条件],...[PRIMARY KEY (主键列名)],[FOREIGN KEY (外键列名) REFERENCES 参考表(参考列名)]age FLOAT,修改表。
2024-06-24 14:43:48
1440
原创 使用Java实现哈夫曼编码
哈夫曼编码是一种经典的无损数据压缩算法，它通过赋予出现频率较高的字符较短的编码，出现频率较低的字符较长的编码，从而实现压缩效果。这篇博客将详细讲解如何使用Java实现哈夫曼编码，包括哈夫曼编码的原理、具体实现步骤以及完整的代码示例。首先定义一个内部类Node，用于表示哈夫曼树的节点。每个节点包含字符、频率、左子节点和右子节点。实现接口用于在优先队列中排序。// 字符// 频率// 左右子节点// 判断是否为叶子节点= null));// 根据频率比较节点，用于优先队列。
2024-06-21 22:09:33
861
原创 基数排序详解：LSD和MSD的实现与比较
基数排序是一种基于“位”的排序算法，通过将数据按位进行多次排序来实现最终的排序效果。它特别适用于整数和字符串的排序。基数排序有两种主要的变种：LSD和MSD，它们的主要区别在于排序的方向。通过将计数排序抽象出来，我们简化了LSD和MSD基数排序的实现。这样不仅提高了代码的复用性和可读性，也使得修改和扩展算法变得更加容易。无论是从最低有效位开始排序的LSD基数排序，还是从最高有效位开始排序的MSD基数排序，都可以利用同一个计数排序模块来实现其核心功能。
2024-06-20 20:52:31
928
原创 基础排序算法详解与对比分析
排序算法是计算机科学中最基础和重要的算法之一。本文将详细介绍几种经典的排序算法，包括选择排序、插入排序、希尔排序、堆排序和归并排序，并进行代码实现和对比分析。
2024-06-15 10:56:28
796
原创 在有向无环图（DAG）中实现拓扑排序与最短路径和最长路径算法
首先，我们定义一个简单的图结构，包括节点和边。i ++) {} } }i ++) {} } }i++) {@Override本文介绍了在有向无环图（DAG）中实现拓扑排序、单源最短路径和单源最长路径算法的详细步骤和Java代码。通过比较不同的拓扑排序方法和最长路径算法，我们可以根据实际需求选择最适合的实现方案。希望这些内容能帮助读者更好地理解和应用DAG相关的算法。
2024-06-14 00:45:00
733
原创 最短路径与最小生成树：Dijkstra、Prim与Kruskal算法详解
为了完整性，我们需要定义一个Graph类，以支持上述算法的实现。i ++) {} } }i ++) {} } }i++) {@Override通过对Dijkstra、Prim和Kruskal算法的介绍和代码实现，我们可以更好地理解这三种经典算法在图论中的应用。每种算法都有其适用场景和优劣性，选择合适的算法可以提高解决问题的效率。希望本文能为你在学习和应用图算法时提供帮助。
2024-06-13 08:39:01
1713
原创 Xv6文件系统详解
Xv6文件系统虽然简单，但其设计和实现涵盖了许多现代文件系统的核心概念。通过理解Xv6的磁盘布局、文件读取和写入操作以及崩溃恢复机制，我们可以更好地理解操作系统和文件系统的基本原理。希望这篇文章能帮助您深入了解Xv6文件系统，并为进一步研究和学习提供一个坚实的基础。
2024-06-12 10:44:46
1622
原创 高效Trie实现：子节点的存储数据结构：数据索引字符映射，哈希表以及二叉搜索树
Trie（前缀树）是一种高效的字符串数据结构，广泛用于实现字典和搜索引擎中的自动补全功能。本文将详细探讨三种不同的Trie实现方法：基于数据索引字符映射的Trie、基于哈希表的Trie和基于二叉搜索树（BST）的Trie，并比较它们的优缺点和性能。
2024-06-11 00:00:00
1174
原创 深入了解FAT文件系统
FAT文件系统由于其简单性和兼容性，仍然在许多领域广泛应用。了解其内部结构和工作原理有助于更好地管理和维护存储设备，同时在需要时也可以进行数据恢复和故障排除。希望这篇博客能够帮助你更好地理解FAT文件系统的运作机制。
2024-06-10 00:00:00
2696
原创 深入了解Git：从数据模型到集成IDEA
通过理解Git的数据模型、暂存区、命令行接口，并将其集成到IntelliJ IDEA中，可以极大地提升开发效率。希望本文能够帮助你更好地使用和管理Git仓库，充分利用IntelliJ IDEA的强大功能进行版本控制。
2024-06-09 00:00:00
976
原创 优先队列的实现：基于最小堆的 Java 实现
优先队列是一种抽象数据类型，其中每个元素都有一个与之相关的优先级。在删除操作中，总是删除具有最高优先级的元素（对于最小堆来说是最小值）。优先队列的典型应用包括任务调度、图算法（如 Dijkstra 算法）等。
2024-06-08 00:00:00
1215
原创 前后端不分离与前后端分离的Java Web开发对比介绍
无论是前后端不分离还是前后端分离，最终目标都是提供高效、可靠的Web服务。前后端分离架构使得开发更灵活，前后端团队可以独立工作，提升开发效率和代码维护性。通过示例代码和详细解释，希望能帮助你更好地理解这两种架构模式及其实现方式。如果你有更多的问题或需要更详细的讲解，欢迎留言讨论！
2024-06-07 00:00:00
4298
原创 什么是Web应用--以JavaWeb为例
Web应用是通过Web服务器运行并提供服务的应用程序。Web服务器（如Tomcat）负责接收、解析和处理HTTP请求，并生成响应。Spring Boot等现代开发框架简化了开发和部署流程，但其工作原理与传统的Servlet技术一致，都是为了实现接收请求、处理请求和生成响应的基本流程。理解这些基础知识，可以帮助我们更好地开发和维护高性能的Web应用。希望本文能帮助你更好地理解什么是Web应用，以及它是如何工作的。如果你有更多的问题或需要更详细的讲解，欢迎留言讨论！
2024-06-06 00:00:00
2082
原创 探索文件系统的世界：从基础概念到挂载机制
同时，挂载机制和链接功能进一步扩展了文件系统的灵活性和功能性。因此，磁盘抽象和文件系统的结合，为我们提供了一个强大的数据管理工具，为计算机系统的正常运行和数据管理提供了重要支持。本文将深入探讨以下几个主题：为什么将磁盘抽象为块设备，为什么有了磁盘抽象还需要文件系统，文件系统如何作为虚拟磁盘，文件系统的分类，文件系统中的挂载，以及硬链接和软链接的概念。它在物理磁盘的基础上，通过逻辑结构（如文件和目录）来组织数据，使得用户和应用程序无需直接操作底层的磁盘块和扇区，而是通过更为直观和易用的接口进行数据存取。
2024-06-05 00:00:00
1248
原创 构造一个高效的哈希表：从基本思路到最终实现
在本篇博客中，我们从最基本的思路出发，逐步完善了一个高效的哈希表的实现。我们通过引入哈希函数解决键的类型问题，使用开放地址法解决冲突，通过取模操作减少空间浪费，并最终实现了动态更改哈希表大小以优化性能。这些优化措施使得我们的哈希表在处理不同类型的键和不同规模的数据时都能保持高效运行。希望通过本文的介绍，你对构造高效的哈希表有了更深入的理解，也能在实际应用中更好地利用哈希表这一重要的数据结构。
2024-06-04 00:00:00
574
原创 介绍计算机系统中的I/O设备工作方式
I/O设备是计算机系统的重要组成部分，它们通过多种设备和机制与CPU相连，实现高效、可靠的数据传输和设备管理。设备驱动程序和固件的协同工作，使得计算机系统能够稳定、高效地运行。理解I/O设备的工作原理和连接方式，有助于更好地设计和优化计算机系统。此外，GPU的并行计算能力极大地提升了神经网络等计算密集型任务的处理效率，推动了深度学习和人工智能的发展。
2024-06-03 00:00:00
1274
原创 介绍谷歌开发工具中的 Application 面板
Application 面板是 Chrome DevTools 中的一个重要部分，用于管理和调试 Web 应用的客户端存储、服务工作线程（Service Workers）、缓存、Cookie 等。它为开发者提供了对浏览器存储和后台服务的全面控制和洞察。
2024-06-02 00:00:00
1222
原创 介绍HDD、SSD、U盘：存储技术的恢复原理与安全保存私密文件的方法
随着数字存储技术的飞速发展，硬盘驱动器（HDD）、固态驱动器（SSD）和USB闪存驱动器（U盘）已经成为我们日常生活中不可或缺的部分。尽管这些设备在存储数据方面表现出色，但数据丢失问题仍然时有发生。在这篇博客中，我们将探讨HDD、SSD和U盘的工作原理、特点、删除过程及其数据恢复原理，并介绍如何安全地保存私密文件。
2024-06-01 00:00:00
3255
原创 HTML、DOM 和 BOM：深入解析网页加载和渲染过程
HTML（HyperText Markup Language）是用于描述网页结构的标记语言。它通过标签（如<div><p><a>等）定义网页的内容和布局，是网页的基础。DOM（Document Object Model）是 HTML 文档的编程接口。它将文档表示为树结构（或节点树），每个节点代表文档的一部分（例如元素、属性、文本）。通过 DOM，开发者可以使用 JavaScript 动态地访问和修改文档的内容、结构和样式。
2024-05-31 00:35:54
2683
原创 基于Chrome DevTools手册，介绍DevTools的使用方法
通过这些详细的步骤和示例，你可以更好地理解和使用谷歌开发者工具（DevTools）来调试、分析和优化网页。在 Console 中输入并执行上述代码，将输出 “Hello, Console!
2024-05-30 00:17:52
1738
原创 可执行文件以及其加载过程
可执行文件是程序经过编译和链接后生成的文件，其中包含了机器指令、数据和必要的元信息，使得操作系统能够加载并执行该程序。Windows：使用PE（Portable Executable）格式，文件扩展名通常为.exe或.dll。macOS：使用Mach-O（Mach Object）格式，文件扩展名通常为.app或.dylib。Linux：使用ELF（Executable and Linkable Format）格式，文件扩展名通常为没有特定的要求，但共享库使用.so。
2024-05-29 00:21:00
1536
原创 spanner，mit6.824论文解读
但T2在T1提交（实时）之后开始，因此外部一致性要求T2看到x=2。提交后，所有读取都应该看到我们的更新。如何确保如果读/写事务T1在只读事务T2开始之前结束，那么TS1 < TS2。T2选择TT.now().latest，这在当前时间之后，即在10之后。情景是T1提交，然后T2开始，T2必须看到T1的写入。我们希望T3看到T2的所有写入，或者一个也不看。一个读/只事务的读取看到的是事务时间戳时的版本。假设我们有两次银行转账，和一个读取两者的事务。没有锁，没有两阶段提交，没有事务管理器。
2024-05-27 00:09:42
614
原创 Distributed Transactions Mit 6.824
当您执行一些并发事务并产生结果时，“结果”既包括输出也包括数据库中的变化。存在一种串行执行事务的顺序，这种顺序产生的结果与实际执行的结果相同。（串行意味着一次一个——没有并行执行。（这个定义应该让你想起线性一致性。您可以通过寻找产生相同结果的顺序来测试执行结果是否是可串行化的。T1;T2T2;T1T1;T2;两者的结果不同；任何一种都可以接受。没有其他结果是可以接受的。实现可能已经并行执行了T1和T2，但它必须仍然产生如同按照串行顺序执行一样的结果。
2024-05-26 00:02:31
950
原创 红黑树基于Java代码的剖析
红黑树通过维护额外的颜色属性和引入旋转操作，确保了树的高度始终保持在 (O(\log n)) 的级别，从而保证了高效的插入、删除和查找操作。通过上述代码剖析，可以清晰地看到红黑树是如何通过颜色调整和旋转来保持平衡的。
2024-05-25 00:16:25
590
原创 递归，进程fork()，以及线程clone()之间的比较
递归、进程fork()和线程clone()递归适用于自然递归问题，代码简洁，但受限于栈空间。进程fork()提供高隔离性，适用于并行处理独立任务，但资源开销大。线程clone()提供高效共享和并发处理，适用于需要高效数据共享和高并发的场景，但同步复杂。理解这三种方法的特点和适用场景，能够帮助开发者在实际项目中做出最优选择，从而提高代码性能和可靠性。希望这篇文章能帮助您更好地理解递归、进程和线程之间的区别和联系。如有任何问题或建议，欢迎在评论区讨论交流。
2024-05-24 00:00:00
1285
原创 现代操作系统之内存虚拟化的处理(结合具体代码示例)
虚拟化内存是一种内存管理技术，通过将物理内存抽象成虚拟地址空间，使得每个进程拥有独立的地址空间。这种方法不仅提升了内存利用率，还提高了系统的安全性和稳定性。虚拟化内存管理通过分页和交换机制，实现了内存资源的高效利用和灵活管理。通过使用 TLB 和优化的页表结构，系统能够快速进行地址转换。同时，操作系统采用多种交换策略，在内存紧张时有效释放资源，确保系统性能和稳定性。了解这些机制和策略，对于深入理解操作系统的内存管理原理，以及优化程序性能，都具有重要意义。
2024-05-23 00:03:04
1020
原创 基于链表实现的Map与二叉搜索树的Map对比
Set;总体而言，ULLMap实现简单，适用于小规模数据集，操作效率在键值对数量较少时表现尚可。然而，随着数据规模增大，其操作性能会显著下降。而BSTMap尽管实现复杂，但在大规模数据集下操作效率更高，尤其在平衡树情况下，其查找、插入和删除操作的性能明显优于ULLMap。因此，在需要处理较大数据集或对操作效率要求较高的情况下，BSTMap是更合适的选择。
2024-05-22 00:05:28
1356
原创 结合libc手册描述libc与Linux的爱恨情仇
libc是标准C库，包含了一系列标准函数，这些函数可以被所有C程序以及其他语言的程序使用。提供基础函数：如字符串处理、内存管理、输入输出操作等。封装系统调用：为程序提供一致的接口，使得开发者不必直接处理复杂的系统调用。libc作为Linux系统的标准C库，在程序开发中扮演着基础且关键的角色。它不仅为C语言提供了标准化的函数库和系统调用封装，还通过其高度优化的实现和广泛的功能支持，为高级编程语言提供了可靠的基础。
2024-05-21 00:00:44
1262
原创 二分查找介绍
二分查找是一种在排序数组中查找目标值位置的搜索算法。它通过反复将搜索区间一分为二来实现，直到找到目标值或搜索区间为空。二分查找利用数组已排序的特性，将时间复杂度降低到 O(log N)。
2024-05-20 00:20:05
562
原创 CS61B:并查集
并查集（Union-Find）是一种数据结构，用于处理不相交集合（Disjoint Sets）的合并和查询操作。它非常适合解决动态连通性问题，例如在图论中判断两个节点是否属于同一个连通分量。并查集的主要操作有两个：查找（Find）和合并（Union）。并查集通常使用一个数组来实现，数组中的每个元素表示一个节点，值表示该节点的父节点。如果某个元素是根节点，则其值为负数，表示集合的大小（按大小合并）或秩（按秩合并）。并查集以其高效的操作和易于实现的特性，成为解决连通性问题的常用工具。
2024-05-19 00:00:25
482
原创 Frangipani: A Scalable Distributed File System(解读)
在一段时间内，关于新创建文件的信息只存在于该工作站的缓存（RAM）中。第5节说，当Frangipani工作站释放读锁时，必须使缓存数据失效，并在释放写锁时将修改后的缓存数据写回Petal。如果一个工作站在系统调用完成后，但在发送相应的日志条目到Petal之前崩溃会发生什么？如果一个工作站在系统调用完成后，但在发送相应的日志条目到Petal之前崩溃会发生什么？如果： WS1持有一个锁，WS2认为WS1已经死亡，进行恢复，释放WS1的锁，如果WS1实际上是活着的，它随后能够尝试写入被锁定的数据吗？
2024-05-17 00:23:06
633
原创 Chain Replication for Supporting High Throughput and Availability，Chain Replication笔记
由于头部和尾部的负载可能比中间节点的负载更高，可能出现性能受到头/尾限制的情况，但中间节点却有大量空闲CPU的情况。更好的方法是提前传输状态的快照，然后冻结系统的时间足够长，以发送最后几个更新到新尾部，然后重新配置并解冻，可能使用ZooKeeper的模糊快照概念。现在，假设三个链上的活动大致相等，那么三个服务器的负载也将大致相等。通过这样的布置，请求处理工作可能更加均衡，因为每个服务器参与了多个分片组，而且分片的大小相对较小。对于主/备份系统，服务器在一些组中是主服务器，在其他组中是备份服务器。
2024-05-16 00:01:33
727
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人