Elian's blog page

1. 什么是单例模式？单例模式（Singleton Pattern）是一种创建型设计模式，它确保一个类只有一个实例，并提供一个全局访问点来访问该实例。 2. 为什么需要单例模式？在多线程环境下，我们需要多个线程使用同一份资源。 2.1 为什么不使用全局变量？在一些较为简单的环境中，直接使用一些全局变量供所有线程使用是很好的。 但是，如果这个对象是资源密集型的，使用全局变量会导致资源的浪费。而且，简单的全局变量没有提供访问控制（封装），线程可以任意地访问和修改。 而单例模式就可以实现按需创建实例，避免了资源的浪费。而且提供了类封装，确保不会有意外的修改。 3. 单例模式的实现（go）单例模式尤其要注意线程安全。 sync.Once 确保了实例只被创建一次，避免了多线程环境下的竞态条件。 以下是一个懒加载的版本。 中间件代码： 1234567891011121314151617var once sync.Oncetype singleton struct {}var singleInstance *singletonfunc GetInstance()...

关于二叉树的遍历，有递归法和迭代法两种。递归法简单易懂，但是迭代法较为复杂，需要使用栈来模拟递归的过程。 这里以“将二叉树按某种顺序遍历输出”为例，介绍迭代法的实现。 关键在于理解某个节点输出的时机。 1. 前序遍历 先输出，再将左子节点入栈。没有左子节点了，才考虑右子节点的入栈。 1234567891011121314vector<int> preorderTraversal(TreeNode* root) { vector<int> ans; stack<TreeNode*> stk; while(!stk.empty() || root!=nullptr){ while(root!=nullptr){ ans.push_back(root->val); stk.emplace(root); root=root->left; ...

埃氏筛是一种简单的筛法，用于求小于等于n的所有质数。 流程1234567Prime(n): mark i from 2 to n as prime (initial) for i from 2 to n: if i is marked as prime: for j from i^2 to n with step i: mark j as not prime return all marked primes 解释： 为什么是从$i^2$开始标记非质数？ 因为如果一个数不是质数，那么它一定有一个小于等于$\sqrt{n}$的质因子。 所以，我们只需要从$i^2$开始标记，因为小于$i^2$的数，一定已经被小于$i$的数标记过了。

状压dp使用二进制数来表示状态，将当前已选元素的集合表示为一个二进制数。适用于需要枚举每一种排列进行判断、且最大的$n$有$10<n<20$的题目。状压dp能使得时间复杂度从暴力搜索的$O(n!)$降到$O(n*2^n)$(相邻无关)或者$O(n^2 * 2^n)$(相邻相关)。 若当前表示已选元素的集合的二进制掩码为mask，则； mask &(1<<i) : 表示第i个元素是否被选择 mask|(1<<i) : 表示将第i个元素加入集合 popcount(mask) : 表示集合中元素的个数 1. 相邻无关当前位置的选择不依赖于前一个位置的选择，只依赖于当前已选元素的集合。 $dp[mask]$表示状态为mask的情况(即已经选择的集合的二进制掩码为mask)下的最优解。 1.1 例题假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ： perm[i] 能够被 i 整除 i 能够被 perm[i] 整除 1 <=...

2. 第二部分 shell 脚本编程基础2.11 构建基础脚本2.11.2 创建 shell 脚本文件 其中输入命令。 在创建 shell 脚本文件时,必须在文件的第一行指定要使用的 shell,格式如下: #!/bin/bash 在普通的 shell 脚本中,#用作注释行。shell 并不会处理 shell 脚本中的注释行。然而,shell 脚本文件的第一行是个例外,#后面的惊叹号会告诉 shell 用哪个 shell 来运行脚本。(是的,可以使用 bash shell,然后使用另一个 shell 来运行你的脚本。) 通过 chmod 命令(参见第 7 章)赋予文件属主执行文件的权限后，就可以直接./script.sh来运行脚本了。 2.11.3 显示消息 如果在 echo 命令后面加上字符串,那么 echo 命令就会显示出这个字符串 echo输出默认句末带一个换行符\n,可以使用-n选项取消换行符 2.11.4 使用变量2.11.4.1 环境变量 反斜线允许 shell...

本周学习了Linux Command Line and Shell Scripting Bible这本书的第一部分到第二部分。这里对一些我自己不熟悉的、我自己觉得比较重要的内容进行记录摘要。 1. 第一部分 linux命令行1.3 bash shell基础命令1.3.5 列出文件和目录1.3.5.3 过滤输出列表 模式匹配: 问号(?)代表任意单个字符; 星号(*)代表零个或多个字符。 方括号代表单个字符位置并给出了该位置上的多个可能的选择。你可以将可能的字符逐一列出,也可以指定字符范围,比如字母范围[a–i]。 还可以使用惊叹号(!)将不需要的内容排除在外。 1.3.6 处理文件1.3.6.2 复制文件 cp 命令可以完成文件和目录从文件系统的一个位置复制到另一个位置的操作。 cp 命令最基本的用法需要两个参数,即源对象和目标对象:cp source destination。 当参数 source 和 destination 都是文件名时,cp 命令会将源文件复制成一个新的目标文件,并以 destination...

本周主要跟着代码随想录学习了LRU, LFU, 以及ARC三种缓存替换算法的原理和C++实现。 1. LRULRU是Least Recently Used的缩写，即淘汰最近最少使用的元素。 缓存的实现使用了一个哈希表和一个双向链表。哈希表用于快速查找缓存中的元素，双向链表用于维护缓存中的元素顺序。 每当涉及一个元素的key时，将该元素移动到双向链表的头部。当缓存满时，将双向链表的尾部元素删除。同时将该元素从哈希表中删除。 1.1 改进以上的LRU存在着缓存污染、锁的粒度过大的问题。 缓存污染：当新加进来的一次性的数据很多，导致缓存满时，传统的LRU会直接删除尾部元素。但是，尾部元素可能是热门数据。锁的粒度大：一把大锁锁全局。多线程高并发的访问下，同步等待将是一笔极大的时间开销。 故考虑以下改进： 1.1.1...

1. 总结二分查找的原理非常简单，但是一些细节例如是 l<r还是 l<=r、更新 r时是 r=mid还是 r=mid-1（l同理）等地方却有些让人头疼，实际写来如果不注意就可能会造成死循环。 于是总结一种模板： 定义域为[lo, hi)的单增的f(x), 找出最小的ans, 使得f(ans)>0成立。 单减同理，甚至可以进行预处理先转化为单增的情况。 伪代码如下： 12345678910111213141516algorithm binary-search(lo,hi) while the search area has elments do: mid <- lo + (hi-lo)/2; if f(mid) satisfied: // the answer may occur here ans := mid; hi <- mid; // the search area could have no elments when in the next loop, so return ans; ...

他向远方望去，无法看到高山背后的矮山，只看到一座座更高的山峰。————by 灵神 1. 总结单调栈就是保持栈内元素单调的栈。当新元素破坏单调性时，弹出栈顶元素，弹出的瞬间就找到栈顶元素对应的答案。 栈里存放着暂时还没有找到对应答案的元素。新元素入栈时，如果栈顶元素使得栈单调性被破环，那么栈顶元素的答案产生，栈顶元素找到答案，出栈。因此需要建立的栈的单调性与题目的答案需求往往是“反过来”。要下一个更大就要单减；要下一个更小就要单增。 12345678910algorithm generalized-monotonic-stack(A, cmp, process) stack S ← ∅ for i ← 0 to n-1 do: while S ≠ ∅ and condition(A[i], A[S.top()]) do: // 栈的单调性被破坏，while是为了让栈里满足条件的元素都可以出栈 j ← S.pop() // 栈顶出栈 recordAnswer(j, i) // 计算并记录栈顶对应的答案 ...

本周完成了剩下的实验。上一篇见2024-xv6-labs-1 1. net lab1.1 NIC第一个实验是补全e1000_transmit() 和 e1000_recv() 重点在于先要理解e1000初始化的代码，以及e1000_dev.h里给出的各寄存器的定义。 然后理清一下工作流程：transmit所做的，其实就是将发送区和发送环的尾部更新为带发送的数据对应的元数据。注意此时status应为0而不是E1000_TXD_STAT_DD，因为这只是代表将数据填入发送区，并没有真正发送。然后更新E100_TDT的值。但为了防止竞态条件，所以还要注意用e1000_lock加锁。 而receive所做的就是以帧为单位，不断地将缓冲区里的数据交给net_rx()，并更新缓冲区和E1000_RDT，直到遇见E1000_RXD_STAT_DD。这里不用加锁，但值得注意的是E1000_RDT必须在最后更新？想不通。 1.2 UDP Receive说来惭愧，这个部分我实在没有思路，是让ai写的。。。 2. lock2.1 Memory...