Tensor Puzzles 记录

https://github.com/srush/Tensor-Puzzles

When learning a tensor programming language like PyTorch or Numpy it is tempting to rely on the standard library (or more honestly StackOverflow) to find a magic function for everything. But in practice, the tensor language is extremely expressive, and you can do most things from first principles and clever use of broadcasting.

This is a collection of 21 tensor puzzles. Like chess puzzles these are not meant to simulate the complexity of a real program, but to practice in a simplified environment. Each puzzle asks you to reimplement one function in the NumPy standard library without magic.

I recommend running in Colab. Click here and copy the notebook to get start.

!pip install -qqq torchtyping hypothesis pytest git+https://github.com/chalk-diagrams/chalk
!wget -q https://github.com/srush/Tensor-Puzzles/raw/main/lib.py
from lib import draw_examples, make_test, run_test
import torch
import numpy as np
from torchtyping import TensorType as TT
tensor = torch.tensor

Rules

  1. These puzzles are about broadcasting. Know this rule.
  2. Each puzzle needs to be solved in 1 line (<80 columns) of code.
  3. You are allowed @, arithmetic, comparison, shape, any indexing (e.g. a[:j], a[:, None], a[arange(10)]), and previous puzzle functions.
  4. You are not allowed anything else. No view, sum, take, squeeze, tensor.
  5. You can start with these two functions:
def arange(i: int):
    "Use this function to replace a for-loop."
    return torch.tensor(range(i))
def where(q, a, b):
    "Use this function to replace an if-statement."
    return (q * a) + (~q) * b

# In diagrams, orange is positive/True, white is zero/False, and blue is negative.

Puzzle 1 – ones

Compute ones – the vector of all ones.

def ones_spec(out):
    for i in range(len(out)):
        out[i] = 1
        
def ones(i: int) -> TT["i"]:
    # raise NotImplementedError
    return arange(i) * 0 + 1 

test_ones = make_test("one", ones, ones_spec, add_sizes=["i"])

这个TT["i"]中的"i"是一个类型注解,实际上不会被翻译成机器语言执行,但它是解释器可读的注释。当调用函数的__annotations__的时候会显示变量类型提示。

def ones(i: int) -> str:
    return "hi"

print(ones.__annotations__)
# {'i': <class 'int'>, 'return': <class 'str'>}

Puzzle 2 – sum

Compute sum – the sum of a vector.

def sum_spec(a, out):
    out[0] = 0
    for i in range(len(a)):
        out[0] += a[i]
        
def sum(a: TT["i"]) -> TT[1]:
    # raise NotImplementedError
    return (a * 0 + 1)[None, :] @ a


test_sum = make_test("sum", sum, sum_spec)

一个向量和同尺寸全1向量的点积得到的就是该向量的元素和

注意得到的结果是一个只有一个元素的向量而不是一个标量

[:, None]和[None, :] 是加轴操作,对于只有一个轴的向量,它的转置还是它自己。因为转置本质上是换轴。

torch.arange(5)        # shape (5,)   一维,横着的一串: [0, 1, 2, 3, 4]
torch.arange(5)[:, None]  # shape (5, 1)   竖起来了

索引语法 [:, None] 的含义:

  • : → “第一个轴原样保留”
  • None → “在这里插入一个大小为 1 的新轴”
  • None 就是 np.newaxis 的简写
写法结果解释
a * b(i,) 逐元素乘* 没有求和,也没有轴可撑网格
a @ b标量 = 内积@ 规则:1D 相遇 → 自动乘加缩并
a[:, None] * b[None, :](i, j) 外积网格* + 轴 → 广播撑出网格
a[:, None] @ b[None, :](i, j) 外积网格矩阵乘法

Puzzle 3 – outer

Compute outer – the outer product of two vectors.

def outer_spec(a, b, out):
    for i in range(len(out)):
        for j in range(len(out[0])):
            out[i][j] = a[i] * b[j]
            
def outer(a: TT["i"], b: TT["j"]) -> TT["i", "j"]:
    # raise NotImplementedError
    return a[:, None] @ b[None, :]
    
test_outer = make_test("outer", outer, outer_spec)

Puzzle 4 – diag

Compute diag – the diagonal vector of a square matrix.

def diag_spec(a, out):
    for i in range(len(a)):
        out[i] = a[i][i]
        
def diag(a: TT["i", "i"]) -> TT["i"]:
    # raise NotImplementedError
    return a[arange(a.shape[0]), arange(a.shape[0])]


test_diag = make_test("diag", diag, diag_spec)

