ARTS 0830: 有效括号、LLM 在预测下一个词与真正昂贵的是逐对象 new/free

每周完成一个 ARTS： 至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。（也就是 Algorithm、Review、Tips、Share 简称 ARTS）

Algorithm

这周我们写一个关于栈相关的题目。我们来介绍一下什么是栈，并且栈可以这么实现？

1、栈（stack）是一种遵循先入后出逻辑的线性数据结构。支持的操作是 pop（出栈）、push（入栈）、peek（访问栈顶元素）

2、栈如何实现，分为两种实现方式：数组和链表，两种方式各有优缺点：

1）数组：时间效率相对不稳定，因为如果出现数组扩容的情况插入效率会下降很多；空间效率可能会浪费一些空间，因为扩容的时候会数组长度 x 2

2）链表：时间效率更稳定一些；需要存储额外的指针，占用空间相对较大

对应的简单代码实现：

1）Array实现：

    // Array 实现栈
    private final ArrayList<Integer> stack = new ArrayList<>(10);

    public void push(Integer i) {
        stack.add(i);
    }

    public Integer pop() {
        int index = stack.size() - 1;
        return stack.remove(index);
    }

    public Integer peek() {
        return stack.get(stack.size() - 1);
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public int size() {
        return stack.size();
    }

2）链表实现：

这里使用的 ListNode 有两个属性，如果是不使用 ListNode 的 next 属，就需要从 head 找到需要 peek 的 pre 节点，还需要进行循环判断找到 pre 节点（也就是需要 peek 的前一个）

    private ListNode top; 
    private int size = 0;

    public void push(Integer i) {
        top = new ListNode(i, top);
        size++;
    }

    public Integer pop() {
        if (top == null) {
            return null;
        }
        Integer val = top.val;
        top = top.next;
        size--;
        return val;
    }

    public Integer peek() {
        return top == null ? null : top.val;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

---

LeetCode 题目

image-20260830112609834

1）第一次做感觉用 Stack 还真是没有想到，一开始还以为这个 []() 和 ([]) 是两种情况

2）更多的情况举一些具体的例子，来辅助：

输入 "()[]{}"

第一次：输入 ( ，栈 空

第二次：输入 )，栈 (，进行判断是否匹配，发现匹配就推出

等等

输入 "([)]"

第一次：输入 ( ，栈空

第二次：输入 [，栈 ( [

第三次：输入 )，栈 ([)

第四次：输入 ]，栈 ([)]

最终栈还有 stack 有数据，就证明不匹配

输入 "([])"

第一次：输入 ( ，栈空

第二次：输入 [，栈 ([

第三次：输入 ]，进行对比发现 stack.peek 元素和当前进行匹配，那么最终栈的元素 (

第四次：输入 )，进行对比发现 stack.peek 元素和当前进行匹配，那么最终栈的元素为空

最终栈的 stack 没有数据，证明是 valid 的

class Solution {

    private Map<Character, Character> map = new HashMap<>();

    {
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
    }

    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (!stack.isEmpty() && Objects.equals(aChar, map.get(stack.peek()))) {
                stack.pop();
                continue;
            } 
            stack.push(aChar);
            
        }
        return stack.isEmpty();
    }
}

Review

文章 https://www.3blue1brown.com/lessons/gpt 关于 LLM 是如何工作的。

关于 LLM 是如何工作的，有大佬是这样说的：

想象一下，有一些书，而书中有一个单词分隔符。这个单词分隔符总是保存某个单词在那个被分隔的单词之前出现了什么，并把它保存下来。通过概率和数学计算，LLM 使用这些分隔出来的单词进行训练，并尝试预测下一个单词是什么。所以在我给你的这个上下文中，这个单词分隔符会保存书中的每一个单词，以及哪个单词出现在它之前、哪个单词出现在它之后，例如“bread pudding”，然后是“new bread”，然后是“new bread is good”“too good!” 然后，当 LLM 收到问题“is bread pudding good?” 时，你会从你这里收到“pudim”“bread”和“good”这些词，并返回短语“bread pudding is good!”。这个例子很荒谬也很简单，但就是这么回事。

很荒谬但是 LLM 就是这样工作的，其实就像人脑的神经元也是一样的，一个很简单但是每一个连接起来就变得异常复杂，可以处理很多复杂的问题。

Tips

1）MacOS 不睡眠的命令：

caffeinate -d

2）用 pi 在需要 -p 的模式下还是挺好用的。比如批量校验文字是否有问题，可以用 Python 脚本 + pi 实现

3）语音转文字可以使用 whisper-cpp 搭配 large-v3-turbo 实现。

下载 whisper-cpp：

brew install whisper-cpp

下载模型：

注意：1）不要设置系统 proxy 2）需要设置 Token 获取链接

hf download ggerganov/whisper.cpp \
  ggml-large-v3-turbo.bin

Share

文章：https://www.gingerbill.org/article/2026/01/02/was-it-really-a-billion-dollar-mistake/

「十亿美元错误」可能高估了 null 的问题。真正昂贵的，是「每个对象单独 new/free」的个体思维。

Tony Hoare 把空引用称为「十亿美元错误」，但 Odin 作者 gingerBill 认为，null 本身未必是最致命的问题。

在 C/Odin 里，空指针反而是最好发现、也相对少见的错误，更常见的是 use-after-free、指针运算错误和访问未映射内存。去掉 null，也只是把问题转移到「到处检查」或「强制初始化」上。

更深层的问题是内存管理方式：一个对象一个对象地分配和释放。

更合理的思路是把生命周期相同的数据放在一起，用 arena、pool、scratch （下面有介绍）这类方式批量管理。这样可以减少 malloc/free、减少指针和管理开销，也能避免大量无意义的逐对象初始化。

- Arena：预先申请大块内存，统一分配，最后整体释放。

- Pool：预先准备对象，需要时取出，用完后归还复用。

- Scratch：专门存放临时数据，用完后一次性清空释放。

真正值得警惕的，可能不是 null，而是我们习惯把一组数据拆成一个个独立对象，然后逐个管理。