Like World

Like's blog

免费使用DigitalOcean上的虚拟机

0. 前提条件

自己是学生,具有edu.cn或edu的邮箱。如果没有的话,据说使用学生证也可。

1. DigitalOcean上VPS的作用

DigitalOcean就是卖虚拟机的,包括全球多个机房(如旧金山、纽约、新加坡等)。用户购买虚拟机可以干很多事情,包括但不限于:

  • 安装shadowsocks穿越防火长城GFW。从此,无障碍访问互联网;
  • 部署个人博客/网站;

2. 免费/低价使用的步骤

1) 获取Github Student Developer Pack

Github为学生提供了很多福利,包括100刀的DigitalOcean券,免费注册.me域名(一年)等等。

首先,访问https://education.github.com/pack,获取自己的pack(使用edu/edu.cn的邮箱)。

然后,在DigitalOcean那一项获得100刀的促销码。

2) 注册DigitalOcean账号

访问https://www.digitalocean.com/?refcode=65b0f33ddec8注册DigitalOcean账号。前面这个注册链接带了我的推荐小尾巴,使用我的推荐链接注册你可以额外获得10美刀。当然也可以直接搜索官网,然后注册。但是,不会有这10美刀。

注册完,在Billing页面输入刚刚获取的100刀促销码。此时,账号里已经有110刀(推荐链接送10刀 + 100刀促销码),但账号并没有激活。

3) 激活DigitalOcean账号

一共有两种方式,使用双币信用卡免费激活或者使用PayPal付5美元激活。如果使用信用卡,那么就可以免费激活账号(认证信用卡时会临时扣钱,但会退还)。后期只要账户里有余额,使用没超,就不会扣钱。我选择了使用PayPal付5美元注册。

访问https://www.paypal.com/c2/webapps/mpp/get-started注册PayPal账户,账户类型选“个人”。注册完以后就可以使用银联卡进行美元支付,跟平时使用支付宝一样一样的。但是需要注意的是不能使用中国银行的长城借记卡,PayPal会识别为Discover的一个卡。这是因为长城借记卡的卡号没有按照银联标准走。5美元约合人民币30元多一点点。

4) 购买虚拟机(Droplets)

可以在多个机房中选(我选了旧金山机房),也可以选择多个实例。如果选择最便宜的5美刀的实例,那么账户里100多刀就可以用20多个月。

我购买虚拟机后,目前只是安装了shadowsocks。看优土鳖,vimeo上的视频还是很流畅的,基本无卡顿(教育网)。从此,自由上网。

使用免费的Goagent自由上网存在一些安全风险,见:http://www.williamlong.info/archives/3882.html

Cc150总结-4. Trees and Graphs

基本纲领

树形结构的特征很明显:子树也是树(废话)…所以,首先要想到的解法就是递归。然后具体方法又分为自顶向下(Top-down)和自底向上(Bottom-up)。

图的算法就那么多吧…这章就一个图的题。

4.1 实现一个函数判断一个二叉树是不是平衡的。

  • 解法1:一个函数求树的高度,然后判断当前树是否平衡。如果平衡就判断子树是否平衡(Top-down)。这个解法的缺点是重复访问底层的节点。
  • 解法2:递归到最底层,然后从下往上计算各个节点的高度(不需要单独一个函数计算)。然后再从底向上判断树是否平衡(Bottom-up)。 优点就是每个节点只会访问一次。

代码在此

4.2 判断图中两个节点的连通性

可以使用BFS和DFS。代码在此

4.3 通过一个有序数组创建二叉搜索树,使得其高度最低(平衡二叉树吧)

方法很简单,选中间的节点作为根节点,然后使用前半段区间递归生成左子树,后半段区间生成右子树。代码在此

4.4 将树的每层节点串起来成D个链表,D是树的高度

这里显然要用到层次遍历。但是要稍微修改下传统的层次遍历。由于这里最终结果是D个链表,那么就不需要使用队列了。用链表模拟队列。同时维护两个链表。一个链表包含当前这层的节点,另一个链表包含下层节点。然后一层一层往下。将每层节点的链表直接添加到result中。代码在此

4.5 检查一个二叉树是否是二叉搜索树

  • 解法1:自顶向下,维护一对minVal和maxVal。只有当前节点的值在这个区间,才是二叉搜索树。
  • 解法2:使用二叉搜索树的特性。它的中序遍历必然是有序的。然后只需要一个变量指出它的前驱节点就好了(通过中序遍历)。当前节点需要大于(或等于)其前驱节点。

代码在此

4.6 需找二叉搜索树中一个节点的后继

后继就是:1)如果有右子树,那么右子树最左边的节点就是其后继。2)往父节点走,第一个右父节点(自己体会下右父节点的意思,第一个向右走的父节点)就是其后继。