这里要引入一个下标语法定义,同一个方括号里的下标列表默认按位置拉链配对,而不是取笛卡尔积。类似zip

写法下标数组形状结果
a[idx, idx](i,) + (i,)同位配对 → 对角线
a[idx[:, None], idx[None, :]](i,1) + (1,i)广播展开 → 全矩阵

广播展开由维度不一致来触发,因此下面这种情况下标会直接张成全位置矩阵,然后输出整个a矩阵

Puzzle 5 – eye

Compute eye – the identity matrix.

def eye_spec(out):
    for i in range(len(out)):
        out[i][i] = 1
        
def eye(j: int) -> TT["j", "j"]:
    # raise NotImplementedError
    return (arange(j)[:, None] == arange(j)[None, :]) * 1
    
test_eye = make_test("eye", eye, eye_spec, add_sizes=["j"])

矩阵逐位比较后将对应位置变成bool值True或者False,需要乘1才能变成数字矩阵。

在这里可以看出,比较和其他运算一样会触发广播

Puzzle 6 – triu

Compute triu – the upper triangular matrix.

def triu_spec(out):
    for i in range(len(out)):
        for j in range(len(out)):
            if i <= j:
                out[i][j] = 1
            else:
                out[i][j] = 0
                
def triu(j: int) -> TT["j", "j"]:
    # raise NotImplementedError
    return (arange(j)[:, None] <= arange(j)[None, :]) * 1

test_triu = make_test("triu", triu, triu_spec, add_sizes=["j"])

Puzzle 7 – cumsum

Compute cumsum – the cumulative sum.

def cumsum_spec(a, out):
    total = 0
    for i in range(len(out)):
        out[i] = total + a[i]
        total += a[i]

def cumsum(a: TT["i"]) -> TT["i"]:
    # raise NotImplementedError
    return a @ ((arange(len(a))[:, None] <= arange(len(a))[None, :]) * 1)

test_cumsum = make_test("cumsum", cumsum, cumsum_spec)

这里要实现一个累加功能,令向量矩阵乘一个上三角阵即可。

Puzzle 8 – diff

Compute diff – the running difference.

def diff_spec(a, out):
    out[0] = a[0]
    for i in range(1, len(out)):
        out[i] = a[i] - a[i - 1]

def diff(a: TT["i"], i: int) -> TT["i"]:
    return a - a @ ((arange(i)[:, None] == arange(i)[None, :] - 1) * 1)

test_diff = make_test("diff", diff, diff_spec, add_sizes=["i"])

计算差分需要构造一个差分矩阵,即一个单位阵减去一个超对角算子矩阵,对角线偏置随列向量数值增加向上移动

Puzzle 9 – vstack

Compute vstack – the matrix of two vectors

def vstack_spec(a, b, out):
    for i in range(len(out[0])):
        out[0][i] = a[i]
        out[1][i] = b[i]

def vstack(a: TT["i"], b: TT["i"]) -> TT[2, "i"]:
    # raise NotImplementedError
    return (arange(2) == 0)[:, None] * a + (arange(2) == 1)[:, None] * b


test_vstack = make_test("vstack", vstack, vstack_spec)

Puzzle 10 – roll

Compute roll – the vector shifted 1 circular position.

def roll_spec(a, out):
    for i in range(len(out)):
        if i + 1 < len(out):
            out[i] = a[i + 1]
        else:
            out[i] = a[i + 1 - len(out)]
            
def roll(a: TT["i"], i: int) -> TT["i"]:
    # raise NotImplementedError
    # return a @ (((arange(i)[:, None] - arange(i)[None, :] -1) % len(a) == 0) * 1 )
    return  a[(arange(i) - 1) % i]

test_roll = make_test("roll", roll, roll_spec, add_sizes=["i"])

这个题告诉我们不能老想着矩阵乘,构建下标列表更加方便

Puzzle 11 – flip

Compute flip – the reversed vector

def flip_spec(a, out):
    for i in range(len(out)):
        out[i] = a[len(out) - i - 1]
        
def flip(a: TT["i"], i: int) -> TT["i"]:
    # raise NotImplementedError
    # return a @ (((arange(len(a))[:, None] + arange(len(a))[None, :] ) == len(a)-1 ) * 1 )
    return a[i - 1 - arange(i)]
    

test_flip = make_test("flip", flip, flip_spec, add_sizes=["i"])

这个题再次告诉我们不能老想着矩阵乘,构建下标列表更加方便

Puzzle 12 – compress

