Rust 基本语法：

变量绑定

Rust一个明显的特征是默认变量是绑定切不可修改的：

1
2
3

fn main(){
	let x = 5;
}

let被用来声明一个绑定，x于数值5绑定起来

模式

Rust的let比一般语言的声明前缀更加强大，它的左边可以是一个模式：

1

let (x,y) = (1,2);

类型注解

Rust依然是静态类型语言，意味着任何声明的类型在编译期就应该明确，之前我们并没有加类型声明是因为Rust有类型推断的功能。

1

let x: i32 = 5;

完整的Rust system type可以在这里找到

可变性

Rust绑定默认是不可变的，这有别于传统的C++/python之类的语言，如果我们声明了一个绑定并在之后试图修改：

1
2

let x = 5;
x = 10;

编译器就会报错。这个feature确保了Rust的安全性。如果我们希望声明一个可修改的变量，需要使用mut关键字：

1
2

let mut x = 5;
x = 10;

这个feature看起来有点像C++里的const,但它比const更加安全，在C++中如果我们声明了一个const对象，直接对其修改时会报错的，这是const的性质所决定的。但是如果我们声明了一个non-const指针并将其指向这个const值，我们便可以通过修改指针来改变这个const value. 这是一个C++常见但不太好debug的bug.

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment

学习python pandas库的最佳方法是通过解决一个个问题学习

How to read a tabular data file into pandas

将表格型数据文件(excel, csv…)读入pandas十分简单
因为大家没有现成的数据文件，我们用一个URL代替，没错，pandas.read_table可以传入一个URL, 确认你可以访问到这个地址，大陆需要自备梯子

1
2

import pandas as pd
pd.read_table('http://bit.ly/chiporders')

read_table默认数据是用tab分割的，如果数据使用其它符号分割（比如’|’）

1
2
3

import pandas as pd
user_headers = ['use_id','age','gender','occupation','zip_code']
pd.read_table('http://bit.ly/movieusers', sep='|', header=None, names=user_headers)

在上面这个代码片段中我们从http://bit.ly/movieusers这个URL导入了数据，但是数据是用’|’分割的，因此我们要声明seperator:sep='|', header=None, names=user_headers则告诉python第一行的数据不是header,将其忽略并换上自定义的header user_headers
read_tables有大量的控制参数，可以参考官网的定义

How to select a pandas series from a DataFrame

实验代码：这个URL记录了历史上目击UFO的相关数据

1
2
3
4
5
6
7
8
9
10
11

import pandas as pd
ufo = pd.read_csv('http://bit.ly/uforeports')
type(ufo)

ufo.head()
ufo['City']
type(ufo['City'])

ufo.City

ufo['Location'] = ufo.City + ', ' + ufo.State

read_csv函数与read_table几乎一样，唯一一点不同的是read_csv使用,作为默认seperator
ufo.head() 显示ufo数据的前5行
pandas会自动将frame的series转换成frame的方法，因此ufo['City'] == ufo.City，但是方法有一些局限性
ufo['Location'] = ufo.City + ', ' + ufo.State: 创建一个新的series location, 是原来两个series的组合

前言

费了很大劲配置好了Jekyll + Gitblog，却不知道写些什么，正好前几天Parallel Computer System的课程刚刚结束，趁着还有印象把自己准备的Presentation总结一下。

过程式编程的流程

先看一下经典的快速排序的C++实现：

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

int partition(vector<int> &nums, int p, int r)
{
	int x = nums[r];
	int i = p - 1;
	for (int j = p; j < r; ++j)
	{
		if (nums[j] <= x)
		{
			swap(nums[++i], nums[j]);
		}
	}
	swap(nums[++i], nums[r]);
	return i;
}

void quick_sort(vector<int> &nums, int p, int r)
{
	if (p < r)
	{
		int q = partition(nums, p, r);
		quick_sort(nums, p, q - 1); 
		quick_sort(nums, q + 1, r);
	}
}

其中quick_sort函数中partition函数必须先执行，之后的两个quick_sort函数可以并行执行。快速排序的原理很简单：随机选择数组中一个数，将数组分成两部分，一部分所有元素小于等于该数，另一部分所有元素大于该数；对两个数组递归调用快速排序，之后将整个数组整合起来。

从定义上也可以看出：快速排序中拆分数组必须先执行，之后的排序是不相关的。算法的定义决定了算法的并行方式，从人的角度来说，我们可以很快从快速排序的描述中定义并行方式，但是如果是从算法或代码的角度观察，并行性会变得十分隐蔽。

什么决定了算法并行性？

• 数据依赖性(Data Dependency)
  从本质上来说，算法中的数据依赖性制约了并行化，快排中的两个子快排的对象是由partition函数产生的，因而必须等数组拆分完才能调用。另一个例子是归并排序(merge sort)，由于归并的必须是两个排好序的数组，所以归并排序的并行优化是“先并行，后顺序”。

