&#65279 引发奇怪的空白

使用 Visual studio 编辑 html 时,发现页面上会出现奇怪的、CSS 无法消除的空白。在折腾了几个小时后,我发现浏览器查看元素时会有一些“&#65279”。

这些字符就是所谓的字节顺序标记(byte order marks,BOMs),这个字符是“零宽度不换行空格”。这种东西在 VS 编辑器中完全不可见(在 Word 里面打开显示隐藏标记的话会显示)。如果在 Word 里面替换的话,可以用 ^u8520 替换掉。

Visual Studio 在保存 UTF-8 文件时默认是 “with signature” 的,这就会保存 BOM 字符。

解决方法就是在 VS 中保存时选择编码 “UTF-8 without signature”。

塞德里克·维拉尼教授访谈录

塞德里克·维拉尼(Cédric Villani),法国数学家,现任法国庞加莱研究所所长,法兰西科学院院士,在数理物理学(朗道阻尼和玻尔兹曼方程)、最优输运理论和黎曼几何领域做出了重大贡献。2009年获得费马奖,2010年获得菲尔兹奖。维拉尼教授以日记形式在《一个定理的诞生》一书中再现了这段研究生涯,揭示了一个数学定理的诞生历程。

四月九日,借塞德里克·维拉尼教授访华之机,我们代表“图灵访谈”节目,对维拉尼教授进行了专访。

IMG_4029s P1060885ss

Continue reading “塞德里克·维拉尼教授访谈录”

遇到了BAD_SYSTEM_CONFIG_INFO咋整

Windows 10,用着用着就蓝屏了。BAD_SYSTEM_CONFIG_INFO,安全模式也进不去,自动修复也没有用。

按照某软的说法,”This bug check indicates that there is an error in the registry.”

解决办法是

  1. Try restarting the computer by selecting “last known good configuration” in the boot options.
  2. If the restart does not fix the problem, the registry damage is too extensive. You must reinstall the OS or use the Emergency Repair Disk (ERD) that you previously created by using the Windows Backup tool.

真是呵呵了。不过这至少还告诉我是注册表坏了。于是重启进命令行,注册表在 D:\Windows\System32\config。这里面有个隐藏文件夹叫做 RegBack,是注册表的近期的备份。我把现有的注册表又备份了一次,把这个备份拷贝出来覆盖掉 D:\Windows\System32\config 里面的。重启,搞定。

正态分布随机数的生成 (2)

没有看过上一篇的同学请看正态分布随机数的生成 (1)

接受—拒绝法

求反变换固然还可行,但是碰到无法解析求逆的函数,用数值方法总归比较慢。下面我们就来说说另一个能够适合任何概率密度分布的方法——接受—拒绝法 (Acceptance-Rejection Method),国内也有翻译成叫做舍选法的。接受—拒绝法的思路其实很简单——比如说你想要正态分布,我们就弄个方框框把它框起来,然后均匀地往里面扔飞镖。扔到曲线以下我就留着,扔到曲线以上就不要了。这样搞好以后来看,曲线之下的点就是(二维)均匀分布的。那这些点的横坐标就正好满足我们要的分布——高的地方的点就多,低的地方的点就少嘛。

accept-rejection

Continue reading “正态分布随机数的生成 (2)”

正态分布随机数的生成 (1)

正态分布——听起来非常耳熟,用起来也很顺手——因为很多语言都已经内置了有关正态分布的各种工具。但其实,在这个最普遍、最广泛的正态分布背后,要生成它还有很多学问呢。

$$f(x \; | \; \mu, \sigma) = \frac{1}{\sigma\sqrt{2\pi} } \; e^{ -\frac{(x-\mu)^2}{2\sigma^2} }$$
normal

难道教科书上没有讲吗?看看概率书上是怎么说的……比如我手头这本浙大版的《概率论与数理统计》(第四版)第 378 页上说……“标准正态变量的分布函数 $\Phi(x)$ 的反函数不存在显式,故不能用逆变换法产生标准正态变量……”
Continue reading “正态分布随机数的生成 (1)”

蓄水池抽样浅说 (3)

加个权吧