Compute compress – keep only masked entries (left-aligned).

def compress_spec(g, v, out):
    j = 0
    for i in range(len(g)):
        if g[i]:
            out[j] = v[i]
            j += 1
            
def compress(g: TT["i", bool], v: TT["i"], i:int) -> TT["i"]:
    # raise NotImplementedError
    return (((cumsum(g * 1)-1)[None, :] == arange()[:, None])*g[None, :] *1) @ v


test_compress = make_test("compress", compress, compress_spec, add_sizes=["i"])

这一题就比较有趣了,我们需要将g向量中为True的位置对应的v中的同位置元素保留并向左对齐。

这要求我们记录一个True数量的信息。

这一题的启示是:倒着想应该会更加方便。

假设g=[T, F, T, F, T], v=[1, 2, 3, 4, 5], return : [1, 3 , 5, 0, 0]

那么我们需要一个这样的矩阵来完成运算

\left[
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5
\end{array}
\right]

\left[
\begin{array}{ccc}
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0& 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]

=
\left[
\begin{array}{ccc}
1 & 3 & 5 & 0 & 0
\end{array}
\right]

要构造这样的矩阵,我们需要记录True的数量然后和位置变量进行比较

\left[
\begin{array}{ccc}
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 2 \\
3 & 3 & 3 & 3 & 3 \\
\end{array}
\right]
==
\left[
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
\end{array}
\right]

=
\left[
\begin{array}{ccc}
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0& 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]

然后我们需要再mask掉False行

\left[
\begin{array}{ccc}
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0& 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]
*
\left[
\begin{array}{ccc}
1 & 1 & 1 & 1 & 1 \\
0 & 0 & 0& 0 & 0 \\
1 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 \\
\end{array}
\right]
=
\left[
\begin{array}{ccc}
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0& 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]

大功告成!

v @ ((cumsum(g*1)[:, None] == arange(i)[None, :]) * g[:, None] * 1)

Puzzle 13 – pad_to

Compute pad_to – eliminate or add 0s to change size of vector.

def pad_to_spec(a, out):
    for i in range(min(len(out), len(a))):
        out[i] = a[i]


def pad_to(a: TT["i"], i: int, j: int) -> TT["j"]:
    # raise NotImplementedError
    return a @ ((arange(i)[:, None] == arange(j)[None, :] ) *1)


test_pad_to = make_test("pad_to", pad_to, pad_to_spec, add_sizes=["i", "j"])

需要变更向量维度的时候找[i, j]形状的矩阵即可,保留主对角线为1即可

Puzzle 14 – sequence_mask

Compute sequence_mask – pad out to length per batch.

def sequence_mask_spec(values, length, out):
    for i in range(len(out)):
        for j in range(len(out[0])):
            if j < length[i]:
                out[i][j] = values[i][j]
            else:
                out[i][j] = 0
    
def sequence_mask(values: TT["i", "j"], length: TT["i", int]) -> TT["i", "j"]:
    # raise NotImplementedError
    return values * (arange(len(values[0]))[None, :] < length[:, None])


def constraint_set_length(d):
    d["length"] = d["length"] % d["values"].shape[1]
    return d


test_sequence = make_test("sequence_mask",
    sequence_mask, sequence_mask_spec, constraint=constraint_set_length
)

对每行进行一个length长度的截断,数乘一个mask矩阵即可

Puzzle 15 – bincount

Compute bincount – count number of times an entry was seen.

def bincount_spec(a, out):
    for i in range(len(a)):
        out[a[i]] += 1
        
def bincount(a: TT["i"], j: int) -> TT["j"]:
    # raise NotImplementedError
    return (a * 0 + 1) @ ((a[:, None] == arange(j)[None,:]) * 1)

def constraint_set_max(d):
    d["a"] = d["a"] % d["return"].shape[0]
    return d


test_bincount = make_test("bincount",
    bincount, bincount_spec, add_sizes=["j"], constraint=constraint_set_max
)

通过广播来将对应数字数量存到矩阵列中,然后用全一向量点乘即可。

仁慈的点是提供了数字上限

\left[
\begin{array}{ccc}
1 & 1 & 1 & 1 & 1 \\
2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 2 \\
3 & 3 & 3 & 3 & 3 \\
5 & 5 & 5 & 5 & 5 \\
\end{array}
\right]
==
\left[
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 4 & 5 \\
\end{array}
\right]

=
\left[
\begin{array}{ccc}
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0& 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 \\
\end{array}
\right]

Puzzle 16 – scatter_add

Compute scatter_add – add together values that link to the same location.