代码在此

4.7 寻找两个节点第一个共同祖先,不使用某数据结构存放额外节点

情形一:节点中包含parent指针

书上描述的太复杂,实际上有个很简单的解法:把parent当做list的next指针。然后需要做的是:1)找到node1的root节点,并将他们连成一个环:root->parent = node1;2)现在问题就变成了node1和node2是否相交,如果相交,找出第一个相交节点。就是进入环的节点。解法就很简单了,list里做过的。完事后记得还原root->parent。

情形二:节点中不包含parent指针

  • 解法一:自顶向下。1)写个函数covers判断某树是否包含某节点); 2)判断左子树是否包含node1,右子树是否包含node2。如果是这样,那么root就是第一个祖先了;3)如果不是,那么遍历包含两个节点的子树。缺点就是重复访问底层节点。
  • 解法二:自底向上。我想的,跟书上不太一样。用一个元祖(p1, p2)维护包含(node1, node2)的祖先。从最底层开始(初始(null,null))。直到某个节点p1和p2都不再是nullptr。那么就找到第一个公共祖先了。

代码在此

4.8 两个二叉树:T1有百万节点,T2有数百个节点。判断T2是否是T1的子树(注意,中间那一部分是不能叫子树的)

  • 解法一:这是根据树的性质来的,如果是子树,T1那么两种遍历(前序+中序,其他也可以)产生的字符串里必然包含T2的遍历结果。这种方法快(O(m + n))。但是需要大量的空间(O(m + n))。
  • 解法二:自顶向下。写一个函数判断两棵树是否相同。然后依次判断T1是否和T2相同,T1的子树(左右)是否和T2相同。这种方法慢(最差O(mn)),但需要的空间小(递归产生的空间O(log(m) + log(n)))。
  • 解法三:有更好的解法么?题目强调了百万,就在想是不是有更好的解法。最开始想的是解法二,以为这是很笨的解法。结果答案里也是这解法…

代码在此

4.9 二叉树的节点包含一个数值,设计个算法,打印一条路径使得它的总和等于一个给定值。这条路径不需要从root开始或以leaf结束

  • 解法一:自顶向下。用数组维护自开始节点以来的路径,只要结果等于sum就打印路径,一直遍历到null。然后开始回溯,直到数组为空,然后设定子树的根节点为起始节点,重复操作。这个解法会重复访问底层节点。
  • 解法二:自顶向下。优化上面的解法,使得不需要重复遍历节点。使用数组维护自根节点到当前节点的path,然后在path里从后往前累加,只要累加值等于给定的值,就打印这个path。所有节点只需遍历一遍。

代码在此

总结

树的题目一般有两个解法:自顶向下和自底向上:

  • 自顶向下解法直观,但通常会重复访问底层的节点。
  • 自底向上需要维护额外的变量,用来纪录底部以来的状态。好处是通常只遍历每个节点一次。

LevelDB——Arena分析

Arena可以单次申请内存,但不能单次释放内存。只有当Arena析构时,才会释放所有申请的内存。另外,Arena允许浪费内存,所以整个Arena的实现就很简洁。

分配bytes大小的空间
1
2
3
4
5
6
7
8
9
10
inline char* Arena::Allocate(size_t bytes) {
  assert(bytes > 0);
  if (bytes <= alloc_bytes_remaining_) {  //如果有足够的剩余内存,就直接分配
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }
  return AllocateFallback(bytes);  //否则就从新分配的一块内存里分配
}
分配bytes大小的空间,返回的地址是内存对齐的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
char* Arena::AllocateAligned(size_t bytes) {
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8; //最小8字节对齐
  assert((align & (align-1)) == 0);   // Pointer size should be a power of 2
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1); //当前指针超出对齐边界的字节数
  size_t slop = (current_mod == 0 ? 0 : align - current_mod); //需要调整的字节数
  size_t needed = bytes + slop;
  char* result;
  if (needed <= alloc_bytes_remaining_) { //有足够的剩余内存,就直接分配
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  } else {
    // AllocateFallback always returned aligned memory
    result = AllocateFallback(bytes);  //否则就从新分配的一块内存里分配
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
  return result;
}
根据情况申请大块内存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static const int kBlockSize = 4096;