前面说的是均匀抽样,要是想加个权怎么办呢?先说加权有什么用呢?比如我们已经统计好了搜索的关键字和词频,那么有了加权就可以直接用这个数据来抽样而无需把关键字重复好多遍了。

我们先来看看这个抽样应该是怎么样的。假设这总共 $n$ 项都摆在你面前了,设第 $i$ 项的权值为 $w_i$,那么我们抽到这一项概率应该是

$$P_i = \frac{w_i}{w_1 + w_2 + \cdots + w_n}$$

我们现在来看看,如果把这 $n$ 项按照第 $n$ 项、第 $n-1$ 项、…… 第 $2$ 项、第 $1$ 项的顺序抽出来,这个概率是多少。因为这 $n$ 项的顺序是可以随便摆的,所以它求出来是有一定普遍意义的。

第一次抽出第 $n$ 项的概率是

$$P_n(1) = \frac{w_n}{w_1 + w_2 + \cdots + w_n}$$

第 $n$ 项已经被抽走了,那第二次抽到第 $n-1$ 项的概率是

$$P_{n-1}(2) = \frac{w_{n-1}}{w_1 + w_2 + \cdots + w_{n-1}}$$

以此类推,按照这个顺序抽出所有元素的概率就是

$$P(S) = \prod_{i=1}^n \frac{w_i}{w_1+w_2+\cdots w_i} $$

这有什么用呢?别着急,先记下这个结果,我们下面来说说算法怎么做。

Continue reading “蓄水池抽样浅说 (3)”

蓄水池抽样浅说 (2)

没有看过前一篇的同学请看这里:蓄水池抽样浅说 (1)

跳跳跳!—— Algorithm X

前面介绍的方法都很好,但是要计算 $n-k$ 个随机数实在是有点浪费时间…… 有兴趣的同学可以把那个调用函数换成比如 reservoirSample(range(10**8), 10**5),就知道这东西还是要算上一会儿的了。

再来看看这个过程吧——把前 $k$ 个元素放进去之后,随机决定接下来的元素要不要放进去,但是每次决定时都需要产生一个随机数。要是我们能够确定应该跳过多少个元素,不就可以省掉很多生成随机数的工夫了吗?每一步过程就变成了

  • 确定该跳过多少个元素 $S(k, n)$
  • 跳过 $S(k, n)$ 个元素
  • 从前 $k$ 个元素中随机产生一个要替换的元素,用下一个元素替换

Continue reading “蓄水池抽样浅说 (2)”

蓄水池抽样浅说 (1)

jar_of_marbles

我们有时候会有进行数据抽样的需要,比如要从文件中随机取出若干行,或从数据集中随机取出若干数据进行分析。通常情况下这并不是什么难事,比如 Python 中直接提供了 random.sample() 来做这件事,Numpy 中更提供了功能更为强大的 numpy.random.choice()。然而这些东西都有一个问题,就是你必须把整个数据集读到内存里。如果数据集超出了内存的限制,或者要对一个持续的输入流做抽样,即从包含 $n$ 个项目的集合中(等概率)选取 $k$ 个样本,其中 $n$ 为很大或未知,又该怎么做呢?

Continue reading “蓄水池抽样浅说 (1)”

素数求和的动态规划方法

怎么求出从 $2$ 到 $N$ 之间的所有素数之和?

素数求和是数论中一个很典型的问题。这事情乍听起来并不难,只要把素数都求出来再加起来就好了嘛。可能你已经了解了一些求素数的方法,比如最简单的试除。写过这个程序的同学都知道这样搞有多慢。或者常用的是埃氏筛法,简单来说,就是列好从 $2$ 到 $N$ 的范围,先用 $2$ 去筛,把从 $2 \times 2$ 开始的 2 的倍数剔掉;再用下一个素数 3 筛,把 $3 \times 3$ 开始的 3 的倍数剔除掉…… 一直筛完不大于 $\sqrt{N}$ 所有素数为止。我直接从 wiki 上借了一个动画来演示这个过程,有兴趣的同学可以自己写一个试试看。

Sieve_of_Eratosthenes_animation

本文中的方法来自于解决了 ProjectEuler 全部问题的大神 Lucy_Hedgehog。
Continue reading “素数求和的动态规划方法”