def scatter_add_spec(values, link, out):
    for j in range(len(values)):
        out[link[j]] += values[j]
        
def scatter_add(values: TT["i"], link: TT["i"], j: int) -> TT["j"]:
    # raise NotImplementedError
    return values @ ((link[:, None] == arange(j)[None, :]) * 1)

def constraint_set_max(d):
    d["link"] = d["link"] % d["return"].shape[0]
    return d


test_scatter_add = make_test("scatter_add",
    scatter_add, scatter_add_spec, add_sizes=["j"], constraint=constraint_set_max
)

其实就是统计out的每一个元素由values的哪几个元素相加得到,这个信息存在link里面。

所以计算link为列 与 位置为行的比较即可。

Puzzle 17 – flatten

Compute flatten

def flatten_spec(a, out):
    k = 0
    for i in range(len(a)):
        for j in range(len(a[0])):
            out[k] = a[i][j]
            k += 1

def flatten(a: TT["i", "j"], i:int, j:int) -> TT["i * j"]:
    # raise NotImplementedError
    return a[arange(i * j) // j, arange(i * j) % j]

test_flatten = make_test("flatten", flatten, flatten_spec, add_sizes=["i", "j"])

这个题再再次告诉我们不能老想着矩阵乘,构建下标列表更加方便

Puzzle 18 – linspace

Compute linspace

def linspace_spec(i, j, out):
    for k in range(len(out)):
        out[k] = float(i[0] + (j[0] - i[0]) * k / max(1, len(out) - 1))

def linspace(i: TT[1], j: TT[1], n: int) -> TT["n", float]:
    # raise NotImplementedError
    return i + (j - i) * (arange(n) / ((n - 1) + (n == 1)))


test_linspace = make_test("linspace", linspace, linspace_spec, add_sizes=["n"])

相等运算符的妙用,以兼容n为1 的边界条件。

Puzzle 19 – heaviside

Compute heaviside

def heaviside_spec(a, b, out):
    for k in range(len(out)):
        if a[k] == 0:
            out[k] = b[k]
        else:
            out[k] = int(a[k] > 0)

def heaviside(a: TT["i"], b: TT["i"]) -> TT["i"]:
    # raise NotImplementedError
    # return where(a == 0, b, where(a > 0, arange(len(a))*0+1, arange(len(a))*0 ))
    return (a == 0) * b + (a > 0) * 1

test_heaviside = make_test("heaviside", heaviside, heaviside_spec)

可以说是直接翻译了

Puzzle 20 – repeat (1d)

Compute repeat

def repeat_spec(a, d, out):
    for i in range(d[0]):
        for k in range(len(a)):
            out[i][k] = a[k]

def constraint_set(d):
    d["d"][0] = d["return"].shape[0]
    return d

            
def repeat(a: TT["i"], d: TT[1]) -> TT["d", "i"]:
    # raise NotImplementedError
    return a[None, :] * (arange(d[0])*0 +1)[:, None]

test_repeat = make_test("repeat", repeat, repeat_spec, constraint=constraint_set)

Puzzle 21 – bucketize

Compute bucketize

def bucketize_spec(v, boundaries, out):
    for i, val in enumerate(v):
        out[i] = 0
        for j in range(len(boundaries)-1):
            if val >= boundaries[j]:
                out[i] = j + 1
        if val >= boundaries[-1]:
            out[i] = len(boundaries)


def constraint_set(d):
    d["boundaries"] = np.abs(d["boundaries"]).cumsum()
    return d

            
def bucketize(v: TT["i"], boundaries: TT["j"]) -> TT["i"]:
    # raise NotImplementedError
    return ((v[:, None] >= boundaries[None, :]) * 1) @ ones(len(boundaries))

test_bucketize = make_test("bucketize", bucketize, bucketize_spec,
                           constraint=constraint_set)

“桶化”,将v中的元素分布到boundaries分割出的区间中。

小结

1. 制造:`arange(i) * 0 + 1` 造全 1(ones)

2. 定向:`[:, None]` / `[None, :]` 决定行/列方向(outer)

3. 缩并 vs 纯乘:`@` 带求和,`*` 不带(sum / outer / cumsum)

4. 条件:比较运算生成 mask(eye / triu / sequence_mask)

5. 编号:cumsum 当”位置变量”(compress / scatter_add)

6. 散开:one-hot 矩阵 `@` = scatter(compress / bincount / bucketize)

7. 挑选:张量当下标,拉链配对(diag / flatten / roll / flip)

Related Posts