Python可变与不可变数据：C语言视角的深度解析
一、从"盒子"到"标签"1.1 C语言的"盒子"模型在 C 语言中，变量是一个有固定大小的"盒子"： 1234int a = 10; // 盒子 a 里装着 10int b = a; // 把 a 盒子里的 10 拷贝一份，装进盒子 ba = 20; // 把盒子 a 里的值改成 20// b 仍然是 10，因为每个盒子独立存储自己的值 赋值（a = b）就是把 b 盒子里的东西拷贝一份到 a 盒子里。两个盒子互不干扰。 1.2 Python的"标签"模型Python 的变量更像一张"便利贴"或"标签"，而数据本身是堆内存中的一个"对象"： 1234a = 10 # 创建整数对象 10，把标签 a 贴上去b = a # 把标签 b 也贴到同一个对象 10 上a = 20 # 把标签 a 从 10 撕下来，贴到新对象 20 上# b 仍然贴在 10 上 赋值（a = b）不是拷贝对象，而是给...
内存池的初步实现
导言在 C++ 开发中，频繁使用 new/delete 会导致内存碎片、系统调用开销大等问题，尤其在多线程场景下性能损耗显著。内存池作为一种高效的内存管理方案，通过预先申请大块内存、重复利用空闲内存的方式，能有效解决这些问题。 一、内存池核心设计思路1.1 解决的核心问题 内存碎片：原生 new/delete 分配的内存大小随机，长期使用会产生大量无法利用的小块内存（碎片）； 系统调用开销：每次 new 都会触发系统调用（如 brk/mmap），频繁调用会严重影响性能； 多线程安全：原生内存分配器的锁竞争会导致多线程场景下性能下降。 1.2 核心设计方案我们的内存池采用 “多池分治 + 无锁空闲链表 + 内存块复用” 的设计，具体如下： 多池分治：按内存大小划分 64 个内存池，分别管理 8~512 字节的内存（步长 8 字节），超过 512 字节的内存直接使用原生 new/delete； 无锁空闲链表：用原子操作（CAS）实现空闲内存的入队 / 出队，避免多线程锁竞争； 内存块复用：预先申请 4096 字节的大块内存（与...
并行与向量化（SIMD）
1. 为什么需要并行：三类并行层级CS61C 的核心立场是"把一台机器抽象出来给你看"。在"机器"这一层，性能提升几乎都来自并行——让硬件在同一时刻做更多事。并行按粒度从细到粗分成三类： 指令级并行（ILP, Instruction-Level Parallelism）：单条指令内部、或相邻指令之间重叠执行。我们前面讲过的流水线、乱序执行、转发（forwarding）都属于这一类。 数据级并行（DLP, Data-Level Parallelism）：同一份操作，作用在很多个数据点上。典型场景是"对 100 万个像素都加 10""把两个等长数组逐元素相加"。 线程级并行（TLP, Thread-Level Parallelism）：多核，每个核心跑不同的线程，甚至不同程序。 本篇聚焦 DLP，因为它最"便宜"：不需要多核、不需要改算法、不需要加锁，很多时候只把数据组织方式改一改，或者让编译器帮个忙，就能白捡数倍吞吐。 本质一句话：当同一件事要在大量数据上重复做时，就把"...
虚拟内存
虚拟内存 一句话本质：虚拟内存是硬件（MMU）+ 操作系统共同提供的一块“每人独享整片地址空间”的幻觉——程序以为自己霸占了从 0 到 4GB/256TB 的全部内存，实际上物理内存被所有进程切片共享，地址翻译由 MMU 在每条指令取数时悄悄完成。 CS61C 站在机器/架构视角看虚拟内存：我们关心的是「一条 lw 指令里的地址是怎么变成内存条上某个字节的物理位置的」「为什么要分页」「TLB 为什么能让翻译几乎免费」。至于缺页时操作系统怎么换页、怎么选受害者页，那是 CS162 的主场（本文只在末尾点到为止并附对照）。 1. 为什么需要虚拟内存没有虚拟内存的裸机世界里，所有程序直接操作物理地址，会带来三个老大难： 隔离性为零：进程 A 写错一个指针就可能踩烂进程 B 的数据，甚至改掉内核。 地址空间碎片：程序加载时得去找一块足够大的连续物理内存，内存用久了就「东一块西一块」。 无法超配（overcommit）：物理内存只有 8GB，程序却想用 16GB？直接没门。 虚拟内存用一层地址抽象同时解决这三点： 每个进程拿到一个独立的虚拟地址空间（virtua...
Python函数参数传递的真相——为什么你的变量没被修改？
一、一个令人困惑的场景你刚学 Python 不久，写了这样一段代码： 123456def try_change(x): x = 100num = 42try_change(num)print(num) # 输出：42 —— 为什么不是 100？ 你期望 num 被改成 100，但它纹丝不动。然而换一种写法： 123456def try_append(lst): lst.append(4)nums = [1, 2, 3]try_append(nums)print(nums) # 输出：[1, 2, 3, 4] —— 居然改了！ 列表却被成功修改了。同一个函数、同一种"传参"，为什么有时改了外面，有时改不了？Python 到底是"传值"还是"传引用"？ 答案是：都不是。Python 使用的是一种更精确的机制——传对象引用（Pass by Object Reference）。 二、核心概念：传对象引用2.1 变量是"标签"，不是"盒子"在 C++ 中，变量是一个&qu...
C++ STL 算法绑定成员函数问题整理
一、STL 算法调用成员函数的典型错误在开始解决方案前，我们先明确最常见的错误模式，理解问题本质才能避免重复踩坑。 1.1 错误代码示例1234567891011121314151617181920212223242526#include <vector>#include <algorithm>#include <iostream>class NumberProcessor {private: int value;public: NumberProcessor(int v) : value(v) {} bool isEven() const { return value % 2 == 0; } // 筛选条件成员函数 void printValue() const { std::cout << value << " "; } // 操作成员函数 void add(int num) { va...
存储器层次与 Cache
上一篇我们让多条指令在流水线上重叠执行，把吞吐翻了几倍。但流水线有一个天敌：取指、访存要等内存。如果 CPU 每取一条指令、读一个变量都要干等内存几百个周期，流水线再深也救不回来。 这一篇往上抬一级视角，回答一个根本问题——为什么今天的计算机既能"内存很大"又能"访问很快"？ 答案是用层次结构（memory hierarchy）把"快而贵"和"慢而便宜"组合成一套用户看来又大又快的存储系统，而真正的魔法器件就是 Cache。 一句话定位：局部性是因，Cache 是果；命中是常态，缺失是代价。 1. 存储器层次：用金字塔换"又快又大"CPU 寄存器最快（亚纳秒、在芯片内），但容量只有几百字节；DRAM 主存便宜、能上 GB，但慢几十到上百倍；磁盘更便宜、能上 TB，但慢百万倍。如果只用一个层级，要么快得装不下，要么大得慢死。 寄存器 / L1 ~1ns 最贵 最少(KB) CPU Cache(L2...
组合/时序逻辑与流水线
前两篇我们把 C 翻译成了 RISC-V、把函数调用拆成了栈帧。但还有一个更底层的问题没回答：一条指令从"二进制"变成"动作"，在硬件里到底经历了什么？ 这一篇往下钻到门电路和时钟，再往上拉到流水线——看同一颗 CPU 是怎么靠"让多条指令重叠执行"把吞吐翻几倍的，以及翻倍的代价（冒险）。 一句话定位：组合逻辑管"算"，时序逻辑管"记"，流水线管"快"，冒险管"坑"。 1. 组合逻辑：没有记忆的电路组合逻辑（combinational logic）的定义是——输出只取决于当前输入，和过去发生过什么无关。给它同一组输入，永远得到同一组输出，它肚子里不存任何状态。 最小例子是半加器（half adder）：两个 1 比特相加。 123a ──┬── XOR ── sum │b ──┴── AND ── carry a b sum (a⊕b) carry (a·b) 0 0 0 0 0 1 1 0 1 0 1 0 1...
Python函数柯里化：将多参数函数转化为单参数函数链
一、引言如果你写过 functools.partial，或者曾经用闭包"锁定"一个参数，那你其实已经在不知不觉中使用了**柯里化（Currying）**的思想。这个名字来源于数学家 Haskell Curry，而它背后的思想极为简洁：将接受多个参数的函数，转化为一系列只接受一个参数的函数。 从 Python 的视角出发，柯里化不仅是一种函数式编程技巧，更是深入理解闭包、高阶函数与"函数是对象"这三件事的绝佳切入点。 二、什么是柯里化2.1 原始定义在数学和 lambda 演算中，柯里化的定义是： 将一个接受 N 个参数的函数 f(a, b, c) 转化为 f(a)(b)(c) —— 即接受第一个参数返回新函数，新函数接受第二个参数返回下一个新函数，直到收集完所有参数时执行原始逻辑。 2.2 一个直观的例子从一个简单的加法函数开始： 12345# 普通写法：一次接受两个参数def add(a, b): return a + bprint(add(3, 5)) # 输出：8 柯里化之后： 123456789# 柯里化写法：每次只接...
std::allocator 及 std::vector 原理实现
一、Vector 整体结构与 allocator 定位1.1 Vector 核心数据成员构成std::vector 作为动态数组容器，其核心数据结构由三个指针（或类似指针的迭代器）构成，分别指向： 数据区起始位置（begin）：指向已分配内存块的起始地址 有效数据结束位置（end）：指向当前已存储元素的下一个位置 内存块结束位置（capacity_end）：指向已分配内存块的末尾位置 1.2 allocator 在 Vector 中的核心定位std::allocator 作为 Vector 的内存分配器组件，承担以下核心职责： 提供类型安全的内存分配 / 释放接口 解耦容器逻辑与底层内存管理实现 实现元素构造与内存分配的分离操作 支持自定义内存分配策略的扩展接口 二、std::allocator 核心接口与内存分配流程2.1 allocator 核心成员函数 allocate(size_t n)：分配能够存储 n 个元素的未初始化内存块，返回指向内存块起始位置的指针，内存大小为 n * sizeof (T) deallocate(T p, size_t n)*：...
过程调用与栈帧 / 调用约定
CPU 只有 32 个寄存器，但一段递归可以轻松嵌套一万层，每一层都有自己的一份局部变量、都记得该回到哪里去。这两件事摆在一起是有矛盾的：32 个格子，怎么装下一万层的现场？ 答案不在硬件里。RV32I 里没有一条叫「call」的指令，也没有任何一条指令知道「函数」是什么。函数是约定造出来的幻觉——一份编译器之间互相签署的合同，加一块叫做栈的内存。这一篇就把这份合同逐条拆开。 1. 一次函数调用要解决四件事先别看汇编，想想 C 里这一行发生了什么： 1int y = f(x) + 1; 拆成机器视角，有四个独立的问题需要各自解决： 问题 说白了 谁来解决 去哪儿 PC 得跳到 f 的第一条指令 jal 指令 怎么回来 f 结束时得知道跳回哪一条 返回地址寄存器 ra 参数怎么递 x 得让 f 看得见 ABI 约定：a0–a7 寄存器归谁 f 里也要用寄存器，会不会把我的值踩了 ABI 约定：caller/callee saved 前两个由硬件（指令）解决，后两个纯靠约定——硬件完全不管你有没有遵守。这就是为什么手写汇编最容易死在后两条上。 ...
RISC-V 汇编基础
上一课我们把 C 语言的指针和位运算拽到了门电路旁边。现在还有一道缝没填上：sum += a[i] 这么一行字，CPU 里那几十亿个门到底是"照着什么"动起来的？答案是指令——一串二进制码，每一条都对应硬件里一小段被点亮的通路。汇编就是这串二进制的人类可读写法。 这一篇只干一件事：把 RV32I 这套指令集讲透到"你能手写一个循环、并且知道每条指令在硬件里意味着什么"的程度。 1. 指令集是硬件与软件之间的合同CPU 不认识 C，也不认识 Java。它只认识一件事：从内存里取一个 32 位的数，按事先约定好的规则解码，然后驱动相应的电路。这份"事先约定好的规则"就是 ISA（Instruction Set Architecture，指令集架构）。 ISA 规定了三样东西，一样都不能少： ISA 规定什么 具体内容 为什么必须由 ISA 定 有哪些寄存器 RV32I：32 个 32 位通用寄存器 编译器要知道往哪儿放变量 有哪些指令 add / lw / beq …… 二进制码怎么解码是...
C++ 使用 bind / mem_fn 了解函数对象与可调用实体
一、核心概念辨析在开始代码实现前，需先明确三个核心概念的区别： 概念 定义 典型示例 可调用实体 (Callable Entity) 所有可以通过()语法调用的对象或表达式的统称 函数指针、lambda 表达式、仿函数、bind返回对象 函数对象 (Function Object) 具有operator()成员函数的类实例（仿函数） 自定义struct Add { int operator()(int a, int b); } 可调用对象 (Callable Object) 除函数指针外的可调用实体，强调 "对象" 属性 lambda 表达式、std::bind返回值、std::mem_fn返回值 二、完整代码实现以下代码基于 C++11 标准实现，包含自由函数绑定、成员函数绑定、参数占位符使用、带状态函数对象等典型场景： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585...
Python函数框架：外框架、内框架与环境模型
一、引言当你在 Python 中调用一个函数时，解释器在背后做了大量工作来管理变量的"可见性"。为什么函数内部能访问全局变量，但全局却不能直接看到函数内部的变量？为什么嵌套函数能记住外层函数的变量？这一切的答案，都指向一个核心概念——环境模型（Environment Model）。 本文源自 UC Berkeley CS61A 课程的核心内容，带你从"框架（Frame）"的视角理解 Python 的函数调用机制。 二、什么是环境模型环境模型是 Python 解释器用来追踪变量名与值之间绑定关系的一套机制。它的核心思想极其简单： 一个表达式在特定环境中被求值。环境由一系列框架（Frame）组成，每个框架包含一组绑定（Binding）——即变量名到值的映射。 在这套模型中，有两种最关键的结构： 全局框架（Global Frame）：程序启动时就存在的唯一框架，存储全局变量和函数定义 局部框架（Local Frame）：每次函数调用时动态创建的新框架，存储函数的形参和局部变量 三、框架是什么框架本质上是一个上下文（Context），记录着...
数字逻辑与 C 语言回顾
不管你平时写 Java 还是 C，这台计算机底下其实没有任何"对象"，只有一堆在 0 和 1 之间反复横跳的晶体管。CS61C 要做的，就是把"软件"一路拽回"硬件"的起点。这一篇干两件事：先用数字逻辑把"软件"接回"硬件"（门电路、加法器、补码），再系统回顾 C 语言里最容易踩的坑——指针、手动内存、位运算。 1. 什么是"位"：一切从开关开始计算机最底层没有整数、没有字符串，只有一个个能表示两种状态的元件——通电 / 断电，记为 1 / 0，这就是一个 bit（位）。把若干 bit 并排，就能表示更大的数：8 个 bit 叫 1 字节（byte），32 个 bit 是常见 int 的宽度。 单个 bit 太弱，于是我们用"门电路（gate）"把 bit 组合运算。门是接受若干 0/1 输入、输出一个 0/1 的小电路，由晶体管搭成。最基础的几种： AND &...
算法复杂度实战与收尾
十篇走到最后。前面我们学了数组、链表、栈队列、树与平衡树、哈希、堆、图、并查集、排序——每一个都挂着一串 O(...)。可"复杂度"不是背结论，而是拿到一段代码或一道题，能亲手算出来、能选对数据结构。本篇把散落的工具收拢：怎么解递归式（主定理）、均摊分析回顾、以及一个"看到需求就选结构"的决策表。这是 CS61B 的收官，也是把前面九篇拧成肌肉记忆的一课。 一、实战：看到代码，算出复杂度1.1 循环套循环123for (int i = 0; i < n; i++) // n 次 for (int j = 0; j < n; j++) // 每次 n 次 sum += a[i] * b[j]; 外层 n、内层 n → O(n²)。 1.2 循环减半（二分、堆下沉）1for (int i = n; i > 0; i /= 2) process(i); // 每次规模 /2 i 走 n → n/2 → n/4 → … → 1，共 log₂ n 步 → O(log n)。 坑①：log...
Python如何像C++引用头文件
一、引言在C++中，我们通过#include指令引用头文件来复用代码，这种方式使得代码结构更加清晰，便于维护和管理。而在Python中，虽然没有直接的"头文件"概念，但通过其强大的模块导入系统，我们同样可以实现类似的代码组织和复用功能。本文将详细介绍Python中如何像C++引用头文件一样组织和导入代码。 二、C++头文件与Python模块的对比2.1 C++的头文件机制在C++中，头文件（.h文件）通常包含： 函数声明 类定义 常量定义 模板声明 通过#include指令，我们可以在源文件中引用这些头文件，从而使用其中定义的内容。 2.2 Python的模块机制在Python中，模块是一个包含Python定义和语句的文件，文件名就是模块名加上.py后缀。通过import语句，我们可以在其他Python文件中导入并使用模块中的内容。 三、Python模块的基本使用3.1 创建模块创建一个Python模块非常简单，只需要创建一个.py文件并在其中定义函数、类、变量等。 例如，创建一个名为utils.py的模块： 1234567891011# utils.py...
图形计算程序
引言在传统的 C++ 面向对象设计中，我们通常使用虚函数实现多态。本文将展示如何使用std::function替代虚函数，并结合移动语义，构建一个更灵活高效的图形计算程序。这种方式不仅能保持多态性，还能提升性能并增加代码灵活性。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631...
并查集与排序（归并、快排、堆排）
前面几篇都在讲"怎么组织数据、怎么查找"。本篇补两个 CS61B 里极其常用、却容易被低估的工具：**并查集（Union-Find）**管"动态连通性"，三大 O(n log n) 排序管"把数据排好序"。它们一个藏在 Kruskal 最小生成树里，一个藏在 Arrays.sort 背后——看似简单，细节全是坑。 一、并查集：谁和谁是一伙的？一句话：并查集维护若干"不相交集合"，支持两个操作——find(x) 找 x 的祖先（代表），union(x,y) 把 x、y 所在集合合并。它回答的是"这两个元素连通吗"。 典型场景：逐步加边建网络，随时问"a 和 b 现在通不通"；或 Kruskal 算法里判断加一条边会不会成环。 1.1 朴素 vs 优化朴素实现 union 直接把一棵树挂到另一棵，最坏退化成链，find 变 O(n)。两个经典优化把它压到几乎 O(1)（反阿克曼函数 α(n)，实际常数级）： 按秩/大小合并（union by rank&...
C++ 文件读取再整理
一、文件读取核心概念与基础流程1.1 文件操作的三要素文件读取本质是 "数据在外部存储与内存间的传输过程"，需关注三个核心要素： 流对象：C++ 标准库通过std::ifstream（输入文件流）提供文件读取接口，是连接程序与外部文件的桥梁 流状态：通过good()/eof()/fail()/bad()四个状态标志判断操作有效性 数据缓冲区：操作系统与标准库均会维护缓冲区，减少磁盘 IO 次数（默认缓冲区大小通常为 4KB 或 8KB） 1.2 基础文件读取流程（标准范式）所有文件读取操作都遵循 "打开 - 读取 - 关闭" 的核心流程，标准实现代码如下： 123456789101112131415161718192021222324252627282930313233343536373839#include <fstream>#include <iostream>#include <string>int main() { // 1. 创建流对象并打...
图：表示、DFS、BFS 与 Dijkstra
数组管顺序，树管层次，哈希管查找——可现实里的关系常常既不是一条线、也不是一棵树：地铁线网、朋友关系、任务依赖、互联网路由，全都是"点连着点"的网络。这种结构叫图（Graph）。本篇我们解决三件事：图怎么存进计算机、怎么把整张图"走一遍"、以及怎么在带权图里找到两点间最短的路。 一、是什么：顶点、边、权一句话：图 = 顶点集合 V + 边集合 E；边可以有向/无向，可以带**权重（权）**表示距离/代价/时间。 无向图：边双向（朋友关系）。 有向图：边单向（关注关系、依赖）。 带权图：边上标数字（地图里程）。 二、怎么存：邻接表 vs 邻接矩阵这是图论里第一个关键取舍。 维度 邻接表（adjacency list） 邻接矩阵（adjacency matrix） 存储 O(V+E) O(V²) 遍历某点邻居 O(degree) 很快 O(V) 要扫整行 判断两点是否相邻 O(degree) O(1) 适合 稀疏图（大多数真实网络） 稠密图、需要频繁查边 ...
Python 生成器和迭代器深度解析
一、什么是迭代器？迭代器（Iterator）是 Python 中一种实现了迭代协议的对象，它允许我们逐个访问集合中的元素，而不需要知道集合的内部结构。迭代器必须实现两个方法： __iter__()：返回迭代器对象本身 __next__()：返回下一个元素，如果没有更多元素则抛出 StopIteration 异常 1.1 迭代器的基本使用123456789101112# 创建一个迭代器numbers = [1, 2, 3, 4, 5]iterator = iter(numbers)# 使用 next() 函数获取下一个元素print(next(iterator)) # 输出: 1print(next(iterator)) # 输出: 2print(next(iterator)) # 输出: 3# 使用 for 循环遍历（自动处理 StopIteration 异常）for num in iterator: print(num) # 输出: 4, 5 1.2 自定义迭代器1234567891011121314151617class Countdown: def...
堆与优先队列（二叉堆）
队列我们都熟：先进先出，队头永远是来得最早的那一个。可现实往往不按先来后到——急诊室里重伤员优先，操作系统里短作业优先，Dijkstra 最短路里"当前距离最小"的节点优先。我们需要一种"按优先级出队，而不是按到达顺序"的结构，这就是优先队列（Priority Queue）；而它最高效的数组实现，叫二叉堆（binary heap）。 本篇讲清三件事：堆长什么样、插入/取最小怎么 O(log n) 完成、以及它和排序、图算法的关系。 一、是什么：堆不是"排好序的数组"一句话：二叉堆是一棵"完全二叉树"，满足堆序性质（heap property）——每个节点的值都不大于（最小堆）或不小于（最大堆）它的孩子。 完全二叉树：除最后一层外全满，最后一层从左往右填。这个形状让它能紧凑地存进数组，不需要指针。 堆序性质：最小堆里，父 ≤ 子，所以全局最小值一定在堆顶（下标 0）。最大堆反过来。 最小堆（树视图 = 数组视图） 2 5 7 9 11 ...
C++ 中 std::bind 与 std::function
一、std::function —— 可调用对象的 "万能容器"1.1 概念解析：什么是 std::function？std::function 是 C++11 标准库 头文件中引入的通用可调用对象封装器，其核心作用是将各种不同类型的可调用实体（函数指针、成员函数指针、lambda 表达式、函数对象）统一到一个类型安全的容器中。 可以将其类比为 "函数的通用接口转换器"—— 无论原始可调用对象的类型如何，只要签名（返回值类型 + 参数类型列表）匹配，就能被 std::function 封装并统一调用。 1.2 实现原理：类型擦除（Type Erasure）std::function 本质是通过类型擦除技术实现的多态封装，核心流程如下： 定义一个抽象基类（如 function_base），包含纯虚函数 operator()（对应目标签名）和析构函数； 为每个具体的可调用对象类型，实现一个模板派生类（如 function_impl），继承自 function_base，并在 operator() 中调用具体对象； std::functi...
哈希表：散列函数、冲突解决与扩容
你有没有遇到过这种尴尬：数组按下标访问是 O(1)，可它要求"下标必须是整数"；而真实世界里的键往往是字符串（"apple"）、对象（一个 User）、甚至一段二进制。我们想问的是——能不能让任意类型的键，也拥有接近 O(1) 的查找速度？ 哈希表（Hash Table，也叫散列表）就是这个问题的答案，也是 Java HashMap、Python dict、C++ unordered_map 背后的真正引擎。它把"键"压缩成一个数组下标，于是插入、查找、删除都甩掉了"逐个比较"的包袱。但它不是免费的午餐：冲突（collision） 一定会发生，怎么设计散列函数、怎么消解冲突、什么时候扩容，正是本篇要讲清楚的三件事。 一、是什么：哈希表的三件套一句话：哈希表 = 一个数组（桶 buckets）+ 一个散列函数（hash function）+ 一套冲突解决机制。 散列函数 h(key) 把任意键映射到一个整数下标 0..m-1，我们就去数组的那个位置存取。理想情况下每次都 O(1)。 核心约...
