最近刷 leetcode 952 题，第一次知道并查集这个数据结构，来记录一下。 什么时候使用并查集？ 当有许多节点在一起，你想要找到某一点以及和这一点相连以及间接相连的所有的点的时候，并查集就是最佳的数据结构之一。假设我们有下面这个图： 123456789101112graph = { 1: [], 2: [1], 3: [2], 4: [2, 3], 9: [6, 7], 5: [9], 6: [], 7: [5], 8: [5, 6, 9]} 很容易看出：1, 2, 3, 4 是相连的；5, 6, 7, 8 ...

前缀和是一种很常见的数据结构，在 leetcode 上面也有相应的题目，如（523，1292）。我们利用前缀和可以很容易快速的求出一块区域的值。我们分一维数组的前缀和和二维数组的前缀和来介绍。 一维数组的前缀和 在一维数组中，某一点的前缀和表示从数组的起始点到这一点的所有元素加在一起的值。如下例： 12a = [6, 3, 7, 2, 4]prefix_sum = [6, 9, 16, 18, 22] 利用前缀我们可以很快的算出 a[1:3] 的大小为 prefix_sum[3 - 1] - prefix_sum[1 - 1] = 10。很容易看出公式为 a[i: j] = prefi ...

embedding layer 网上个个都将的神乎其神，其本质上就是一个转换。将某一维度的向量转化到另一个维度。看到转换这两个字，很容易想到矩阵相乘。实际上大多数的 embedding layer 就是调用了一下 linear layer。 背景 在 NLP 中，如果用一个数字代表一个汉字，对于某一个待定的汉字，就要用一个非常稀疏的向量来表示它。假设有5000个汉字，那么标识一个汉字要用的向量就是一个5000x1的向量，其中有4999个为0，1个为1。这种方法叫做 one-hot。很明显，这样子效率很低，所以有人想出了这样一个办法，不再用一个数字表示一个汉字，而是使用一组数字来表示这个汉字 ...

简介 最近我发现几乎在每一个 neural network architecture 中，它们 fc 层后面都会跟着一个 ReLU 层，但是我一直不知道为什么要加一个 ReLU。只记得 CS231n 里面说过 in practice，每个 fc 层后面都会加一个 ReLU 层，今天我就抽空好好地研究了一下其中的原理。 整个文章分两部分： 1. 为什么要使用 activation function? 2. 为什么要使用 ReLU? 为什么要使用 activation function? 想要说明这一点，可以通过比较含有 activation function 的架构和不含有 activa ...

什么是 affine function ? 和 linear function 有什么不同？ 两者的公式定义不同： affine function 的定义： \(f(X)=Ax+b\)，其中A为非 0 向量。 linear function 的定义： \(f(X)=Ax\)，其中A为非 0 向量。 可以看出，linear function 是 affine function 的 \(b=0\) 的一种特殊情形。 问题设定 已知误差\(e\)（标量），有函数 \(Y=f(Q)\)，且 \(\frac{\partial e}{\partial Q}\) 是一个 \((2,4)\ ...

什么是 SVM loss vectorized SVM loss vectorized 即用 vector 的方式来计算 SVM 的 loss function. SVM loss function 的原理并不难理解，直接用循环实现也很简单。但是因为 Numpy 的底层做了优化，所以使用矩阵运算会比使用循环快得多。而这对于不熟悉 Numpy 的人来说，写起来有不小的压力。所以本文将详尽的对实现代码进行分析，包括整体计算思路，每一个函数的作用和每一步以后变量的变化。 准备工作 本文聚焦于 Multiclass Support Vector Machine Loss，首先简要的介绍下什么是 ...

大致思路 DFS: 首先访问一个节点，然后访问他的邻居，再访问邻居的邻居......如果再某一次访问的路径中，访问到了之前已经访问过的节点，则表示有环。如果全部遍历完以后，未遍历到之前访问过的节点，则表示无环。 实现技巧 算法理解起来并不难，不过实现起来有一些小技巧。 设置visited变量，存储之前总体访问情况。visited变量存储的应该是之前访问过，且它和它的邻居不存在环的变量。不能用这个变量来判断是否存在环，否则实现起来会有混乱。 设置path变量，记录当前此次路径中的访问情况。我们应该用这个变量来判断是否存在环。注意，因为判断的是当前路径，所以每次对于新路径要进行重置， ...

作为一个编程新手，长期以来，我一直对于 exception 和 if 充满了疑惑，不知道为什么要使用 exception，而我是从 C 语言开始学习，对于 exception 本生了解就不深。最近在一些实战和思考中对于 exception 有了一些自己的感悟，简单的记录一下。 为什么要使用exception？ 有一点很明确的，从我第一天学习编程的时候老师就提到过的：任何一门编程语言，只要含有顺序、选择和循环三种结构就能在理论上写出任何程序。那为什么还要exception呢？答案很简单，为了写代码时更爽，写出的代码更加优雅。 一个例子 假设我正在给我的朋友们写一个库，作用是将一个文件中的 ...