• 变量修改(Variable Modification)
  数据依赖性导致了算法并行极限。在代码中数据依赖体现在函数共享变量或内存地址，然而由于程序员的编程习惯，很多可以实现并行的算法由于共享变量等原因而无法并行执行，这导致了代码并行优化的复杂度提升。

Sequencial Programming Parallelism常用技术与局限

为了解决数据依赖与共享内存缺陷，人们引入了Mutex, Semaphore, Locks, Synchronization等技术，使得过程式编程并行化变得十分复杂。很多介绍并行化编程的书有几乎一大半的篇幅被用于介绍同步，消息互锁等概念，由此可以看出并行化编程之复杂。

从本质上讲，这种复杂性源自于过程式编程的数学模型：图灵机，图灵机简单来说包括一个写着0-1字符的纸带与可以读取纸带的机器，这个机器可以读取，修改纸带上的字符，移动到纸带的任意位置，从而实现各种运算。从定义上来说，图灵机是顺序式执行的设备，机器必须根据当前读取到的字符进行下一步的执行，这种执行方式导致了Data Dependency十分明显。那么问题来了：是否有另外一种模型没有那么严重的Data Dependency Issue?

函数式编程(Functional Programming)

接着上面的问题，那么究竟有没有这种模型？ 答案是有的，有一种数学模型天生适合做并行化，叫做Lambda表达式。这个数学模型后来在计算机领域衍生成另外一种编程范式，称为函数式编程(Functional Programming)。

首先区分几个概念：

1. Lambda表达式与图灵机是两种数学模型，其中Lambda表达式已经证明是Turing Complete的，意味着Lambda表达式可以模拟图灵机的全部运算。
2. 过程式编程(Sequencial Programming)与函数式编程(Functional Programming)是两种编程范式，分别源自于图灵机与Lambda表达式两种数学模型
3. 编程语言： 不同的编程语言支持不同的编程范式，这也是有各种各样的编程语言的原因之一。过程式编程的代表语言有汇编，B, C；函数式编程的代表语言有Haskell, Scala, Lisp等。当然现代编程语言会支持多种编程范式，C++, Python, Javascript等就支持以上两种编程范式，但是它们又有不同的侧重，这里就不详谈了。

另外，本文章将使用Haskell作为函数式编程实例语言，一方面是因为Haskell是纯函数式编程语言，其内部实现严格遵循了Lambda表达式的演算方式，另一方面作者认为Haskell是一门逼格很高的语言……嗯。

继续看快速排序

回顾一下Quick Sort的表述：随机选择数组中一个数，将数组分成两部分，一部分所有元素小于等于该数，另一部分所有元素大于该数；对两个数组递归调用快速排序，之后将整个数组整合起来。

我们可以换一种表述：
1.Quick Sort是一个函数，这个函数接受一个数组，输出一个排好序的数组
2.Quick Sort (array)= array1 ++ a ++ array2
a: array的第一个元素
array1: Quick Sort [array中所有小于a的元素组成的数组]
array2: Quick Sort [array中所有大于等于a的元素组成的数组]

我们可以看出两种表述方式很相近，第二种表述方式描述了快速排序作为一个函数的行为。

让我们看一下Haskell表示的快排：

1
2
3

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Bang!就是这么简单!

稍微解释一下：
第一句表示如果传入一个空数组，那么就直接输出，这是coner case
第二句描述了整个快排，filter是一个高阶函数，filter (< x) xs表示将数组xs中小于x的数保留，其他删除。

可以看出Haskell版本的Quick Sort基本上就是第二种表述的翻版，这表示相比起C++的版本，Haskell版快排的可读性更加友好。更重要的是我们可以很快发现并行性：
qsort (filter (< x) xs), [x]与qsort (filter (>= x) xs)作为级联关系是可以并行的，不能并行的数组拆分与排序在代码中变成了函数嵌套，这是很重要的特性！在后面我会仔细解释。

万物皆是函数

在函数式编程中，函数是一等公民，一切都可以用函数表示，这里的函数已经不仅仅局限于我们所理解的函数，而是一种映射关系。再看看Haskell版本的快速排序，你能识别出多少函数？

• qsort: 主函数，输入一个数组，输出一个数组
• (=x): 判断大小函数，输入一个数字，将其与x比大小，输出Bool值
• filter: 之前已经说明，是一个高阶函数，输入一个函数与一个数组，输出一个数组
• (++): 嗯，也是函数，输入两个数组，输出一个数组(级联)
• ([]): 。。。也是函数，或确切的说是一个Monad，输入一堆数，将他们打包(wapped)成数组

