CS61B Project 1B：从双端队列到物理建模吉他合成器

Takamatsu Tomori

公告

2026/7/31 网站上线了

Bilibili

标签

Takamatsu Tomori

公告

2026/7/31 网站上线了

Bilibili

标签

Takamatsu Tomori

公告

2026/7/31 网站上线了

Bilibili

标签

2328 字

6 分钟

CS61B Project 1B：从双端队列到物理建模吉他合成器

2025-05-28

技术笔记

Java

/

Data Structures

/

Algorithms

/

CS61B

/

Audio Synthesis

Project 1B 是 UC Berkeley CS61B（Data Structures）课程的经典项目。它分两阶段：先实现一个泛型双端队列 Deque61B，再用它构建一个 Karplus-Strong 物理建模的吉他音色合成器。本文记录实现过程、关键算法的推演，以及从数据结构的正确性到音频合成正确性的完整链路。

项目概览#

整个项目由三个独立部分构成，环环相扣：

部分	内容	核心知识点
Deque ADT	接口 `Deque61B<T>`	抽象数据类型设计、泛型
两种实现	`ArrayDeque61B` / `LinkedListDeque61B`	循环缓冲区、哨兵链表、复杂度
音频合成	`GuitarString` + `GuitarHeroLite`	Karplus-Strong 算法、环形缓冲

关键洞察：GuitarString 不需要知道 Deque 具体怎么实现，它只依赖接口语义。这就是 ADT 的价值——数组版和链表版可以无缝替换，音频合成的正确性只取决于”双端队列的操作语义是否正确”。

一、接口设计：先定义”什么”，再想”怎么做”#

Deque61B 定义了抽象数据类型的契约。它与普通队列（Queue）的关键差异在于两端都可以插入和删除：

1
public interface Deque61B<T> extends Iterable<T> {
2
    void addFirst(T x);
3
    void addLast(T x);
4
    T removeFirst();
5
    T removeLast();
6
    T get(int index);
7
    List<T> toList();
8
    boolean isEmpty();
9
    int size();
10
}

接口设计有两点值得注意：

继承 Iterable<T>：这让 Deque 支持 for-each 语法，也迫使实现者提供迭代器，为后面的音频算法打基础。
toList() 而非直接暴露内部数组：测试代码需要”所见即所得”地检查内容，但实现细节（数组还是链表）被完全隐藏。

TIP
接口只谈”能做什么”，不谈”怎么做”。这是信息隐藏（information hiding）原则——调用方只需依赖契约，实现可以自由演进。

二、ArrayDeque61B：循环缓冲区#

2.1 朴素实现的问题#

最直觉的数组队列用 front 和 back 两个索引，addLast 时 back++。但 removeFirst 后，前面的槽位就浪费了——数组越走越满，最终”假溢出”。

解决方案是循环使用数组：索引到达尾部时回绕到头部。

2.2 关键设计：`nextFirst` 与 `nextLast`#

数组版维护两个游标，指向下一次插入的位置，而不是首尾元素本身：

1
T[] array;
2
int size;
3
int nextFirst;  // 下一次 addFirst 的写入位置
4
int nextLast;   // 下一次 addLast 的写入位置
5
int memory;     // 当前容量

插入时先写入、再回绕游标：

1
public void addFirst(T x) {
2
    if (size() == 0) { initfirst(x); size++; return; }
3
    resize();                    // 必要时先扩容
4
    array[nextFirst] = x;
5
    nextFirst = Math.floorMod(nextFirst - 1, memory);
6
    size++;
7
}

回绕的精髓在于 Math.floorMod。它与 % 的区别：

-1 % 8 == -1（负值，无法作为数组索引）
Math.floorMod(-1, 8) == 7（总是返回非负结果）

当 nextFirst 已经指向 0，再往前一步就是 7，数组被”卷”成环。删除则反向操作：nextFirst = Math.floorMod(nextFirst + 1, memory)，读出元素后置空以释放引用。

2.3 读取的索引映射#

get(index) 是隐藏的难点：逻辑下标必须换算成物理数组位置。

1
public T get(int index) {
2
    if (index >= size() || index < 0) return null;
3
    int actualIndex = Math.floorMod(nextFirst + 1 + index, memory);
4
    return array[actualIndex];
5
}

