CS336: Assignment 1 - BPE

collections.Counter

1. 直接print和for items的顺序是不一样的

   1
   from collections import Counter
   2
   
   3
   c = Counter()
   4
   
   5
   c[0] += 10
   6
   c[1] += 20
   7
   
   8
   print(c)
   9
   # Counter({1: 20, 0: 10})
   10
   
   11
   for a, b in c.items():
   12
       print(a, b)
   13
       # 0 10
   14
     # 1 20

2. defaultdict的效率比Counter高

   1
   import timeit
   2
   from collections import Counter, defaultdict
   3
   import random
   4
   
   5
   # 1. 模拟数据准备
   6
   # 模拟 BPE 中的 (pair, count) 数据流
   7
   # 假设有 1000 种不同的 pair，总共进行 100,000 次累加操作
   8
   unique_pairs = [(f"byte_{i}".encode(), f"byte_{i+1}".encode()) for i in range(1000)]
   9
   data_stream = [random.choice(unique_pairs) for _ in range(100000)]
   10
   # 模拟权重（BPE 中是 += count，而不是简单的 += 1）
   11
   weights = [random.randint(1, 100) for _ in range(100000)]
   12
   data = list(zip(data_stream, weights))
   13
   
   14
   def test_counter():
   15
       """使用 Counter 进行统计"""
   16
       c = Counter()
   17
       for pair, weight in data:
   18
           c[pair] += weight
   19
       return c
   20
   
   21
   def test_defaultdict():
   22
       """使用 defaultdict(int) 进行统计"""
   23
       d = defaultdict(int)
   24
       for pair, weight in data:
   25
           d[pair] += weight
   26
       return d
   27
   
   28
   # --- 运行累加性能测试 ---
   29
   print(f"{'='*10} 累加 (Accumulation) 性能对比 {'='*10}")
   30
   loops = 100
   31
   
   32
   t_counter = timeit.timeit(test_counter, number=loops)
   33
   print(f"Counter 耗时:      {t_counter:.4f} 秒")
   34
   
   35
   t_defaultdict = timeit.timeit(test_defaultdict, number=loops)
   36
   print(f"defaultdict 耗时:  {t_defaultdict:.4f} 秒")
   37
   
   38
   speedup = (t_counter - t_defaultdict) / t_counter * 100
   39
   print(f"--> defaultdict 比 Counter 快了 {speedup:.1f}%")

   1
   ========== 累加 (Accumulation) 性能对比 ==========
   2
   Counter 耗时:      1.3501 秒
   3
   defaultdict 耗时:  0.7618 秒
   4
   --> defaultdict 比 Counter 快了 43.6%

__getitem__

__getitem__的底层是C编写的，速度非常快。而lambda是Python级别的函数，速度会慢很多。

使用 lambda 时，Python 内部实际上是在做这样的事（伪代码）：

1
def process(i):
2
    return BYTE_TABLE[i]  # 这里有变量查找、下标访问等 Python 指令
3

4
for x in data:            # map 在 C 里循环
5
    process(x)            # 但每一轮都要调用这个 Python 函数

使用 __getitem__ 时，Python 内部是在做这样的事：

1
// C 语言伪代码
2
for (int i = 0; i < len(data); i++) {
3
    // 直接调用 C 指针，极快
4
    result[i] = PyTuple_GetItem(BYTE_TABLE, data[i]);
5
}

当你使用 map 进行优化时，千万不要塞进去一个 lambda。

• ❌ 慢：map(lambda x: x.upper(), my_list) -> 因为 lambda 是 Python 函数。
• ✅ 快：map(str.upper, my_list) -> 因为 str.upper 是 C 实现的方法。
• ❌ 慢：map(lambda x: lookup[x], my_list)
• ✅ 快：map(lookup.__getitem__, my_list)