更新题目 Fire Event：多线程回调

题目 everpure-fire-event · 修改（rev 38） · cc · 2026-10-27 00:33
body

@@ -1,23 +1,23 @@
 ## TL;DR
 
-看过全文之后，考前用这一节过一遍。每条都指向正文里讲它的那一节。
-
-- **题**：`register(cb)` 在事件没发生时把回调存起来，发生后当场执行。`fire()` 执行存下的全部回调，从此新来的都直接执行。变体 Trigger 是 `wait()` / `fire()`，Callback manager 只是把「回调」叫成「请求」。开写前先问：fire 调几次、回调由谁执行、要不要保序、回调会不会慢 / 抛异常 / 再调 register（题目一节的表）。
-- **正确写法**（代码一节）：`register` 的「检查标志 + 入队」在同一个临界区。`fire` 的「改标志 + 把队列换出来」在同一个临界区。回调一律在锁外执行。
-- **面试官会改出来的几版 `fire()`**（思路第 3 到 7 节）：
-  - 锁里改标志、出锁后不加锁清队列：对，因为那时队列已经没人共享。
-  - 先 lock / unlock 再在锁外改标志：错。那对锁什么都没保护，fire 会插进 register 的检查和入队之间，回调丢失。
-  - 先改标志再 lock / unlock：对。那次拿锁是栅栏，等正在入队的 register 走完。
-  - 一直拿着锁清队列、最后才改标志：对而且保序，但别人一直登记它就一直清不完。
-- **Trigger**（思路第 8 节）：用条件变量。`fire` 先在锁里改条件、再 `notify_all`。`wait` 外面用 `while`。先 notify 后改条件，等待者会永远睡着。
+- **题**：`register(cb)` 没触发时存回调、触发后当场执行，`fire()` 执行存下的回调（题目一节）。
+- **变体**：Trigger 是 `wait()` / `fire()`，Callback manager 把回调叫「请求」（题目一节）。
+- **先问**：fire 几次、谁执行回调、保不保序、回调会否慢、抛异常、再调 register（题目一节的表）。
+- **正确写法**：`register` 的「检查 + 入队」、`fire` 的「改标志 + 换出队列」各在一个临界区，回调锁外执行（代码一节）。
+- **几版 `fire()`**（思路第 3 到 7 节）：
+  - 锁里改标志、出锁清队列：对，队列已无人共享。
+  - 先 lock / unlock 再改标志：错，锁形同虚设，fire 插进检查和入队之间，回调丢失。
+  - 先改标志再 lock / unlock：对，拿锁是栅栏，等入队中的 register 走完。
+  - 一直持锁清队列、最后改标志：对且保序，但一直有登记就清不完。
+- **Trigger**：条件变量，`fire` 锁里改条件再 `notify_all`，`wait` 外用 `while`，顺序反了等待者永远睡着（思路第 8 节）。
 - **Follow-up**：
-  - 保序用三状态（没触发 / 正在触发 / 已触发完），清到队列空才改成已触发完。
-  - 异常给每个回调单独 `try`。
-  - 回调之间可能同时执行（线程 F 上的旧回调和当场执行的新回调），默认写进接口约定。必须一个一个执行，就全部交给一个工作线程，积压的回调在锁里提交。
-  - 并发执行回调只在回调慢、在等 I/O 时划算。更好的设计是让登记的人传执行器。
-  - 可重置用一个 fire 次数计数器（generation），等的是开始等之后的第一次 fire。
-  - 无锁用 CAS，把标志和链表合成一个原子的头指针。
-  - 可选知识：C++ 里锁外读写的标志要 `std::atomic`，`volatile` 不够（Follow-up 第七条有名词解释）。
-  - 推断的追问（取消登记、fire 传数据、wait 超时、回调里再调 register 或 fire、asyncio）见 Follow-up 第八条。
+  - 保序：三状态（未触发、触发中、已触发），清空队列才算已触发（第一条）。
+  - 异常：每个回调单独 `try`（第二条）。
+  - 旧回调和当场执行的新回调会重叠，默认写进接口约定，要串行就交给一个工作线程、积压的锁里提交（第三条）。
+  - 回调慢、等 I/O 时才值得并发执行，最好让登记方传执行器（第四条）。
+  - 可重置：fire 计数器（generation），只等开始等之后那次 fire（第五条）。
+  - 无锁：CAS，标志和链表合成原子头指针（第六条）。
+  - 可选：C++ 锁外读写的标志用 `std::atomic`，`volatile` 不够（第七条）。
+  - 推断追问：取消登记、fire 传数据、wait 超时、回调里调 register / fire、asyncio（第八条）。
 
 ## 题目