逻辑下标 0 对应物理位置 (nextFirst + 1) % memory，也就是环形缓冲区真正的”头”。
因为存储区可能发生过回绕，物理连续性不代表逻辑连续性，必须用取模换算。

1
初始：        nextFirst          nextLast
2
               ↓                  ↓
3
        ┌────┬────┬────┬────┬────┬────┬────┬────┐
4
        │  0 │  1 │  2 │  3 │  4 │  5 │  6 │  7 │
5
        └────┴────┴────┴────┴────┴────┴────┴────┘
6

7
addFirst(x)：写入 nextFirst=0 后游标回绕到 7
8
              ┌─────────────────────────┐
9
              ▼                         │
10
        ┌────┬────┬────┬────┬────┬────┬────┐
11
        │ x  │  1 │  2 │  3 │  4 │  5 │  6 │ 7 │
12
        └────┴────┴────┴────┴────┴────┴────┴────┘
13
        nextFirst = 7

2.4 动态扩容#

当数组写满（size == memory），需要翻倍扩容并重新规整元素顺序：

1
public void resize() {
2
    if (size() == memory) {
3
        T[] newArray = (T[]) new Object[memory * 2];
4
        for (int i = 0; i < size(); i++) {
5
            newArray[i] = array[Math.floorMod(nextFirst + 1 + i, memory)];
6
        }
7
        array = newArray;
8
        memory *= 2;
9
        nextFirst = memory - 1;
10
        nextLast = size();
11
    }
12
}

这一步把环形结构”拉直”成线性：从 nextFirst + 1 开始按逻辑顺序依次拷贝，然后在更大的数组上重新建立环。关键点：每次扩容后游标都要根据新容量重新计算，因为 memory 变了，floorMod 的模也随之改变。

扩容的平摊分析（amortized analysis）：

每次扩容复制 $O(n)$ 个元素。
但扩容只在容量翻倍时发生，平均到每次插入上是 $\frac{n}{n} = O(1)$ 。

IMPORTANT
虽然最坏情况下单次插入是 $O(n)$ ，但平摊下来仍是 $O(1)$ 。这是”动态数组”类数据结构（如 Java ArrayList）的理论基石。

三、LinkedListDeque61B：双向哨兵链表#

3.1 为什么需要哨兵（Sentinel）#

链表的朴素实现在空列表时有两个 bug：首节点为 null，addFirst / removeFirst 必须写特判分支；而且”空 vs 非空”两种状态代码路径完全不同，极易出错。

哨兵节点是恒存在的哑节点，不存数据。它消除了所有空特判，让首尾操作在空表时也有统一的代码路径。

1
private Node sentinelFirst;  // 头哨兵，永远存在
2
private Node sentinelLast;   // 尾哨兵，永远存在

初始化时两个哨兵互指：

1
public LinkedListDeque61B() {
2
    sentinelFirst = new Node(null, null, sentinelLast);
3
    sentinelLast  = new Node(sentinelFirst, null, null);
4
    // sentinelFirst.next == sentinelLast，即"空"状态
5
}

3.2 双端插入#

addFirst 在头哨兵和原首节点之间插入新节点：

1
public void addFirst(T item) {
2
    Node n = new Node(sentinelFirst, item, sentinelFirst.next);
3
    sentinelFirst.next.prev = n;   // 原首节点指回新节点
4
    sentinelFirst.next = n;        // 头哨兵指向新节点
5
    size++;
6
}

注意这里的顺序：必须先让新节点的前驱/后继接线，再让哨兵改指向。如果先改 sentinelFirst.next，就丢了到原首节点的引用。这类”接线顺序”错误是链表实现最常见的 bug 来源。

3.3 哨兵带来的统一性#

有了哨兵，“空表插入”和”非空表插入”走的是同一条代码路径：

1
插入前（非空）：S1 ↔ A ↔ B ↔ S2
2
插入后：        S1 ↔ N ↔ A ↔ B ↔ S2
3

4
插入前（空表）：S1 ↔ S2
5
插入后：        S1 ↔ N ↔ S2      ← 和上面完全一致！

isEmpty() 也因此退化为一个引用判断：

1
public boolean isEmpty() {
2
    return sentinelFirst.next == sentinelLast;
3
}

这是哨兵结构最优雅之处：把特殊情形变成普通情形，边界条件从”两个”（空/非空）合并成”一个”。

