Jason Wang's Playground


  • Home

  • Archives

  • Tags

  • 公益404

RESTful API Design Principles

Posted on 2016-03-25

RESTful API 设计指南

[转载] 原文地址:RESTful API 设计指南

作者: 阮一峰

日期: 2014年5月22日

网络应用程序,分为前端和后端两个部分。当前的发展趋势,就是前端设备层出不穷(手机、平板、桌面电脑、其他专用设备……)。

因此,必须有一种统一的机制,方便不同的前端设备与后端进行通信。这导致API构架的流行,甚至出现“API First”的设计思想。RESTful API是目前比较成熟的一套互联网应用程序的API设计理论。我以前写过一篇《理解RESTful架构》,探讨如何理解这个概念。

今天,我将介绍RESTful API的设计细节,探讨如何设计一套合理、好用的API。我的主要参考了两篇文章

  1. http://codeplanet.io/principles-good-restful-api-design/
  2. https://bourgeois.me/rest/。

一、协议

API与用户的通信协议,总是使用HTTPs协议。

二、域名

应该尽量将API部署在专用域名之下。

https://api.example.com

如果确定API很简单,不会有进一步扩展,可以考虑放在主域名下。

https://example.org/api/

三、版本(Versioning)

应该将API的版本号放入URL。

https://api.example.com/v1/

另一种做法是,将版本号放在HTTP头信息中,但不如放入URL方便和直观。Github采用这种做法。

四、路径(Endpoint)

路径又称”终点”(endpoint),表示API的具体网址。

在RESTful架构中,每个网址代表一种资源(resource),所以网址中不能有动词,只能有名词,而且所用的名词往往与数据库的表格名对应。一般来说,数据库中的表都是同种记录的”集合”(collection),所以API中的名词也应该使用复数。

举例来说,有一个API提供动物园(zoo)的信息,还包括各种动物和雇员的信息,则它的路径应该设计成下面这样。

https://api.example.com/v1/zoos
https://api.example.com/v1/animals
https://api.example.com/v1/employees

五、HTTP动词

对于资源的具体操作类型,由HTTP动词表示。

常用的HTTP动词有下面五个(括号里是对应的SQL命令)。

GET(SELECT):从服务器取出资源(一项或多项)。
POST(CREATE):在服务器新建一个资源。
PUT(UPDATE):在服务器更新资源(客户端提供改变后的完整资源)。
PATCH(UPDATE):在服务器更新资源(客户端提供改变的属性)。
DELETE(DELETE):从服务器删除资源。

还有两个不常用的HTTP动词。

HEAD:获取资源的元数据。
OPTIONS:获取信息,关于资源的哪些属性是客户端可以改变的。

下面是一些例子。

GET /zoos:列出所有动物园
POST /zoos:新建一个动物园
GET /zoos/ID:获取某个指定动物园的信息
PUT /zoos/ID:更新某个指定动物园的信息(提供该动物园的全部信息)
PATCH /zoos/ID:更新某个指定动物园的信息(提供该动物园的部分信息)
DELETE /zoos/ID:删除某个动物园
GET /zoos/ID/animals:列出某个指定动物园的所有动物
DELETE /zoos/ID/animals/ID:删除某个指定动物园的指定动物

六、过滤信息(Filtering)

如果记录数量很多,服务器不可能都将它们返回给用户。API应该提供参数,过滤返回结果。

下面是一些常见的参数。

?limit=10:指定返回记录的数量
?offset=10:指定返回记录的开始位置。
?page=2&per_page=100:指定第几页,以及每页的记录数。
?sortby=name&order=asc:指定返回结果按照哪个属性排序,以及排序顺序。
?animal_type_id=1:指定筛选条件

参数的设计允许存在冗余,即允许API路径和URL参数偶尔有重复。比如,GET /zoo/ID/animals 与 GET /animals?zoo_id=ID 的含义是相同的。

七、状态码(Status Codes)

服务器向用户返回的状态码和提示信息,常见的有以下一些(方括号中是该状态码对应的HTTP动词)。

200 OK - [GET]:服务器成功返回用户请求的数据,该操作是幂等的(Idempotent)。
201 CREATED - [POST/PUT/PATCH]:用户新建或修改数据成功。
202 Accepted - [*]:表示一个请求已经进入后台排队(异步任务)
204 NO CONTENT - [DELETE]:用户删除数据成功。
400 INVALID REQUEST - [POST/PUT/PATCH]:用户发出的请求有错误,服务器没有进行新建或修改数据的操作,该操作是幂等的。
401 Unauthorized - [*]:表示用户没有权限(令牌、用户名、密码错误)。
403 Forbidden - [*] 表示用户得到授权(与401错误相对),但是访问是被禁止的。
404 NOT FOUND - [*]:用户发出的请求针对的是不存在的记录,服务器没有进行操作,该操作是幂等的。
406 Not Acceptable - [GET]:用户请求的格式不可得(比如用户请求JSON格式,但是只有XML格式)。
410 Gone -[GET]:用户请求的资源被永久删除,且不会再得到的。
422 Unprocesable entity - [POST/PUT/PATCH] 当创建一个对象时,发生一个验证错误。
500 INTERNAL SERVER ERROR - [*]:服务器发生错误,用户将无法判断发出的请求是否成功。

状态码的完全列表参见这里。

八、错误处理(Error handling)

如果状态码是4xx,就应该向用户返回出错信息。一般来说,返回的信息中将error作为键名,出错信息作为键值即可。

{
    error: "Invalid API key"
}

九、返回结果

针对不同操作,服务器向用户返回的结果应该符合以下规范。

GET /collection:返回资源对象的列表(数组)
GET /collection/resource:返回单个资源对象
POST /collection:返回新生成的资源对象
PUT /collection/resource:返回完整的资源对象
PATCH /collection/resource:返回完整的资源对象
DELETE /collection/resource:返回一个空文档

十、Hypermedia API

RESTful API最好做到Hypermedia,即返回结果中提供链接,连向其他API方法,使得用户不查文档,也知道下一步应该做什么。

比如,当用户向api.example.com的根目录发出请求,会得到这样一个文档。

{
  "link": {
    "rel":   "collection https://www.example.com/zoos",
    "href":  "https://api.example.com/zoos",
    "title": "List of zoos",
    "type":  "application/vnd.yourformat+json"
  }
}