@@ -97,5 +97,5 @@
 ```
 
-队列用的是 `collections.deque`。回调按登记顺序排队，先登记的先执行：`append` 加到队尾，`popleft` 从队头取，两头都是 O(1)。换成 `list` 的话，`pop(0)` 每取一个都要把后面所有元素往前挪一格，是 O(n)，清 n 个回调就成了 O(n²)。实测（2026-10-25）10 万个元素逐个取，`list.pop(0)` 用了 599 毫秒，`deque.popleft()` 用了 4.5 毫秒。后面所有版本、包括「代码」一节和 Follow-up 里的写法，都用同一个 `deque`，名字都叫 `_queue`。
+队列用的是 `collections.deque`。回调按登记顺序排队，先登记的先执行：`append` 加到队尾，`popleft` 从队头取，两头都是 $O(1)$。换成 `list` 的话，`pop(0)` 每取一个都要把后面所有元素往前挪一格，是 $O(n)$，清 n 个回调就成了 $O(n^2)$。实测（2026-10-25）10 万个元素逐个取，`list.pop(0)` 用了 599 毫秒，`deque.popleft()` 用了 4.5 毫秒。后面所有版本、包括「代码」一节和 Follow-up 里的写法，都用同一个 `deque`，名字都叫 `_queue`。
 
 成员变量名前面的下划线是 Python 的约定（PEP 8 叫 non-public）：表示这是类内部的状态，类外面的代码不该直接读写。它只是给读代码的人的提示，解释器不会拦着你访问。两个下划线开头（如 `__fired`）会触发名字改写（name mangling），是为了避免子类里同名变量互相覆盖，这道题用不上。2017 年原帖的 Java 代码用的是 `eventQueue`、`isFired` 这样的公开名字，本页统一改成带下划线的 Python 写法。
@@ -493,7 +493,7 @@
 ## 复杂度
 
-- `register` 是 O(1)（`deque` 往队尾追加）。
-- `fire` 执行 n 个回调是 O(n)，这部分省不掉。
-- 更值得说的是**持锁时间**：两个方法在锁里都只做 O(1) 的事（读标志、追加一个元素、交换两个队列的引用），回调全部在锁外执行。临界区越短，线程之间互相等待的时间越少。
+- `register` 是 $O(1)$（`deque` 往队尾追加）。
+- `fire` 执行 n 个回调是 $O(n)$，这部分省不掉。
+- 更值得说的是**持锁时间**：两个方法在锁里都只做 $O(1)$ 的事（读标志、追加一个元素、交换两个队列的引用），回调全部在锁外执行。临界区越短，线程之间互相等待的时间越少。
 
 ## 易错点
@@ -1161,5 +1161,5 @@
 句柄每次都是新建的对象，同一个函数登记两次也能分开取消。这个写法对，因为删除和 `fire` 换出队列在同一把锁里。`unregister` 拿到锁时，句柄要么还在队列里，删掉以后它永远不会执行，返回 True，要么已经被 `fire` 换走了，返回 False，这个回调会执行或已经执行。不会出现「取消成功了却还是执行了」。返回 False 不代表回调已经执行完：`fire` 可能刚换走队列、还没轮到它，这一点要和面试官说清楚。
 
-代价是 `deque.remove` 要从头找，是 O(n)。登记和取消都很频繁的话，可以把队列换成字典（`dict`），键是句柄、值是回调：Python 3.7 起字典保持插入顺序，删除是 O(1)。
+代价是 `deque.remove` 要从头找，是 $O(n)$。登记和取消都很频繁的话，可以把队列换成字典（`dict`），键是句柄、值是回调：Python 3.7 起字典保持插入顺序，删除是 $O(1)$。
 
 实测（2026-10-25）：
更新题目 Fire Event：多线程回调

body

meta
