当我们得到一个概率分布,如何根据这个概率分布抽样是一个常见的问题。这篇文章将介绍alias method(别名采样),这种算法的运行时间复杂度为O(1)的,当然提前需要复杂度为O(n)的预处理。下面我将通过一个例子介绍别名采样算法。

问题背景

  假设一共存在A,B,C,D四种情况,它们的概率分别为 0.3,0.1,0.1,0.5。如何实现按概率抽样呢?
  比较常用的一种方法是生成一个数组:1,2,2,3,3,3,4,4,4,4,其中1对应A,2对应B,以此类推。然后随机在数组中抽取一个即可。这种方法简单易实现,但是这是仅仅有4种情况时。当情况变多,这种方法就会占用很大的空间了,所以并不适用于大规模的通用情况。
  另外,可以根据它们的概率密度分布生成累积分布:0.3,0.4,0.5,1。然后生成一个0-1之间的随机数,看它落在哪个区间。然而,这时需要与临界点进行比较。我们知道,插入有序数列最好的时间复杂度为O(logn),所以这种方法复杂度较大。
  我们这篇文章提到的alias method可以实现以运行复杂度为O(1)的方式抽样。当然它需要预处理,预处理的时间复杂度为O(n),但是重复跑的时候,运行时间复杂度低才是重要的。

别名采样算法

  下面介绍alias method的处理过程。
  我们知道等概率分布抽样的时间复杂度为O(1),考虑一种情况,如果A,B,C,D概率分布均为0.25,那我们随机生成1,2,3,4,抽中哪个就是哪个,复杂度自然为O(1),这是等概率分布抽样的情况。
  我们知道二项不等概率分布抽样的时间复杂度也为O(1),如果只有两个变量,比如A,B概率分布为 0.2,0.8.那我们用累积分布的方法,小于0.2就是A, 大于就是B,只需比较一次,所以复杂度也是O(1),这是二项分布抽样的情况。
  alias method就是把这两种方法结合起来。
  仍然以本文一开始提出的例子为例。原来的概率分布如下,我们用绿色代表A,蓝色代表B,紫色代表C,橙色代表D:

首先我们把原概率分布乘以N(为后面的拼接做准备),这里是N=4。得到:1.2,0.4,0.4,2.0,如图所示。

  我们把它拼成等概率分布和二项不等概率分布:

  注意拼接的过程中,每一列最多有两种情况,这样才能让每一列都符合二项分布。
  做完以上处理后,我们就可以开始抽样了。首先我们以等概率分布抽一列,然后生成一个0-1之间的随机数。
  举例来说,例如我们首先抽中了第四列(概率为0.25)。然后在第四列中进行二项分布抽样,如果小于0.8,绿色,代表A,反之,就是橙色,代表D。这两个操作的复杂度均为O(1),故总时间复杂度也为O(1)。
  那么这样抽样是正确的吗?换句话说,在原概率分布中抽到A的概率是0.3,那使用alias方法抽到的概率还是0.3吗?
  我们仍然以抽取A情况为例。原来抽中a的概率为0.3。运用alias method方法后,抽中a的概率为抽中第一列+抽中第四列且随机数小于0.2,算起来为0.25+ 0.25 * 0.2) = 0.3,完全一样。

参考文献

1, http://blog.csdn.net/sky_zhe/article/details/10051967
2, https://www.cnblogs.com/zqiguoshang/p/5885455.html

网上有很多搭建ghost博客的教程,但是有的步骤不详细,也少有使用云数据库搭建的教程,基本都是本地数据库。这篇教程的目的就是想要教大家一步一步搭建ghost博客,同时把数据库放在腾讯云数据库上,不再使用本地数据库。

一、所需环境

华为云服务器(配置:内存2G,硬盘40G,操作系统Ubuntu 18.04)
腾讯云数据库(类型:MySQL,版本5.7)

二、详细步骤
1、安装GCC和G++

1.1、首先查看系统是否已经安装,使用如下命令:
gcc --version
g++ --version
如果正确显示版本则已经安装,直接进入下一步操作。否则,使用如下命令进行安装:

sudo apt-get install gcc
sudo apt-get install g++

1.2、如果没有安装开发编译工具包,则使用如下命令安装:

sudo apt-get install build-essential

2、安装Node.js

执行以下命令,安装Node.js

sudo curl -sL https://deb.nodesource.com/setup_10.x | sudo -E bash -
sudo apt-get install -y nodejs

3、安装nginx

3.1、输入以下命令安装Nginx。

sudo apt-get update
sudo apt-get install nginx

3.2、验证是否正确安装:
在浏览器中通过域名或者 IP 地址进行访问Nginx,如果Nginx正常启动则会打开Welcome to nginx的欢迎页面。
3.3、配置Nginx
新建配置文件
vim /etc/nginx/sites-available/ghost.conf
在配置文件中输入以下内容:

server {

listen 80;
server_name xx.xxx; #这里写自己的域名或者ip地址
location / {
    proxy_set_header   X-Real-IP $remote_addr;
    proxy_set_header   Host      $http_host;
    proxy_pass         http://127.0.0.1:2368;
}

}

3.4、把配置文件软链接到sites-enabled中:
sudo ln -s /etc/nginx/sites-available/ghost.conf /etc/nginx/sites-enabled/ghost.conf
3.5、重启Nginx
sudo service nginx restart

4、创建新用户

4.1、执行以下命令,创建新用户。
adduser 你的用户名
输入此命令后,会要求你输入密码,自己设置即可。
然后要求你输入一系列信息,我们直接按回车表示默认即可。
最后问你是否确认,输入y
4.2、执行以下命令,将新创建的用户添加到superuser组。
usermod -aG sudo 你刚才创建的用户名
4.3、执行以下命令,切换到你刚才创建的用户。
su 你刚才创建的用户名

5、安装Ghost-CLI

sudo npm i -g ghost-cli

6、安装Ghost

6.1、创建一个文件夹:
sudo mkdir -p /var/www/ghost
6.2、更改所有者:
sudo chown [user]:[user] /var/www/ghost
6.3、进入我们刚才创建的文件夹:
cd /var/www/ghost/
6.4、用Ghost-CLI 安装Ghost。
ghost install
接下来会提示我们没有找到本地数据库:

由于我们要使用云数据库,所以无需本地安装数据库,所以直接输入y,按下回车
接下会进行配置:
在配置数据库的时候,host填写云数据库地址,username填写云数据库用户名,表名填写事先在云数据库中创建好的表名。密码填写云数据库密码。如果你的云服务器和云数据库不在同一可用区之内,你需要使用外网地址,否则使用内网即可。
注意,有云数据库如何创建用户、创建数据库、内网外网是什么等基本概念,请参考腾讯云官方文档,或参考本站今后会推出的文章。
根据作者的实际经验,由于访问云数据库需要在地址后面加端口,而将地址:端口直接写在上面host中并不能让配置成功,需要单独使用vi config.production.json打开配置文件,在有关数据库的配置中加一项port,填写云数据库的端口。
如下所示:

7、开始配置用户

至此安装完成,访问http://你的IP或域名/ghost按系统说明配置即可