从这里我们可以大概感受到函数式编程中“万物皆是函数”的定义，从Lambda表达式的角度来说，常量，符号，数字等都是函数，在这里我不准备详谈，有机会另写。

正题：函数式编程的并行化优势

优势一：引用透明(Referential transparency)

引用透明是纯函数(Pure Function)的特性之一，纯函数源自于数学上对于函数的定义：函数的输出仅取决于其输入。或是我们常用的公式定义：y=f(x)。
相比于数学上的函数，程序中的函数更像是过程(procedure)。对与C++来说，观察一下下面3种函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int f1(int x)
{
	x = x + 1;
	return 10;
}

int f2(int & x)
{
	x = x + 1;
	return 10;
}

int f3(int * x)
{
	*x = *x + 1;
	return 10;
}

3种函数从返回值上来说，都做了一样的事：返回常量10。此外，3种函数还做了另外一件事：将传入的参数+1，其中参数传入方式分别是值传递，引用传递，指针传递。效果也是十分明显的，如果分别执行完这三种函数后我们继续打印x的值得话，可以发现：f1中的x没变，而f2``f3函数将x的值+1了，换句话说，f2``f3函数除了返回一个常量，还做了其它行为，修改了一些“外部”状态。这种现象称为函数的“副作用”。

对于编程来说，函数的副作用有很多种，比如全局变量，引用传递，IO操作等。现在我们再重新定义一下纯函数，纯函数具有如下特征：

1. 函数如果传入相同参数，返回值不变
2. 函数不会产生副作用

举个例子，sqrt(x)是一个纯函数，launch_nuclear_missile()是一个有很大副作用的函数(╯-╰)

从定义上看纯函数是有很多优点的，其中最重要的是：纯函数没有状态(state)，意味着纯函数是“线程安全的”，因而不需要进行同步。当然其缺点也很明显：没有什么卵用!=_=, 我们仔细想一想，大部分编程活动是需要副作用的，比如我们要把数据打印到屏幕上的，进程之间是需要进行通讯的，等等等等。那么有什么解决方法？很简单，只要将算法中需要副作用的部分分离开就可以了。

传统数据结构的“副作用”

过程式编程有很多经典的数据结构，现在我们从纯函数的角度出发，看看哪些行为是有副作用的：

数据结构是算法的基础，人们设计这些数据结构本身是为了优化一些带有副作用的行为的，这些行为优化了算法复杂度，但也由于引入复杂度而导致并行复杂化。
大部分函数式编程采用最原始的数组为核心数据对象，当然函数式编程也是有自己的数据结构的，比如说Functional Programming领域中近似于“算法导论”存在的论文Pure Functional Data Structures，建议所有对函数式编程感兴趣的人读一下。

优势二：类型抽象 Abstraction Hierarchy

Haskell强大的类型抽象从一定程度上剥离了算法问题的关联性，其中的typeclass, functor,applicative,monad一步一步提高了问题的抽象，同时也削弱的Data Dependency的问题，首先推荐一下国外大神的文章，Functors, Applicatives, And Monads In Pictures，文章通过漫画生动地展示了它们的关系，我准备将这一篇文章翻译一遍。

优势三：惰性求值 (Haskell 独有)

优势四：Lambda演算的并行优势(以后有机会再写。。。)

前几天接触了前一阵大火的Rust，作为未来最有可能替代C++位置的语言，了解一下也是很有必要的。
初接触时，感觉Rust是C++, Python, Haskell的综合体，比如指针，切片，模式匹配等等。根据官方宣传，Rust作为一门系统编程语言，它尤其注重安全，速度和并发性，这也是我比较感兴趣的部分。

基本配置

以后再写。。。

Hello, world!

1
2
3

fn main(){
    println!("Hello, world");
}

需要注意的几点：

1. 在main函数中，缩进是4个空格，不是制表符
2. println!()是一个Rust宏，使用!表示，这是与函数不同的地方

运行程序：

1
2

$ rustc main.rs
$ ./main

转换到Cargo

Cargo是Rust的项目管理工具，Cargo的一个比较人性化的地方是它可以帮助我们自动管理程序依赖的库文件，这是非常重要的。
基本命令：

开启一个新项目：

1

$ cargo new hello_world --bin

--bin参数表明这个项目的目标是一个可执行程序。Cargo会创建两个文件和一个目录：Cargo.toml和包含了main.rs文件的src目录。Cargo.toml负责管理项目的依赖库以及相关配置

编译运行项目：

1
2

$ cargo build
$ cargo run

Hexo markdown基本语法配置

一级标题：Level one header

二级标题：Level two header

三级标题：Level three header

四级标题：Level four header

Insert Code block:

1

$ hexo new "My New Post"

1
2
3

data List a = Cons a (List a)
            | Nil
              deriving (Show)

Insert a picture

Insert by url address