B-Tree BST Performance Binary Search Tree 根据插入的数据不同，最好的情况树的高度为 $O(logN)$, 最坏的情况为 $O(N)$。 17.3 B-Tree Operations Avoiding Imbalance 采用的一种方法是“过度填充”叶节点。我们不需要在插入时添加新节点，而是简单地将新值堆叠到适当位置的现有叶节点中。 Moving Items Up 为了改善过度填充叶节点的问题，我们可以考虑在叶节点达到一定数量的值时“上移”一个值。 然而，这遇到了一个问题，我们的二分搜索属性不再被保留——16 在 17 的右边。这时候我们需要将过度填充节点的子节点划分： 在这个结构上的搜索操作将与 BST 完全相同，除了值在 15 到 17 之间，我们去中间的子节点，而不是左边或右边。 如果我们设置一个常数𝐿作为节点大小的限制，那么我们的搜索时间只会增加一个常数因子。 添加到节点可能会导致级联链式反应，如下图所示，我们添加了 25 和 26。 当我们的根超过限制，我们需要增加树的高度： 这种数据结构的名称为 B-Tree, 如果每个节点最多有 3 个 items, 那么我们称之为 2-3-4 trees 或者 2-4 trees(一个 node 可以有 2/3/4 个子节点)。如果每个节点最多有 2 个 items，那么称之为 2-3 trees。 17.4 B-Tree Invariants 所有叶子节点到根节点的距离都是一样的。 具有 k 项的非叶节点必须恰好有 k + 1 个子节点。 17.5 B-Tree Performance 根据每个节点最多包含 $L$ 个 items, B-Tree 的最大高度在 $log_{L+1}N$ 到 $log_2N$ 之间。...
Posts
Inheritance I: Interface and Implementation Inheritance 9.2 Hypernyms, Hyponyms, and the Implements Keyword interface 类： public interface List61B<Item> { public void addFirst(Item x); public void add Last(Item y); public Item getFirst(); public Item getLast(); public Item removeLast(); public Item get(int i); public void insert(Item x, int position); public int size(); } 实现类： public class AList<Item> implements List61B<Item>{...} 9.3 Overriding, Interface Inheritance overriding 实现类实现 interface 类的时候要加上@Override关键字。 @Override public void addFirst(Item x) { insert(x, 0); } 9....
Conditional Breakpoints, Execution Breakpoints 的设置. Conditional Breakpoints 对Intellij中的断点右键，会出现 在condition中输入条件表达式，当满足条件时，断点生效。 Execution Breakpoints Run->View Breakpoints, 选择Java Exception Breakpoints, 选择需要断点的异常类型.
lab4a 处理下面这种情况： 比如我们提交了 lab1 对 Collatz.java 的修改 commit，然后远程仓库更新了一个 commit，但仍然包含旧的 Collatz.java。 此时我们 git pull 就会冲突。 lab4b git checkout <commit-id> 进入 detached HEAD 状态，此时可以查看文件历史，但不要做任何修改。 git checkout master 回到 master 分支。 # 从某个提交或分支中恢复特定文件 git checkout branch-name -- file-name git checkout commit-hash -- file-name A Debugging Mystery 这个问题是因为 Java 中 Integer 对象的缓存机制导致的。 在 Java 中，== 运算符比较的是对象的引用（内存地址），而不是对象的值。当你使用 == 比较两个 Integer 对象时，你实际上是在比较它们是否是同一个对象实例。 Java 为了优化性能，对于范围在 -128 到 127 之间的整数，会预先缓存对应的 Integer 对象。这意味着： 当你创建值在 -128 到 127 范围内的 Integer 对象时，Java 会返回缓存中的对象 当值超出这个范围时（如 128），每次创建都会生成新的对象实例 因此，当你比较两个超出这个范围的 Integer 对象时，它们是不同的对象实例，== 运算符返回 false。...
Java and Compilation javac capers/Main.java java capers.Main story "this is a single argument" File & Directory Manipulation in Java File File f = new File("dummy.txt"); f.createNewFile(); // 创建文件 f.exists() // 检查文件是否存在 Utils.writeContents(f, "Hello World"); // 将字符串写入文件 Directory File d = new File("dummy"); d.mkdir(); // 创建目录 Serializable 如果有更复杂的 object 需要保存，可以利用 java.io.Serializable, 将 object 序列化成 byte stream 保存到文件中： import java.io.Serializable; public class Model implements Serializable { ... } 把对象序列化成 byte stream： Model m = ....
book 看浮点数实现。 浮点数汇编。 lab data lab 继续做以及笔记。 bomb lab phase6和secret bomb。
deivce interrupt 的入口在kernel/trap.c 的 devintr函数。 5.1 Code: Console input ns16550 uart driver 寄存器相关，每个占 1 个 byte: LSR: line status register, 保存 uart 硬件的状态。 RHR: receive holding register, 保存接收到的数据。 THR: transmit holding register, software 往里写，uart hardware 就会发送。 xv6 main 函数通过 kernel/console.c 中的 consoleinit 函数来初始化 uart 硬件，使能 uart 中断。 xv6 shell 通过在 init.c 中打开的 console file descriptor 从 console 中读取数据。通过 read system call 调用到 consoleread 回调函数。consoleread 函数等待 input, 并保存到 cons.buf. 如果 user 还没有输入完完整的一行，reading process 会进入 sleep....
6.1 Races 6.2 Code: Locks Xv6 有两种锁，spinlocks 和 sleep-locks. struct spinlock { uint locked; // 0 表示可以获取锁，1 表示锁被占用 char *name; // 锁的名称 struct cpu *cpu; // 持有锁的 CPU }; void acquire(struct spinlock *lk) { push_off(); // disable interrupts to avoid deadlock. if (holding(lk)) // 如果当前进程已经持有锁，则 panic，不可重入 panic("acquire"); while (__sync_lock_test_and_set(&lk->locked, 1) != 0) ; __sync_synchronize(); lk->cpu = mycpu(); } __sync_lock_test_and_set 是 C 库的一个原子操作，在 risc-v 上，它会被编译成 amoswap 原子指令。 __sync_lock_test_and_set(&lk->locked, 1) 的工作原理： 原子性地读取 lk->locked 的当前值 将 lk->locked 设置为 1（表示锁被占用） 返回 lk->locked 的原始值 如果返回 0：说明锁之前是空闲的（0），现在成功获取了锁，跳出循环 如果返回 1：说明锁之前就被占用（1），继续自旋等待 void release(struct spinlock *lk) { if (!...