四、复杂度对比#

两种实现各有取舍，这是数据结构选型的核心权衡：

操作	ArrayDeque	LinkedListDeque
`addFirst` / `addLast`	$O(1)$ 平摊	$O(1)$
`removeFirst` / `removeLast`	$O(1)$	$O(1)$
`get(index)`	$O(1)$ （直接映射）	$O(n)$ （必须遍历）
内存	紧凑、缓存友好	每个节点额外 3 个引用
扩容	需要翻倍复制	不需要

NOTE
课程要求 get 是 $O(n)$ 的（链表无索引），而数组版能到 $O(1)$ ——但注意真实项目中接口契约并不会承诺这个。这也说明：接口抽象会隐藏实现的性能差异，选型必须在架构层面决定。

五、Karplus-Strong 算法：物理建模吉他#

5.1 从物理到算法#

真实吉他弦的振动并非简单正弦波：拨弦产生的是复杂非周期信号，能量随时间指数衰减，且有独特的泛音结构。Karplus-Strong 算法用极简的数字信号处理模型近似了这一过程，核心思想是噪声激励 + 反馈延迟环：

1
拨弦（白噪声） → [环形缓冲] → 采样输出
2
                      ↑            │
3
                      └──── 滤波 ←┘
4
               （相邻样本平均 × 0.996）

三步核心操作：

pluck（拨弦）：用白噪声填充缓冲区——随机数序列模拟拨弦瞬间的混沌振动。
tic（推进）：取出队首样本，与下一个样本求平均后乘以衰减系数 DECAY = 0.996，再放回队尾。这一”平均”是低通滤波，衰减高频能量，模拟弦的能量耗散。
sample（采样）：读出队首值作为当前输出。

5.2 用 Deque 实现环形缓冲#

GuitarString 的缓冲区直接复用 Deque61B<Double>：

1
public class GuitarString {
2
    private static final int SR = 44100;       // 采样率
3
    private static final double DECAY = .996;  // 能量衰减系数
4
    private Deque61B<Double> buffer;
5

6
    public GuitarString(double frequency) {
7
        int capacity = (int) Math.round(SR / frequency);
8
        buffer = new ArrayDeque61B<>(capacity);
9
        for (int i = 0; i < capacity; i++) {
10
            buffer.addFirst(0.0);
11
        }
12
    }
13
}

缓冲区长度 = 采样率 ÷ 基频。例如标准音 A（440 Hz）：

$capacity = \frac{44100}{440} \approx 100$

这意味着缓冲区恰好容纳一个周期的采样，tic 每次取出头、放回尾，信号在环中循环一圈的时间正好对应弦振动的周期——这是算法能产生正确音高的几何约束。

5.3 pluck 与 tic 的实现细节#

1
public void pluck() {
2
    int n = buffer.size();
3
    for (int i = 0; i < n; i++) buffer.removeFirst(); // 清空
4
    for (int i = 0; i < n; i++) buffer.addFirst(Math.random() - 0.5); // 白噪声
5
}
6

7
public void tic() {
8
    double first = buffer.removeFirst();
9
    double next  = buffer.get(0);
10
    double last  = (first + next) / 2 * DECAY;
11
    buffer.addLast(last);
12
}

tic 的一行，本质是一阶数字低通滤波器：

$y[n] = 0.996 \cdot \frac{x[n] + x[n+1]}{2}$

平均值削弱了相邻样本的差异 → 抑制高频分量。
每次衰减 0.4% → 信号指数衰减到 $1/e \approx 37\%$ 需要约 $\frac{1}{0.004} = 250$ 步。

WARNING
注意一个易错点：Math.random() - 0.5 每次调用必须产生新的随机数。如果偷懒用一个固定值或复用同一个随机变量，缓冲区里全是相同样本，滤波后信号立即归零，听不到任何声音。

5.4 合成主循环#

GuitarHeroLite 把音频推进和画面渲染耦合在一个循环里：

1
while (true) {
2
    if (StdDraw.hasNextKeyTyped()) {
3
        char key = StdDraw.nextKeyTyped();
4
        if (key == 'a') { stringA.pluck(); ... }
5
        else if (key == 'c') { stringC.pluck(); ... }
6
    }
7
    double sample = stringA.sample() + stringC.sample(); // 叠加
8
    StdAudio.play(sample);                               // 播放
9
    stringA.tic();                                       // 推进
10
    stringC.tic();
11
}