char* Arena::AllocateFallback(size_t bytes) {
  if (bytes > kBlockSize / 4) {  //申请大内存,就直接申请一块
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  //前面剩余的内存就浪费掉了
  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}
一次性分配block_bytes大小的空间
1
2
3
4
5
6
char* Arena::AllocateNewBlock(size_t block_bytes) {
  char* result = new char[block_bytes];
  blocks_memory_ += block_bytes;
  blocks_.push_back(result);
  return result;
}

求平方根算法

1. 牛顿法

先猜一个初值,然后依次迭代,直到结果足够精确。比如求number的平方根:

  • X0 = guess
  • X1 = (X0 + number / X0) / 2
  • X2 = (X1 + number / X1) / 2
  • ……
  • Xn = (Xn-1 + number / Xn-1) / 2

结束条件可以是 abs(Xn * Xn – number) 小于某个数,或者两次迭代结果 abs(Xn – Xn-1) 小于某个数.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cmath>
#include <limits>

using namespace std;

double sqrt_newton(double x)
{
    if (x <= 0)
        return x;

    double val = x, prev;

    do {
        prev = val;
        val = (prev + x / prev) / 2;
    } while(abs(val - prev) > numeric_limits<double>::epsilon());

    return val;
}

注意:上面这个代码不能使用第一个条件判断。因为此时求sqrt_newton(3)时,abs(val * val – x)最后一直是4.44089e-16,而numeric_limits::epsilon()是2.22045e-16。这样就导致了死循环。这应该是由于浮点数的精度问题导致的。 如果要使用第一个条件,可以用 abs(val * val – x) > 0.00000001。

2. 二分法

二分法就是每次取中间的值,然后比较。直到结果足够精确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
double sqrt_bi(double x)
{
    if (x <= 0)
        return x;

    double low = 0, high = x;
    double mid = (low + high) / 2, prev;

    do {
        if (mid * mid > x)
            high = mid;
        else
            low = mid;

        prev = mid;
        mid = low + (high - low) / 2;
    } while(abs(mid - prev) > numeric_limits<double>::epsilon());

    return mid;
}

3. 不知所云法

QUAKE-III里用来计算1/sqrt(x)的算法,速度快。 这里的float不能改成double,改成double就不对了。

还有个问题是,下面这个算法求出的结果精度会有点问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
float sqrt_magic(float x)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5;

    x2 = x * 0.5;
    y = x;
    i = * (long *) &y;
    i = 0x5f3759df - (i >> 1);
    y = * (float *) &i;
    y = y * (threehalfs - (x2 * y * y));
    y = y * (threehalfs - (x2 * y * y));

    return 1 / y;
}

补充知识:C++中的numeric_limits

numeric_limits定义于limits头文件中,主要用于取代C语言中limits.h中的那些宏。具体见它的参考页面

比如,

  • INT_MAX和INT_MIN使用numeric_limits<int>::max()和numeric_limits<int>::min()代替。

  • DBL_EPSILON使用numeric_limits<double>::epsilon()代替

References:

[1] 一个Sqrt函数引发的血案

[2] 维基百科-牛顿法

Cc150总结-1. Arrays and Strings

重点推荐1.8

1.1 查看字符串中的字符是否唯一的,如果不使用额外的数据结构怎么做?

A: 核心思路是记录每个字符出现的次数,如果某个字符出现第二次,就返回false。否则返回true。有下面3种解法,代码在此:

  • 最简单的方法是使用Hash表。
  • 因为字符最多只有256个,可以用一个包含256个元素的bool数组。
  • 使用位图,只需要256位,也就是大小为32的char数组。

1.2 实现void reverse(char *str)

A: 使用前后指针同时操作。但这个函数必须保证str是字符数组,而不能是字符串常量。比如reverse(“haha”)就会报段错误。正确的函数应该是返回一个指向reversed字符串的指针。代码在此

1.3 给定两个字符串,判定一个字符串是否是另一个字符串的排列

A:借用1.1的思路,使用包含256个元素的数组,统计两个字符串上的元素是否都一样。代码在此

1.4 写一个函数将所有的空格替换成%20

A:先统计有多少个空格,从字符串尾部开始将字符移动到正确位置,当遇到空格时,就使用%20替换。简单的题目要写出bug free的代码。代码在此

1.5 压缩字符串,如果压缩后的长度不比原来的字符串短,就返回原来的字符串。比如aabcccccaaa –> a2b1c5a3

A:基本思路就是查看邻近的字符,相同就增加计数,不同就添加到压缩串里。(这里要注意边界条件,比如最后一组等)代码在此

1.6 将N×N的矩阵顺时针旋转90度,最好在原地进行。

A:这道题的主要思路就是找到旋转时,4个点的关系。旋转是一层一层来,从最外层到最里层。可以通过实例来推导关系,比如一个4×4的矩阵:

  • (0, 0) –> (0, 3) –> (3, 3) –> (3, 0) –> (0, 0)
  • (0, 1) –> (1, 3) –> (3, 2) –> (2, 0) –> (0, 1)
  • (0, 2) –> (2, 3) –> (3, 1) –> (1, 0) –> (0, 2)
  • (1, 1) –> (1, 2) –> (2, 2) –> (2, 1) –> (1, 1)