上面代码表示,文档中有一个link属性,用户读取这个属性就知道下一步该调用什么API了。rel表示这个API与当前网址的关系(collection关系,并给出该collection的网址),href表示API的路径,title表示API的标题,type表示返回类型。

Hypermedia API的设计被称为HATEOAS。Github的API就是这种设计,访问api.github.com会得到一个所有可用API的网址列表。

{
  "current_user_url": "https://api.github.com/user",
  "authorizations_url": "https://api.github.com/authorizations",
  // ...
}

从上面可以看到,如果想获取当前用户的信息,应该去访问api.github.com/user,然后就得到了下面结果。

{
  "message": "Requires authentication",
  "documentation_url": "https://developer.github.com/v3"
}

上面代码表示,服务器给出了提示信息,以及文档的网址。

十一、其他

(1)API的身份认证应该使用OAuth 2.0框架。

(2)服务器返回的数据格式,应该尽量使用JSON,避免使用XML。

(完)

文档信息

版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
发表日期: 2014年5月22日

Introduction of JSON

Posted on 2016-03-24

1 JSON 简介

JSON:JavaScript 对象表示法(JavaScript Object Notation)。

它基于ECMAScript的一个子集,采用完全独立于语言的文本格式。易于人阅读和编写,同时也易于机器解析和生成(一般用于提升网络传输速率)。 类似于 XML,但比 XML 更小、更快,更易解析。是一种理想的数据交换语言。

特点:

  • JSON 指的是 JavaScript 对象表示法(JavaScript Object Notation)
  • JSON 是轻量级的文本数据交换格式
  • JSON 独立于语言
  • JSON 具有自我描述性,易理解

Example:

1
2
3
4
5
6
7
8
9
10
11
12
{
name: "World"
countries: [
{
name: "United States",
capital: "Washington, D.C."
}, {
name: "United Kingdom",
capital: "London"
}
]
}

2 JSON 语法

JSON 语法规则

JSON 语法是 JavaScript 对象表示语法的子集。

  • 数据在键值对中

    “firstName”:”John”

  • 数据由逗号分隔

    “firstName”:”John”, “lastName”:”Lock”

  • 花括号保存对象

    {“firstName”:”John”}

  • 方括号保存数组

    [“id”:1}, {“id”:2}]

JSON 名称/值对

JSON 数据的书写格式是:名称/值对。 名称/值对组合中的名称写在前面(在双引号中),值对写在后面(同样在双引号中),中间用冒号隔开:

"firstName":"John"

等价于这条 JavaScript 语句:

firstName = "John";

JSON 值

JSON 值可以是:

  • 数字(整数或浮点数)

    height: 8848

  • 字符串(在双引号中)

    firstName: “John”

  • 逻辑值(true 或 false)

    is_installed: false

  • 数组(在方括号中)

  • 对象(在花括号中)
  • null

    name: null

即除了以上几种形式的JS对象不是合法的JSON值,如function就不是合法的JSON值

基础结构

JSON结构有两种结构,简单说就是javascript中的对象和数组,所以这两种结构就是对象和数组两种结构,通过这两种结构可以表示各种复杂的结构。

1、对象

对象在js中表示为“{}”括起来的内容,数据结构为 {key:value,key:value,…}的键值对的结构。

在面向对象的语言中,key为对象的属性,value为对应的属性值,所以很容易理解,取值方法为 对象 .key 获取属性值,这个属性值的类型可以是 数字、字符串、数组、对象几种。

2、数组

数组在js中是中括号“[]”括起来的内容,数据结构为 [“java”,”javascript”,”vb”,…],取值方式和所有语言中一样,使用索引获取,字段值的类型可以是 数字、字符串、数组、对象几种。

经过对象、数组2种结构就可以组合成复杂的数据结构了。

3 JSON 使用

3.1 在JavaScript中使用JSON

在JavaScript中,处理JSON不需要任何特殊的API或工具包。

序列化与反序列化

较新的浏览器中,可以通过 JSON.stringify 和 JSON.parse 来实现序列化和反序列化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var world = {
name: "World",
countries: [
{
name: "United States",
capital: "Washington, D.C."
}, {
name: "United Kingdom",
capital: "London"
}
]
};

// Serialization
var str = JSON.stringify(world);
console.log(str);

// Deserialization
var parsedWorld = JSON.parse(str);

访问JSON元素

访问元素

通过 .key 访问对象属性

1
console.log(world.name);

通过 [index] 访问数组元素

1
console.log(world.countries[0]);

遍历元素

通过 for-in 来遍历 JSON 数据

1
2
3
for (var key in world) {
console.log('key: ' + JSON.stringify(world[key]));
}

修改JSON元素

增加元素

通过 obj.key 的方法增加属性

1
2
world.planet = "Earth";
console.log(JSON.stringify(world));

通过 obj[index] 的方法增加数组元素,(index不在已有数组索引范围内)

1
2
3
4
5
world.countries[2] = {
name: "Japan",
capital: "Tokyo"
};
console.log(JSON.stringify(world));

删除元素

通过 delete obj.key 的方式来删除属性:

1
2
delete world.planet;
console.log(JSON.stringify(world));

通过 array.splice 删除数组元素

1
2
world.countries.splice(2, 1);
console.log(JSON.stringify(world));

修改元素

在访问时直接赋新值即可完成修改

3.2 在.NET中使用JSON

在.NET中有三种常用的JSON序列化的类,分别是

  • System.Web.Script.Serialization.JavaScriptSerializer类
  • System.Runtime.Serialization.Json.DataContractJsonSerializer类
  • Newtonsoft.Json.JsonConvert类

定义JSON数据格式类

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
36
37
38
39
40
41
42
[DataContract]
class Country
{
[DataMember]
public string Name { get; set; }
[DataMember]
public string Captital { get; set; }

public Country()
{

}

public Country (string name, string capital)
{

Name = name;
Captital = capital;
}
}

[DataContract]
class World
{
[DataMember]
public string Name { get; set; }
[DataMember]
public List<Country> Countries {get; set; }

public World()
{

Name = "World";
Countries = new List<Country>();
}
}

static void Main(string[] args)
{

World world = new World();

// Add elements
world.Countries.Add(new Country("United States", "Washington, D.C."));
world.Countries.Add(new Country("United Kingdom", "London"));
}

使用System.Web.Script.Serialization.JavaScriptSerializer