三行代码对应三个层次：采样（读）→ 播放（输出）→ 推进（状态转移）。多个琴弦通过简单的加法叠加，这是线性系统叠加原理的直接应用。

六、迭代器与测试闭环#

6.1 迭代器的实现#

接口要求 Iterable<T>，数组版用内部游标实现：

1
public class ArrayIterator implements Iterator<T> {
2
    private int index = Math.floorMod(nextFirst + 1, memory);
3
    public boolean hasNext() { return index < size(); }
4
    public T next() {
5
        T x = array[index];
6
        index = Math.floorMod(index + 1, memory);
7
        return x;
8
    }
9
}

6.2 测试驱动#

项目配套 JUnit 测试覆盖了三个层次：

1
// 1. 功能测试：插入、删除、查询的语义正确性
2
@Test
3
public void testAddAndRemove() { ... }
4

5
// 2. 边界测试：空表删除、越界索引、扩容后数据完整性
6
@Test
7
public void testResizeKeepsData() { ... }
8

9
// 3. 前置条件测试：违反契约时明确报错而非静默失败
10
@Test(expected = ...)
11
public void testPreconditionViolation() { ... }

其中 TestGuitarString 通过验证 tic 前后的能量变化来间接检查音频算法的正确性——数据结构测试与算法测试在”用 Deque 当缓冲”这个交汇点汇合。

七、总结与思考#

这个项目最值得回味的不是某一行代码，而是抽象层的逐级构建：

接口层：Deque61B 定义了”能做什么”，屏蔽了内部结构。
实现层：循环数组（时间换空间中的均匀性）与哨兵链表（空间换代码统一性）是同一契约的两种物理诠释。
应用层：GuitarString 把 ADT 当作环形缓冲，实现了物理建模的音频合成，而它对底层实现毫无感知。

从数据结构到算法，再到能”听到”的物理仿真——这正是 CS61B 反复强调的核心能力：用正确的抽象，让复杂的系统分而治之。

如果这篇文章对你有帮助，欢迎分享给更多人！

CS61B Project 1B：从双端队列到物理建模吉他合成器

https://hajim1.art/posts/cs61b-proj1b-deque-guitar-hero/

作者

Takamatsu Tomori

发布于

2025-05-28

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

3D 魔方：React + Three.js 交互与层先法自动求解

CS61A 三连：Hog、Cats 与 Ants——从函数式到面向对象

我真的有在认真念书

项目概览#

一、接口设计：先定义”什么”，再想”怎么做”#

二、ArrayDeque61B：循环缓冲区#

2.1 朴素实现的问题#

2.2 关键设计：`nextFirst` 与 `nextLast`#

2.3 读取的索引映射#

2.4 动态扩容#

三、LinkedListDeque61B：双向哨兵链表#

3.1 为什么需要哨兵（Sentinel）#

3.2 双端插入#

3.3 哨兵带来的统一性#

四、复杂度对比#

五、Karplus-Strong 算法：物理建模吉他#

5.1 从物理到算法#

5.2 用 Deque 实现环形缓冲#

5.3 pluck 与 tic 的实现细节#

5.4 合成主循环#

六、迭代器与测试闭环#

6.1 迭代器的实现#

6.2 测试驱动#

七、总结与思考#

目录

我真的有在认真念书

项目概览#

一、接口设计：先定义”什么”，再想”怎么做”#

二、ArrayDeque61B：循环缓冲区#

2.1 朴素实现的问题#

2.2 关键设计：nextFirst 与 nextLast#

2.3 读取的索引映射#

2.4 动态扩容#

三、LinkedListDeque61B：双向哨兵链表#

3.1 为什么需要哨兵（Sentinel）#

3.2 双端插入#

3.3 哨兵带来的统一性#

四、复杂度对比#

五、Karplus-Strong 算法：物理建模吉他#

5.1 从物理到算法#

5.2 用 Deque 实现环形缓冲#

5.3 pluck 与 tic 的实现细节#

5.4 合成主循环#

六、迭代器与测试闭环#

6.1 迭代器的实现#

6.2 测试驱动#

七、总结与思考#

目录

2.2 关键设计：`nextFirst` 与 `nextLast`#