总结关系如下:

  • i = (0, 1, …), j = (n – 1, n -2 , …), i < j。i最多只到一半的行,因为后半行已经旋转过了。j代表外面的层
  • k = (i, i + 1, …, j – 1)。k是每一行的元素。
  • l = n – k – 1。即l + k = n – 1。

通用关系如下(i, k) –> (k, j) –> (j, l) –> (l, i) –> (i, k)。有这个关系,代码就很简单了,在此

1.7 如果M×N矩阵中,有一个元素为0,那么就将该行该列都清0

A:书中的解法需要O(n)的空间,实际上解法可以优化到O(1)空间,即使用第0行和第0列来记录某一行某一列中是否有0.但是需要注意的是需要单独统计第0行或第0列中最开始时是否有0,这样需要清空第0行或第0列。如果不加以区别,会有额外的元素被清零。代码在此

1.8 给定两个字符串s1和s2,判断s2是否可以通过s1旋转而来(只使用一次isSubstring)。比如waterbottle是由erbottlewat旋转过来的。(重点推荐)

A: 这道题没想出只调用一次isSubstring的方法。。不过看了答案后,又学到一招。

常规方法是依次遍历s1,然后判断前后两部分是否都是s2的子串。但这需要调用太多次isSubstring了。

书上精妙的解法: 假设 s1 = xy, 如果s2由s1旋转而来,s2 = yx 那么两个s1拼接起来就是: s1s1 = xyxy,从这里可以看出s2是s1s1的子串。太妙了!!!代码在此

LevelDB安装及试玩

LevelDB的核心代码很短,1W行不到的样子。注释详细,可以用来学习C++在实际工程项目上的用法。

安装LevelDB

安装很简单,环境为Ubuntu 12.04

1
2
3
4
5
6
git clone https://code.google.com/p/leveldb/
cd leveldb
make
sudo cp -r include/leveldb /usr/local/include/
sudo cp -r libleveldb.so* /usr/local/lib/
sudo ldconfig

简单试用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "leveldb/db.h"
#include <iostream>

using namespace std;

int main()
{
  leveldb::DB *db;
  leveldb::Options option;

  option.create_if_missing = true;
  leveldb::DB::Open(option, "/tmp/leveldb_t", &db);

  string key = "Name";
  string value = "Like";
  db->Put(leveldb::WriteOptions(), key, value);

  key = "Major";
  value = "Computer Science and Technology";
  db->Put(leveldb::WriteOptions(), key, value);


  string ret_s;
  db->Get(leveldb::ReadOptions(), "Name", &ret_s);
  cout << "key = Name" << endl
       << "value = " << ret_s << endl;

  db->Get(leveldb::ReadOptions(), "Major", &ret_s);
  cout << "key = Major" << endl
       << "value = " << ret_s << endl;
  
  delete db;
  return 0;
}

编译运行也很简单:

1
2
g++ test.cpp -lleveldb
./a.out

References:

[1] Google LevelDB 試玩心得

使用Python画CDF图

依赖包:numpy, matplotlib, statsmodels

  • 可以使用sudo apt-get install python-numpy python-matplotlib安装前两个
  • ubuntu 12.04里没新版的statsmodels,使用pip安装。它依赖于pandas和patsy,都可以通过pip安装

实现代码借鉴于参考文献[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/env python
# encoding: utf-8

import numpy as np
import statsmodels.api as sm
import matplotlib.pyplot as plt
import sys


def cdf_plot(data, name, number):
    """
    data: 一组数据
    name: 在legend上显示的名称
    number: 数据最大最小值之间划分多少段
    """
    ecdf = sm.distributions.ECDF(data)
    x = np.linspace(min(data), max(data), number)
    y = ecdf(x)

    #plt.step(x, y, label=name)
    plt.plot(x, y, label=name)


def main():
    for f in sys.argv[1:]:
        data = open(f).readlines()
        data = map(float, data)
        cdf_plot(data, f, 100)

    #plt.xscale('log')
    plt.legend(bbox_to_anchor=(0.65, 0.3), loc=2, borderaxespad=0.)
    plt.show() #显示CDF图

if __name__ == '__main__':
    main()

将代码保存为cdf.py,即可运行。后面跟几个文件,每个文件全是数据

1
./cdf.py data1 data2 data3

References

[1] How to plot empirical cdf in matplotlib in Python?

Hello World

1
2
3
4
5
6
7
#include <stdio.h>

int main()
{
  printf("Hello World!\n");
  return 0;
}