Interview

Algorithm

不同的二叉搜索树

https://leetcode.cn/problems/unique-binary-search-trees/description/

Design

1. 手写cross entropy与softmax优化

原生softmax很容易溢出，需要使用一些优化操作减少对数和指数的计算。

import torch
import torch.nn.functional as F
b, c = 2, 8

z = torch.randn(b, c) * 1000
y = torch.randint(0, c, (b, )).long()

def cross_entropy_with_logits1(z, y):
    p = torch.exp(z) / torch.exp(z).sum(dim=-1, keepdim=True)
    print(p)
    loss = (- y * torch.log(p)).sum(dim=-1)
    return loss

def cross_entropy_with_logits2(z, y):
    z = z - torch.max(z, dim=-1, keepdim=True).values
    p = torch.exp(z) / torch.exp(z).sum(dim=-1, keepdim=True)
    print(p)
    loss = (- y * torch.log(p)).sum(dim=-1)
    return loss

def cross_entropy_with_logits3(z, y):
    z = z - torch.max(z, dim=-1, keepdim=True).values
    loss = (- y * (z-torch.log(torch.exp(z).sum(dim=-1, keepdim=True)))).sum(dim=-1)
    return loss
print(cross_entropy_with_logits1(z, F.one_hot(y, num_classes=c)))
print(cross_entropy_with_logits2(z, F.one_hot(y, num_classes=c)))
print(cross_entropy_with_logits3(z, F.one_hot(y, num_classes=c)))
print(F.cross_entropy(z, y, reduction="none"))

Reference:

• 有效防止softmax计算时上溢出（overflow）和下溢出（underflow）的方法

2. 自动微分计算图设计

pass

3. 大文件中位数

基数排序