JavaScriptSerializer是.NET自带的处理JSON的类,JavaScriptSerializer类在System.Web.Extensions.dll中,需要添加引用System.Web.Extensions.dll

示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using System.Web.Script.Serialization;
using System.Collections.Generic;
using System;

namespace json
{
class Program
{
static void UseJavaScriptSerializer(World world)
{

// JavaScriptSerializer类在System.Web.Extensions.dll中,需要添加引用System.Web.Extensions.dll
JavaScriptSerializer serializer = new JavaScriptSerializer();

//JSON 序列化
string str = serializer.Serialize(world);
Console.WriteLine("JavaScriptSerializer: after Serialization: {0}, length: {1}", str, str.Length);

//JSON 反序列化
World _world = serializer.Deserialize<World>(str);
Console.WriteLine("JavaScriptSerializer: after Deserialization: Name: {0}, Countries Count: {1}", _world.Name, _world.Countries.Count);
}
}
}

执行后输出:

1
2
3
JavaScriptSerializer: after Serialization: {"Name":"World","Countries":[{"Name":"United States","Captital":"Washington, D.C."},{"Name":"United Kingdom","Captita
l":"London"}]}, length: 131

JavaScriptSerializer: after Deserialization: Name: World, Countries Count: 2

注意:

如果不想序列化某个字段,可以在字段前面加[JsonIgnore]标记。

使用Newtonsoft.Json.JsonConvert

Newtonsoft.Json.JsonConvert类是非微软提供的一个JSON序列化和反序列的开源免费的类库(下载网址是:https://github.com/JamesNK/Newtonsoft.Json/releases),它提供了更灵活的序列化和反序列化控制。并且如果你的开发环境使用的是.NET Framework3.5及以后版本的话,你就可以使用Linq to JSON,只解析出关心的那部分即可,非常方便。

需要下载并添加引用Newtonsoft.Json.dll;

示例如下:

1
2
3
4
5
6
7
//JSON 序列化  
string str = JsonConvert.SerializeObject(world);
Console.WriteLine("SerializeObject: after Serialization: {0}, length: {1}", str, str.Length);

//JSON 反序列化
World _world = JsonConvert.DeserializeObject<World>(str);
Console.WriteLine("JavaScriptSerializer: after Deserialization: Name: {0}, Countries Count: {1}", _world.Name, _world.Countries.Count);

注意:

如果需要序列化实体

1、类名必须添加[DataContract]标记;

2、类属性添加[DataMember]标记;

如果有不需要序列化的字段,可以给该字段添加[JsonIgnore]标记

性能对比

image

其他

对JSON数据的操作(如增加、删除、更新)其实就是对C#类的操作。

4 JSON 小结

JSON文件

  • 通常JSON 文件的文件类型设置为 “.json” ,用于区分其它格式的文本文件。
  • JSON 文本的 MIME 类型是 “application/json”

与 XML 比较

  • 可读性

    JSON: 简易的语法, XML: 规范的标签形式

    不分胜负

  • 可扩展性

    不分胜负

  • 编解码难度

    在JS中,JSON具有优势

  • 数据效率

    JSON不需要有严格的闭合标签,有效数据量与总数据包比大大提升,从而减少同等数据流量的情况下,网络的传输压力

相关链接

在线JSON编辑器:http://www.atool.org/jsoneditor.php

5 Reference

  1. JSON_百度百科, http://baike.baidu.com/link?url=9Xh66e3k3V_8H0GXI2UreQ43jK5tX84PVIT1Bh6tgswhISJG6zzwNRhvryOkvFRp9pyXlJtSUyiId9DaDzHAyK
  2. W3School_JSON教程, http://www.w3school.com.cn/json/index.asp
  3. 在.NET使用JSON作为数据交换格式, fangaoxin, http://blog.csdn.net/fangaoxin/article/details/7618152

GBS Build

Posted on 2016-03-22

本文是 Tizen 系统的 gbs build 的用法的中英文对照版,主要内容为如何使用 gbs build 命令

Reference: https://source.tizen.org/documentation/reference/git-build-system/usage/gbs-build

gbs build

PUBLISHED 19 Oct 2014

By using ‘gbs build’, the developer can build the source code and generate rpm packages locally. For instructions on using the build subcommand, use this command: gbs build –help

开发者可使用gbs build在本地编译源代码然后生成RPM包。使用命令 gbs build –help 可以获取关于子命令 build 的帮助指南

$ gbs build -h

gbs build workflow (gbs build 工作流程)

Input of gbs build (gbs build的输入)

Below is the input for gbs build:

以下是 gbs build 所需输入:

  • git project(s) which contains rpm packaging files

    包含rpm packing文件的git项目

  • binary rpm repositories (remote or local)

    二进制rpm包仓库

  • project build configurations (macros, flags, etc)

    项目编译配置,宏定义、标志位等

The binary rpm repositories contain all the binary rpm packages which are used to create the chroot environment and build packages, which can be remote, like tizen release or snapshot repositories, or local repository. Local repository supports two types:

二进制rpm包仓库包含所有rpm包,这些rpm包可以用来创建chroot环境和编译软件包。包仓库可以是远程的或者是本地的,远程的如Tizen的发布或快照仓库,本地仓库支持两种类型,如下:

  • A standard repository with repodata exists

    带repodata的标准仓库

  • A normal directory contains RPM packages. GBS will find all RPM packages under this directory.

    包含RPM包的普通目录,GBS可以在此目录下找到所有的RPM包

Please refer to Configuration File part to configure a repository.

请参考配置文件来配置一个软件包仓库

Build workflow (编译流程)

The input and output of gbs build are all repositories.

gbs build的输入和输出都是仓库

Note: All the rpm packages under the output repository (by default, ~/GBS-ROOT/local/repos/<VERSION>/) will be used when building packages. That is, all the packages under the output repository will be applied to the build environment, so make sure the output repository is clean if you don’t want this behavior.

注意:输出仓库(默认为~/GBS-ROOT/local/repos/<VERSION>/)下所有的rpm包将会被用于编译,如果你不希望使用这些包,请清理掉输出仓库中的rpm包。

Here’s the basic gbs build workflow

gbs build的基本流程

 ____________________
|                    |      ___________
| Source Code (GIT)  |---->|           |      _________________________
|____________________|     |           |     |                         |
 ____________________      |           |     |  Local repository of    |
|                    |     |           |     |                         |
|    Build config    |---->| GBS build |---->|                         |
|____________________|     |           |     |                         |
 ____________________      |           |     |  build RPM packages     |
|                    |     |           |     |(~/GBS-ROOT/local/repos/)|
|Binary repositories |     |           |     |_________________________|
|in GBS conf         |---->|___________|                  |
|(Remote or Local)   |           ^                        |
|____________________|           |________________________|

From the above diagram, we can see the input and input are all repositories and the output repository located at ‘~/GBS-ROOT/locals/repos/‘ by default. You can change the repo path by using ‘–buildroot’ to specify a different build root.

输出仓库默认为:~/GBS-ROOT/local/repos,可以通过 –buildroot 指定build root来改变仓库路径。

Local repos in gbs build root (‘~/GBS-ROOT’ by default) will affect build results, so you must make sure that repos don’t contains old or unnecessary RPM packages. While running gbs build, you can specify ‘–clean-repos’ to clean up local repos, which gbs created, before building. We recommend that gbs users set different gbs build root directories for different profiles. There are several ways:

gbs build root下的本地仓库会影响编译结果,所以你必须要保证仓库里没有旧的软件包或者无关的软件包。在编译的时候可以用 –clean-repos 选项在实际编译前清理 gbs 创建的本地仓库。建议 gbs 使用者针对不同的场景设置不同的 build root 目录。可以使用以下方法:

  • By default, the GBS build will put all output files under ~/GBS-ROOT/.

    GBS build默认会把所有的输出文件都放在 ~/GBS-ROOT/ 里

  • If the environment variable TIZEN_BUILD_ROOT exists, ${TIZEN_BUILD_ROOT} will be used as output top dir

    如果存在环境变量 TIZEN_BUILD_ROOT,其值 $(TIZEN_BUILD_ROOT) 将会作为 build root

  • If -B option is specified, then the specified directory is used, even if ${TIZEN_BUILD_ROOT} exists

    如果使用 -B 选项,那么就其参数将作为 build root ,即使环境变量 $(TIZEN_BUILD_ROOT) 存在

Output of gbs build (gbs build 输出)

Structure of a GBS build root directory

GBS build root的目录结构

gbs output top dir
|-- local
| |-- cache # repodata and RPMs from remote repositories
| |-- repos # generated local repo top directory
| | |-- tizen # distro one: tizen
| | | |-- armv7l # store armv7l RPM packages
| | | |-- i586 # store x86 RPM packages
| | `-- tizen2.0 # build for distro two: tizen2.0
| | `-- i586 # the same as above
| |-- scratch.armv7l.0 # first build root for arm build
| |-- scratch.i586.0 # second build root for x86 build
| |-- scratch.i586.1 # third build root for x86 build
| |-- scratch.i586.2 # fourth build root for x86 build
| |-- scratch.i586.3 # fifth build root for x86 build
| | # The above build root dir can be used by gbs chroot <build root dir>
| `-- sources # sources generated for build, including tarball, spec, patches, etc.
| |-- tizen
| `-- tizen2.0
`-- meta # meta data used by gbs

GBS Build Examples (Basic Usage) (GBS Build示例,基本用法)

1 Build a single package.

编译单个包

$ cd package1
$ gbs build -A i586

2 Build a package for different architectures.

为不同的架构编译包

Note: Supported architectures include: x86_64, i586, armv6l, armv7hl, armv7l, aarch64, mips, mipsel.

注意:支持的架构有: x86_64, i586, armv6l, armv7hl, armv7l, aarch64, mips, mipsel.

$ gbs build -A armv7l #build package for armv7l
$ gbs build -A i586 #build package for i586

3 Make a clean build by deleting the old build root. This option must be specified if the repo has been changed, for example, changed to another release.

删除旧的build root,全新编译。当软件包仓库有变化时,必须使用这个选项,比如改成使用另一个发行版的软件仓库时.

$ gbs build -A armv7l --clean

4 Build the package with a specific commit.

为特定提交编译包

$ gbs build -A armv7l --commit=<COMMIT_ID>

5 Use –overwrite to trigger a rebuild.

用–overwrite触发一次重新编译

If you have already built before, and want to rebuild, –overwrite should be specified, or the packages will be skipped.

如果以前已经编译过,并且想重新编译,应该使用–overwrite,否则已经编过的包会被跳过

$ gbs build -A i586 --overwrite

If you change the commit or specify –include-all option, it will always rebuild, so –overwrite is not needed.

如果有新提交或者带选项–include-all,则GBS总是会重新编译,此时滴必要使用–overwrite

6 Output the debug info.

输出调试信息

$ gbs build -A i586 --debug

7 Build against a local repository. You can config the local repo at .gbs.conf file or through the command line.

$ gbs build -R /path/to/repo/dir/ -A i586

8 Use –noinit to build package in offline mode.

使用 –noinit 选项,在离线模式下编译

–noinit option can only be used if build root is ready. With –noinit option, gbs will not connect the remote repo, and skip parsing & checking repo and initialize build environment. rpmbuild will be used to build the package directly. Here’s an example:

在build root准备好的情况下,可以使用选项 –noinit。使用 –noinit 选项时,gbs不会连接远程仓库并且会跳过解析/检查仓库和初始化编译环境,直接使用rpmbuild编译包.

重要:此选项可用于快速编译

$ gbs build -A i586 # build first and create build environment
$ gbs build -A i586 --noinit # use --noinit to start building directly

9 Build with all uncommitted changes using –include-all.

使用 –include-all 选项编译所有的未提交的改动

重要,此选项为常用选项,当用户本地有修改又没有提交时,经常需要使用此选项用于测试新代码

For example, the git tree contains one modified file and two extra files:

例如,git目录中包含一个改动的文件和二个新加的文件

$ git status -s
M ail.pc.in
?? base.repo
?? main.repo

Build without the –include-all option

不用–include-all编译

Builds committed files only. All the modified files, which are not committed nor added, will NOT be built:

仅编译已提交的文件。所有未提交或未添加到版本控制的文件都不会被编译:

$ gbs build -A i586
warning: the following untracked files would NOT be included: base.repo main.repo
warning: the following uncommitted changes would NOT be included: ail.pc.in
warning: you can specify '--include-all' option to include these uncommitted and untracked files.
....
info: Binaries RPM packages can be found here:
/home/test/GBS-ROOT/local/scratch.i586.0/home/abuild/rpmbuild/RPMS/
info: Done

Build with the –include-all option builds all the files

使用–include-all来编译所有的文件

$ gbs build -A i586 --include-all
info: the following untracked files would be included: base.repo main.repo
info: the following un-committed changes would be included: ail.pc.in
info: export tar ball and packaging files
...
...
[build finished]

Use .gitignore to ignore specific files, when using the –include-all option.

当使用–incldue-all时可以用.gitignore来忽略特定的文件

If you want to ignore some files types, you can update your .gitignore. For example:

如果要想忽略某类型文件可以修改.gitignore,例如:

$ cat .gitignore
.*
*/.*
*.pyc
*.patch*

Incremental build

增量编译

Incremental Concept

增量的概念

Starting from gbs 0.10, the gbs build subcommand supports building incrementally, which can be enabled by specifying the ‘–incremental’ option.

从gbs 0.10开始,gbs build就支持增量式的编译,通过指定–incremental选项来启用。

This mode is designed for development and verification of single packages. It is not intended to replace the standard mode. Only one package can be built at a time using this mode.

这种模式主要用来开发和验证单个软件包,不是用来替代标准的编译模式。在此模式下,一次只能编译一个包。

This mode will set up the build environment in multiple steps, finishing by mounting the local Git tree of a package in the chroot build environment.

这种模式分成多步来设置编译环境,把本地的软件包的Git目录绑定到chroot的编译目录后就完成了。

Note: Because gbs will mount your git tree to the build root, be very careful when you remove your build root. You need to make sure you’ve already umounted the source tree manually before you remove it.

注意:因为gbs会把git目录绑定到buid root,所以当要删除build root时要非常小心,删除前要确定已经手动地把源码解绑定。

This has the following benefits:

这种模式有以下优点:

  • The build environment uses the latest source code and changes to source do not trigger a new build environment (in the chroot).

    编译环境可以使用最新的源代码,并且代码的改动不会修改编译环境

  • The Git source tree becomes the source of the builds. Any change made in the Git repository followed by invocation of the build script will build the changed sources

    git目录变成了编译的源目录,只要在git中的任何改动之后,调用编译命令,就可以编译改动过的源代码

  • If the build fails for some reason, the build script will continue from the spot where it has failed, once the code has been changed to fix the problem causing the failure.

    编译失败后,一旦导致编译失败的错误被修正,编译脚本会从先前失败的地方接着编译

This mode is, in many ways, similar to traditional code development, where changes are made to sources, followed by running make to test and compile the changes. However, it enables development using the build environment of the target, instead of the host OS.

从不同的方面说,这种模式类似于传统的代码开发:修改代码然后运行make编译改动。不同的地方在于,增量编译使用编译环境而不是宿主机器的操作系统

This method has some limitations, mostly related to packaging and how the sources are maintained. Among others, it depends on how the RPM spec file is composed:

这种模式有一些限制,都是关于打包和代码的管理。尤其是依赖于RPM的spec文件

  • It does not support patches in the spec file. All source has to be maintained as part of the Git tree

    不支持spec文件中的patches,所有的源码必须是git目录的一部分

  • It requires a clean packaging workflow. Exotic workflows in the spec files might not work well, because this mode expects the following model:

    需要一个整洁的打包流程。spec文件中的极特殊的流程可能不会有效,因为这种模式预期以下模型:

    1. Code preparation (%prep) (代码准备)
    2. Code building (%build) (代码编译)
    3. Code installation (%install) (代码安装)
  • Because we run the %build section every time, if the %build script has configuration scripts (auto-tools), binaries might be regenerated, causing a complete build every time. To avoid this, you are encouraged to use the following macros, which can be overridden using the –no-configure option:

    因为每次都运行编译部分,如果%build脚本有自动配置脚本,二进制文件会被重新生成,导致每次都完全编译。为了避免这样情况发生,推荐使用下面的宏,这些宏能够用–no-configure选项来覆盖

    1. %configure: runs the configure script with pre-defined paths and options.
    2. %reconfigure: regenerates the scripts and runs %configure
    3. %autogen: runs the autogen script

Example

In this example, we use dlog source code. First, we need to build with –incremental, then just modify one source file, and trigger the incremental build again. We will see that only modified source code has been compiled during the incremental build.

$ cd dlog
# first build:
$ gbs build -A i586 --incremental
$ vim log.c # change code
# second build:
$ gbs build -A i586 --incremental
info: generate repositories ...
info: build conf has been downloaded at:
/var/tmp/test-gbs/tizen.conf
info: Start building packages from: /home/test/packages/dlog (git)
info: Prepare sources...
info: Retrieving repo metadata...
info: Parsing package data...
info: *** overwriting dlog-0.4.1-5.1 i586 ***
info: Next pass:
dlog
info: *** building dlog-0.4.1-5.1 i586 tizen (worker: 0) ***
info: Doing incremental build
[ 0s] Memory limit set to 10854336KB
[ 0s] Using BUILD_ROOT=/home/test/GBS-ROOT/local/scratch.i586.0
[ 0s] Using BUILD_ARCH=i686:i586:i486:i386:noarch
[ 0s] test-desktop started "build dlog.spec" at Thu Sep 13 07:36:14 UTC 2012.
[ 0s] -----------------------------------------------------------------
[ 0s] ----- building dlog.spec (user abuild)
[ 0s] -----------------------------------------------------------------
[ 0s] -----------------------------------------------------------------
[ 0s] + rpmbuild --short-circuit -bc /home/abuild/rpmbuild/SOURCES/dlog.spec
[ 0s] Executing(%build): /bin/sh -e /var/tmp/rpm-tmp.XLz8je
[ 0s] + umask 022
[ 0s] + export LD_AS_NEEDED
[ 4s] + make -j4
[ 4s] make all-am
[ 4s] make[1]: Entering directory /home/abuild/rpmbuild/BUILD/dlog-0.4.1
[ 4s] /bin/sh ./libtool --tag=CC --mode=compile gcc -c -o log.lo log.c
[ 4s] mv -f .deps/log.Tpo .deps/log.Plo
[ 4s] /bin/sh ./libtool --tag=CC --mode=link gcc -o libdlog.la /usr/lib log.lo
[ 4s] libtool: link: gcc -shared .libs/log.o -o .libs/libdlog.so.0.0.0
[ 4s] libtool: link: ar cru .libs/libdlog.a log.o
[ 4s] libtool: link: ranlib .libs/libdlog.a
[ 4s] make[1]: Leaving directory /home/abuild/rpmbuild/BUILD/dlog-0.4.1
[ 4s] + exit 0
[ 4s] finished "build dlog.spec" at Thu Sep 13 07:36:18 UTC 2012.
[ 4s]
info: finished incremental building dlog
info: Local repo can be found here:
/home/test/GBS-ROOT/local/repos/tizen/
info: Done

From the buildlog, we can see that only log.c has been re-compiled. That’s the incremental build behavior.

–noinit option can be used together with –incremental to make a build more quickly, like:

$ gbs build --incremental --noinit

Limitations of Incremental Build

增量编译的限制

Incremental build doesn’t support all packages. Here are some limitations:

增量编译不支持所有的包。一些限制如下:

  • Incremental build currently supports building only a single package. It doesn’t support building multiple packages in parallel

    只支持单个包

  • The tarball’s name in the spec file should be %{name}-%{version}.{tar.gz|tar.bz2|zip|…}, otherwise GBS can’t mount source code to build the root correctly

    spec文件中的压缩包名字必须是%{name}-%{version}.{tar.gz|tar.bz2|zip|…},否则GBS无法正确把源码绑定到build root中

  • %prep section should only contains %setup macro to unpack tarball, and should not contains other source code related operations, such as unpack another source, apply patches, etc.

    %prep部分应该仅包含用于解圧压缩包的%setup宏,而不应该含有对源代码的其他操作,比如解压其他源码或打patch等都不允许

Multiple packages build (dependency build) (多包编译)

Multiple package build has been supported since gbs 0.10. If packages have dependencies on each other, gbs will build packages in the correct order calculated by dependency relationship. Previously built out RPMs will be used to build the following packages that depend on them, which is the dependency build.

从gbs 0.10开始就支持多包编译。如果包有相互的依赖,gbs会计算出它们之间的关系然后按正确的顺序来编译。作为依赖编译,先前编译出的RPM包会用来编译后面的有依赖需求的包

Examples:

1 Build all packages under a specified package directory

编译指定目录下的所有的包

$ mkdir tizen-packages
$ cp package1 package2 package3 ... tizen-packages/
$ gbs build -A i586 tizen-packages # build all packages under tizen-packages

2 Build multiple packages in parallel with –threads

使用–threads选项来并行编译多个包

# current directory have multiple packages, --threads can be used to set the max build worker at the same time
$ gbs build -A armv7l --threads=4

3 Select a group of packages to be built

选择编译一组包

The –binary-from-file option specifies a text file that contains a name list of RPM packages to be built. The format in the text file is one package per line.

The –binary-list option specifies a list in which the package names are separated by comma.

When the number of packages is small, thus the packages can be clearly presented in command line, it is recommended to use the –binary-list option for simplicity.

$ gbs build -A i586 --binary-from-file=/path/to/packages.list
$ gbs build -A i586 --binary-list=<pkg1>,<pkg2>

4 Exclude certain packages.

排除某些包

The –exclude option specifies a list in which the names of packages to be ignored are separated by comma. The –exclude-from-file option specifies a text file that contains a name list of packages to be ignored.

$ gbs build -A i586 tizen-packages --exclude=<pkg1>
$ gbs build -A i586 tizen-packages --exclude=<pkg1>,<pkg2>
$ gbs build -A i586 tizen-packages --exclude-from-file=/path/to/packages.list

5 Build packages based on dependencies.

基于依赖来编译包

The –deps option enables GBS to build specific packages, together with all the related packages on which they depend.The –rdep option enables GBS to build specific packages, together with all the related packages that depend on them.

The specific packages can be included by the –binary-from-file option or the –binary-list option, and be excluded by the –exclude option or the –exclude-from-file option.

These two options are compatible. When added at the same time, besides the specific packages, GBS will build not only the related packages on which they depend, but also all the related packages that depend on them.

$ gbs build -A i586 --binary-list=<pkg1>,<pkg2> --deps
$ gbs build -A i586 --binary-list=<pkg1>,<pkg2> --rdeps
$ gbs build -A i586 --binary-list=<pkg1>,<pkg2> --deps --rdeps

Other useful options (其他有用的选项)

Install extra packages to build root

安装额外的包到build root中

–extra-packs= can be used to install extra packages:

$ gbs build --extra-packs=vim,zypper,gcc,gdb ...

Keep all packages in build root

保留所有build root中的包

Generally, gbs build will remove unnecessary packages in build root. While transferring to build another package, you can use –keep-packs to keep all unnecessary packages, and just install missing build required packages. This option can be used to speed up build multiple packages.

通常情况下,gbs build会把build root中的不需要的包删除掉。当要编译另外的包时可以使用–keep-packs选项来保留不再需要的包而只安装缺失的依赖包。这个选项可以加速多个包的编译。

重要:重要选项,可以节省编译时间

$ gbs build --keep-packs

–keep-packs can be used to create one build root for building multiple packages. Once the build root is ready, you can use –noinit to build these packages quickly.

–keep-packs选项可以用来为多个包创建一个build root。一旦build root准备好,就可以用 –noinit 选项来快速的编译这些包

重要:–keep-packs 配合 –noinit,可以节省编译时间

$ gbs build pkg1/ --keep-packs -A i586
$ gbs build pkg2/ --keep-packs -A i586
$ gbs build pkg3/ --keep-packs -A i586

Now, the build root (~/GBS-ROOT/local/scratch.i586.0) is ready for building pkg1, pkg2, and pkg3. You can use –noinit to build them offline, and don’t need waste time to check repo updates and build root.

$ gbs build pkg1 --noinit
$ gbs build pkg2 --noinit
$ gbs build pkg3 --noinit

Fetch the project build conf and customize build root (for Advanced Users) (高级用户,获取项目的编译配置和定制build root)

Project build conf describes the project build configurations for the project, including pre-defined macros/packages/flags in the build environment. In Tizen releases, the build conf is released together with the released repo. You can find an example at: http://download.tizen.org/releases/daily/trunk/ivi/latest/builddata/xxx-build.conf

gbs build will fetch the build conf automatically

Starting from gbs 0.7.1, by default, gbs will fetch the build conf from a remote repo, if you specify the remote Tizen repo, and then store it in your temp environment. Here’s the build log:

$ gbs build -A i586
info: generate repositories ...
info: build conf has been downloaded at:
/var/tmp/<user>-gbs/tizen2.0.conf
info: generate tar ball: packaging/acpid-2.0.14.tar.bz2
[sudo] password for <user>:

build the package using your own project build conf, using the -D option

You can save it and modify it, and then use it for your purposes:

cp /var/tmp/<user>-gbs/tizen2.0.conf ~/tizen2.0.conf
$ gbs build -A i586 -D ~/tizen2.0.conf

If you need to customize the build config, refer to: http://en.opensuse.org/openSUSE:Build_Service_prjconf

Reference: https://source.tizen.org/documentation/reference/git-build-system/usage/gbs-build

node-gyp 设置 Proxy

Posted on 2016-03-13

node-gyp 设置 Proxy

node-gyp 提供 4 种方式通过Proxy连接

1) 使用命令行参数 –proxy=http://proxy_address:proxy_port

2) 使用环境变量 http_proxy

3) 使用环境变量 HTTP_PROXY

4) 使用环境变量 npm_config_proxy

注意:Proxy的 http:// 不能省略

如何下载离线版Windows Chrome安装文件

Posted on 2016-03-13

如何下载离线版Windows Chrome安装文件

方法如下:

对于Stable Chrome来说,只需要在Chrome的“最终用户许可协议”页面链接后面添加”?standalone=1″即可,也就是:

http://www.google.com/chrome/eula.html?standalone=1

对于特定版本的Chrome来说,按以下地址:

http://dl.google.com/chrome/install/{version number}/chrome_installer.exe

其中的 version number 代表你要下载的Chrome版本号的后面两个数字,比如4.0.223.11的离线包下载地址就是

http://dl.google.com/chrome/install/223.11/chrome_installer.exe

设计模式

Posted on 2016-03-13

March 13, 2016 / Jason Wang

Design Pattern

设计模式(Design pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 毫无疑问,设计模式于己于他人于系统都是多赢的;设计模式使代码编制真正工程化;设计模式是软件工程的基石脉络,如同大厦的结构一样。

设计模式4要素

1. 模式名称 (pattern name) 用一两个词来描述模式的问题、解决方案和效果。

2. 问题(problem) 描述了应当在何时使用模式

3. 解决方案(solution) 描述了设计的组成部分

4. 效果(consequences) 描述了应用模式的效果和使用模式应权衡的问题

设计模式类型

设计模式分为三种类型,共23种。

创建型 结构型 行为型
Factory Method Bridge Template Method
Abstract Factory Adapter Strategy
Singleton Decorator Observer
Builder Composite Memento
Prototype Flyweight Mediator
Facade Command
Proxy Visitor
Chain of Responsibilty
Iterator
Interpreter

创建型模式与对象的创建有关;结构型模式处理类或对象的组合;行为型模式对类或对象怎样交互和怎样分配职责进行描述

创建型模式

Pattern Descriptions
Factory Method(工厂模式) 定义一个用于创建对象的接口,让子类决定将哪一个类实例化。Factory Method使一个类的实例化延迟到其子类。
Abstract Factory(抽象工厂模式) 提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类。
Singleton(单例模式) 保证一个类仅有一个实例,并提供一个访问它的全局访问点。
Builder(建造者模式) 将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。
Prototype(原型模式) 用原型实例指定创建对象的种类,并且通过拷贝这个原型来创建新的对象。

结构型模式

Pattern Descriptions
Bridge(桥接模式) 将抽象部分与它的实现部分分离,使它们都可以独立地变化。
Adapter(适配器模式) 将一个类的接口转换成客户希望的另外一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
Decorator(装饰器模式) 动态地给一个对象添加一些额外的职责。就扩展功能而言, 它比生成子类方式更为灵活。
Composite(组合模式) 将对象组合成树形结构以表示“部分-整体”的层次结构。它使得客户对单个对象和复合对象的使用具有一致性。
Flyweight(享元模式) 运用共享技术有效地支持大量细粒度的对象。
Facade(外观模式) 为子系统中的一组接口提供一个一致的界面,Facade模式定义了一个高层接口,这个接口使得这一子系统更加容易使用。
Proxy(代理模式) 为其他对象提供一个代理以控制对这个对象的访问。

行为型模式

Pattern Descriptions
Template Method(模板方法模式) 定义一个操作中的算法的骨架,而将一些步骤延迟到子类中。Template Method使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。
Strategy(策略模式) 定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。本模式使得算法的变化可独立于使用它的客户。
Observer(观察者模式) 定义对象间的一种一对多的依赖关系,以便当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并自动刷新。
Memento(备忘录模式) 在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。这样以后就可将该对象恢复到保存的状态。
Mediator(中介模式) 用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地相互引用,从而使其耦合松散,而且可以独立地改变它们之间的交互。
Command(命令模式) 将一个请求封装为一个对象,从而使你可用不同的请求对客户进行参数化;对请求排队或记录请求日志,以及支持可取消的操作。
Visitor(访问者模式) 表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。
Chain of Responsibilty(职责链模式) 为解除请求的发送者和接收者之间耦合,而使多个对象都有机会处理这个请求。将这些对象连成一条链,并沿着这条链传递该请求,直到有一个对象处理它。
Iterator(迭代器模式) 提供一种方法顺序访问一个聚合对象中各个元素,而又不需暴露该对象的内部表示。
Interpreter(解析器模式) 给定一个语言, 定义它的文法的一种表示,并定义一个解释器, 该解释器使用该表示来解释语言中的句子。

Ubuntu下配置PPTP VPN

Posted on 2016-03-12

Configure PPTP VPN in Ubuntu

安装pptpd

$ sudo apt-get install pptpd

配置

编辑pptpd.conf

$ sudo vi /etc/pptpd.conf

修改如下两行:

localip xxx.xxx.xxx.xxx
remoteip 192.168.1.100-200

localip: Ubuntu主机的IP

remoteip: 分配给Client的IP段

设置Windows Client的DNS

$ sudo vi /etc/ppp/pptpd-options

修改ms-dns,修改为google的dns:

ms-dns 8.8.8.8
ms-dns 8.8.4.4

设置账号

$ sudo vi /etc/ppp/chap-secrets

添加一行,依次为:用户名,服务,密码,限制ip:

"user" pptpd "user" *

或

username * password *

重启服务

$ sudo /etc/init.d/pptpd restart

执行以上步骤后VPN即可连接上了,但是还无法上网。

设置IP转发

允许转发

$ sudo vi /etc/sysctl.conf

去掉文件中这一行的注释:

net.ipv4.ip_forward=1

使设置生效:

$ sudo sysctl -p

设置NAT

$ sudo iptables -t nat -A POSTROUTING -s 192.168.1.0/24 -o eth0 -j MASQUERADE

设置MTU,防止包过大:

$ sudo iptables -A FORWARD -s 192.168.1.0/24 -p tcp -m tcp --tcp-flags SYN,RST SYN -j TCPMSS --set-mss 1200

保存设置

$ sudo iptables-save

将输出保存到以下文件中

$ sudo /etc/iptables-rules

自动加载规则

编辑网卡文件,加载网卡时自动加载规则

$ sudo vi  /etc/network/interfaces

添加一行:

pre-up iptables-restore < /etc/iptables-rules

Fin

在Github上利用Hexo创建博客

Posted on 2016-03-12

在Github上利用Hexo创建博客

Hexo是一款基于Nodejs的,快速、简单且功能强大的博客框架。支持多线程,支持markdown编写文章,可以方便的生成静态网页托管在github上。

Install Hexo

步骤:

1 安装 Git

下载并安装 msysgit

2 安装 node.js 和 npm

下载并安装 nodejs

3 安装 Hexo

1
$ npm install hexo-cli -g

4 创建Hexo文件夹

创建一个文件夹用于编写本地博客,如(E:\hexo)。

在此文件夹中输入以下命令进行初始化:

1
$ hexo init

5 安装依赖包

1
$ npm install

至此,我们就安装好Hexo了,并且可以开始撰写本地博客了。

Using Hexo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Usage: hexo <command>

Commands:
clean Removed generated files and cache.
config Get or set configurations.
deploy Deploy your website.
generate Generate static files.
help Get help on a command.
init Create a new Hexo folder.
list List the information of the site
migrate Migrate your site from other system to Hexo.
new Create a new post.
publish Moves a draft post from _drafts to _posts folder.
render Render files with renderer plugins.
server Start the server.
version Display version information.

常用命令:

创建一篇新的博客

1
2
3
hexo new
or
hexo n

生成静态博客文件

1
2
3
hexo generate
or
hexo g

启动本地服务

1
2
3
hexo server
or
hexo s

执行可以在浏览器中输入localhost:4000 预览博客。

Deploy

部署之前先要配置一下Hexo。

1 安装hexo-deployer-git

1
$ npm install hexo-deployer-git --save

2 在目录 E:\hexo 下,编辑 _config.yml(将xyz换成你自己的github用户名):

1
2
3
4
deploy:
type: git
repository: https://github.com/xyz/xyz.github.io.git
branch: master

执行下列指令即可完成部署。

1
2
hexo generate
hexo deploy

中途会提示输入GitHub账号和密码,正常输入即可。

Tips

  1. 每次修改本地文件后,需要执行 hexo generate 才能生成新的博客文件。
  2. 所有hexo命令都要在 hexo 文件目录下执行。
  3. 发布后GitHub会有一定的延时

Shuffle Algorithm

Posted on 2016-03-05
Shuffle Algorithm

Febrary 28, 2016 / Jason Wang

洗牌算法

为了保证打牌时的公平性,洗牌后的牌堆应当是完全随机的。

从概率的角度来说,牌堆可以看成一个编号为 $ 1 $ 到 $ n $ 的数的序列,这个序列的排列组合数为 $ n! $。

整齐的牌堆

完全随机也就是说每一种排列组合出现的概率相等,概率为 $ \frac{1}{n!} $

朴素洗牌算法

所谓朴素,就是说每次从未取出的数中随机取出一个数,排成序列。

点击开始洗牌

JavaScript的代码如下:

        
function naiveShuffle(array) {
  var shuffle = [];
  var n = array.length;
  var i;

  while (n) {
    // Pick a random element
    i = Math.floor(Math.random() * n--);

    // Add the element to new pack
    // Re-order the left elements
    shuffle.push(array.splice(i, 1));
  }

  return shuffle;
}
        
      

取第一个数时,从 $ n $ 个数中随机取一个数(有 $ n $ 种可能);取第二个数时,从剩下的 $ n - 1 $ 个数中随机取一个数(有 $n - 1$ 种可能);如此重复 $n$ 次,则可得到一个序列。

此序列的概率为 $ \frac{1}{n!} $ , 与完全随机的概率一致。

分析一下此算法的性能

空间: $ O(n) $, 需要一个额外的大小为 $ n $ 的空间存储结果

时间: $ O(n^{2}) $, while循环的复杂度为 $ O(n) $ , 循环内整理牌堆的复杂度也为 $ O(n) $。

Fisher-Yates算法

接下来介绍一种更为有效的算法。

        
function fisherYatesShuffle(array) {
  var n = array.length;
  var i;

  while (n) {
    // Pick a random element
    i = Math.floor(Math.random() * n--);

    // Swap the random element with element in position n.
    t = array[n];
    array[n] = array[i];
    array[i] = t;
  }

  return array;
}
        
      

从第 $ 1 $ 到 $ n $ 个数中随机选取一个数,和第 $ n $ 个数交换,每次将 $ n $ 的值减 $ 1 $ ,如此重复 $ n $ 次,则可得到一个序列。

此序列的概率同样为 $ \frac{1}{n!} $ 。

同样分析一下此算法的性能

空间: $ O(0) $, 因为将当前位置的数存放在与之交换的数的位置上,所以不需要额外的空间。

时间: $ O(n) $, while循环的复杂度为 $ O(n) $ , 循环内操作的复杂度为 $ O(1) $。

本文主要参考了Mike Bostock的 "Fisher–Yates Shuffle"

可视化使用了D3.js

语法高亮使用了highlightjs

数学公式引擎使用了MathJax

Hello Hexo

Posted on 2016-03-05

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

12
Jason Wang

Jason Wang

Play Fun

20 posts
30 tags
© 2016 Jason Wang
Powered by Hexo
Theme - NexT.Pisces