每天学习一个命令：fdisk 查看磁盘详情

fdisk 命令用于观察硬盘实体使用情况，可以用来列出机器中所有磁盘的个数，也能列出所有磁盘分区情况，也可对硬盘分区（适用于 2T 以下磁盘，高于 2T 磁盘使用 parted)。

常见用法

显示所有磁盘的分区详情

fdisk -l

常见的磁盘标示都是 sda, sdb 类似，而分区则是在磁盘标示后面添加数字，比如 sda1, sda2, … , sdb3 等等。

选择进行操作的磁盘

fdisk /dev/sdb

对 U 盘进行格式化，其他设备同理。

# 查看 U 盘挂载点（此例是 /tmp/mnt/sda1）
$ df -h
Filesystem                Size      Used Available Use% Mounted on
ubi:rootfs_ubifs         77.2M     64.0M     13.2M  83% /
mtd:bootfs                4.4M      3.3M      1.1M  75% /bootfs
mtd:data                  8.0M    556.0K      7.5M   7% /data
/dev/mtdblock8           48.0M      9.0M     39.0M  19% /jffs
/dev/sda1                 3.5G     51.1M      3.3G   2% /tmp/mnt/sda1

# 卸载 U 盘
$ umount /tmp/mnt/sda1

# 查看 U 盘设备路径（此例是 /dev/sda）
$ fdisk -l
Disk /dev/sda: 3869 MB, 3869544448 bytes
245 heads, 52 sectors/track, 593 cylinders
Units = cylinders of 12740 * 512 = 6522880 bytes
   Device Boot      Start         End      Blocks  Id System
/dev/sda1               1         593     3777384  83 Linux

# 删除分区、新建分区
$ fdisk /dev/sda
Command (m for help): d  # 删除分区
Selected partition 1
Command (m for help): n  # 新建分区
Command action
   e   extended
   p   primary partition (1-4)
p
Partition number (1-4): 1
First cylinder (1-1015, default 1): Using default value 1
Last cylinder or +size or +sizeM or +sizeK (1-1015, default 1015): Using default value 1015
Command (m for help): w  # 保存分区
The partition table has been altered.
Calling ioctl() to re-read partition table

# 格式化分区为 ext4
mkfs.ext4 /dev/sda1

# 挂载 U 盘
$ mkdir /tmp/mnt/sda1
$ mount -t ext3 /dev/sda1 /tmp/mnt/sda1

2016-04-02 fdisk , disk , linux , partition , command

MySQL 中的大小写敏感设置

默认情况下 MySQL 中存储内容不是大小写敏感的。MySQL 的大小写和建数据库时的排序规则有关。

utf8_bin 则是将字符串中的每一个字符用二进制存储，bin 是 binary case sensitive collation，区分大小写
utf8_general_ci 不区分大小写，ci 为 case insensitive
utf8_general_cs 区分大小写，cs 为 case sensitive 缩写

建表时字段区分大小写

在建表时可以通过 BINARY 来区别

比如

CREATE TABLE test
(
    name VARCHAR(20),
    UNIQUE(name)
);

mysql>     INSERT INTO test VALUES('California');
Query OK, 1 row affected (0.00 sec)

mysql>     INSERT INTO test VALUES('california');
ERROR 1062 (23000): Duplicate entry 'california' for key 'name'

mysql>     INSERT INTO test VALUES('cAlifornia');
ERROR 1062 (23000): Duplicate entry 'cAlifornia' for key 'name'

mysql>     INSERT INTO test VALUES('cALifornia');
ERROR 1062 (23000): Duplicate entry 'cALifornia' for key 'name'

mysql> SELECT * FROM test;
+------------+
| name       |
+------------+
| California |
+------------+
1 row in set (0.00 sec)

如果需要配置大小写敏感则需要使用 BINARY

mysql>     CREATE TABLE test
    ->     (
    ->         name varchar(20) BINARY,
    ->         UNIQUE(name)
    ->     );
Query OK, 0 rows affected (0.00 sec)

mysql>
mysql>     INSERT INTO test VALUES('California');
Query OK, 1 row affected (0.00 sec)

mysql>
mysql>     INSERT INTO test VALUES('california');
Query OK, 1 row affected (0.00 sec)

mysql>     INSERT INTO test VALUES('cAlifornia');
Query OK, 1 row affected (0.00 sec)

mysql>     INSERT INTO test VALUES('cALifornia');
Query OK, 1 row affected (0.00 sec)

mysql>
mysql>     SELECT * FROM test;
+------------+
| name       |
+------------+
| California |
| cALifornia |
| cAlifornia |
| california |
+------------+
4 rows in set (0.00 sec)

查询区分大小写

当然在建库，或者建表时已经排序规则之后就要按照之前的约定，如果没有约定，按照默认则需要自己指定。

强制让 where 语句中区分大小写需要在 where 后添加 binary

select * from table where binary name='Abc'

配置表名大小写不敏感

需要修改配置

/etc/mysql/my.cnf

在 [mysqld] 配置下面：

lower_case_table_names = 1

然后需要重新加载 mysql 配置或者重启 MySQL 服务。

reference

https://stackoverflow.com/a/20876063/1820217

2016-04-01 mysql , sql , index

查看当前正在使用哪种 Shell

当前正在运行的 shell 路径被保存在 $0 环境变量中，可以使用如下方式查看

echo $0

根据不同系统的实现，输出可能会是当前正在运行的 shell，或者是当前运行的 shell 的路径。

prompt:~$ echo $0
/bin/bash
prompt:~$ sh
sh-4.0$ echo $0
sh
sh-4.0$ exit
exit
prompt:~$ /bin/sh
sh-4.0$ echo $0
/bin/sh
sh-4.0$

$SHELL 变量保存了用户偏好的 shell，而不是当前正在运行的 shell。

更多关于 shell 的默认特殊变量，可以查看之前的总结。

2016-03-27 linux , shell , bash , sh , zsh

推荐网站之邮件签名：htmlsig

推荐好用的网站系列之生成邮件签名 htmlsig 。想要一个漂亮的邮件签名，又不想自己写 html，最好的方法就是找一个模板然后自己填写内容。这个网站就是这样的。

官网地址：https://htmlsig.com/

样式1 htmlsig 1

样式2 htmlsig 2

样式3 htmlsig 3

样式4 htmlsig 4

当然我本人最喜欢样式2.

如果稍微懂一点 html 知识，将模板下载下来然后自己手动修改倒也是不错的选择。

生成自己的模板之后，Gmail 和 Inbox 都可以使用复制粘贴的方式将签名添加进去。

2016-03-23 website , 推荐网站

C++ 解析JSON

因项目需求，需要使用 C++ 解析 JSON。

RapidJSON

第一种方法，使用 RapidJSON 可以方便的用来生成或者解析 JSON。

项目地址：https://github.com/miloyip/rapidjson

RapidJSON 是只有头文件的 C++ 库。使用时只需要把 include/rapidjson 复制到项目目录中即可。

类似如下的JSON，其中包括Object，包括Array，掌握解析该JSON，基本 RapidJSON 解析可掌握：

{
  "ret": "101",
  "error": [
    {
      "errortype": "A0001",
      "errorstroke": {
        "0": "0.2",
        "1": "0.3"
      }
    },
    {
      "errortype": "A0021",
      "errorstroke": {
        "0": "0.2",
        "1": "0.3"
      }
    }
  ]
}

代码如下：

#include <iostream>
#include <vector>
#include <string>

#include "rapidjson/document.h"
#include "rapidjson/writer.h"
#include "rapidjson/stringbuffer.h"

using namespace rapidjson;
using namespace std;

int main() {

    string ret =
            "{\"ret\":\"101\",\"error\":[{\"errortype\":\"A0001\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}},{\"errortype\":\"A0021\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}}]}";
    rapidjson::Document doc;
    doc.Parse<kParseDefaultFlags>(ret.c_str());
    if (doc.HasMember("ret")) {
        string retjson = doc["ret"].GetString();
        for (unsigned i = 0; i < retjson.length(); ++i) {
            cout << retjson.at(i) << " ";
        }
    }
    cout << endl;
    if (doc.HasMember("error")) {
        const Value & errorjson = doc["error"];
        for (SizeType i = 0; i < errorjson.Size(); ++i) {
            // 或者这里可以换用一种遍历使用 Value::ConstValueIterator
            // http://rapidjson.org/md_doc_tutorial.html#QueryArray
            if (errorjson[i].HasMember("errortype")) {
                string errortype = errorjson[i]["errortype"].GetString();
                cout << "errortype: " << errortype << endl;
            }
            if (errorjson[i].HasMember("errorstroke")) {
                const Value & errorstroke = errorjson[i]["errorstroke"];
                cout << "errorstroke" << endl;
                for (Value::ConstMemberIterator iter = errorstroke.MemberBegin();iter != errorstroke.MemberEnd(); ++iter) {
                    cout << iter->name.GetString() << ": " << iter->value.GetString() << endl;
                }
            }
        }
    }

    return 0;
}

关于 RapidJSON 的更多内容可以参考官网。

boost property_tree

使用 boost 库中的 property_tree 解析如下：

/*
 first config your project to include /usr/local/include
 second link lib /usr/local/lib
 */

#include <iostream>
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>
#include <boost/foreach.hpp>
#include <string>

using namespace boost::property_tree;

int main(int argc, const char * argv[]) {

    std::string str_json = "{\"ret\":\"101\",\"error\":[{\"errortype\":\"A0001\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}},{\"errortype\":\"A0021\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}}]}";

    ptree pt;                       //define property_tree object
    std::stringstream ss(str_json);
    try {
        read_json(ss, pt);          //parse json
    } catch (ptree_error & e) {
        return 1;
    }

    std::cout << pt.get<std::string>("ret") << std::endl;
    ptree errortype = pt.get_child("error");            // get_child to get errors

    // first way
    for (boost::property_tree::ptree::iterator it = errortype.begin(); it != errortype.end(); ++it) {
        std::cout << it->first;
        std::cout << it->second.get<std::string>("errortype") << std::endl;
        ptree errorstroke = it->second.get_child("errorstroke");
        for (ptree::iterator iter = errorstroke.begin(); iter != errorstroke.end(); ++iter) {
            std::string key = iter->first;
            std::cout << iter->first << std::endl;
            std::cout << iter->second.data() << std::endl;
        }
    }

    // second way: using boost foreach feature
//    BOOST_FOREACH(ptree::value_type &v, errortype){
//        ptree& childparse = v.second;
//        std::cout << childparse.get<std::string>("errortype") << std::endl;
//        ptree errorstroke = childparse.get_child("errorstroke");
//        BOOST_FOREACH(ptree::value_type& w, errorstroke){
//            std::cout << w.first << std::endl;
//            std::cout << w.second.data() << std::endl;
//        }
//    }

    /*
     101
     A0001
     0
     0.2
     1
     0.3
     A0021
     0
     0.2
     1
     0.3
     */

    return 0;
}

2016-03-17 C++ , JSON , 经验总结 , rapidjson , boost

中国科技馆一日游

早上去的时候一大群熊孩子在外面排队吓得我差点想要放弃，其实后来才发现到的时候没有开馆，排了一会儿队就进去了，还是很快的。其实这个地方还只适合亲子去游玩，如果真的高中都毕业了，真的看到没有意思了，涉及到的一些物理，化学小道具都是课本上曾经存在过的实验。如果有机会未来带小孩来玩一玩还是挺不错的。

进门就能看到这只巨大的恐龙化石。

恐龙化石

去的时候直接从顶层往下逛的，馆中走道还有不少奥运的雕塑。

奥运雕塑1

奥运雕塑2

在上几层物理展馆中还是有不少有趣的玩意儿的，没拍多少照片，让我驻足的有如下的傅科摆，曾经屋里课本上学单摆的时候有看到过。当然傅科摆也间接地证明了地球的自转。物理那块区域的电生磁，磁生电，光等等区都是挺有趣的。

傅科摆

古代计时工具—-日晷。

日晷1

日晷2

最后走的时候在一层见到了很多中国古代天文，地理，木工等等的仪器和小工具，给我印象深刻的就是这个鲁班锁，用6块切割好的木块能够拼接成如图的形状。

鲁班锁

2016-03-12 经验总结 , beijing , travel , 游记

Goodbye Picasa

Google Photos 官网：http://googlephotos.blogspot.com/

Picasa Resources : https://sites.google.com/site/picasaresources/Home/Picasa-FAQ

这个网站整理了 Google Picasa Help Forum 中的很多问题，也解决了困惑我很久的问题，比如新 Google Photos 中相册的排序问题，比如 Google Photos 中分享出去照片自定义大小的问题，比如 Picasa Web Album 关闭之后的问题。

总之有关从 Picasa 平稳迁移到 Google Photos 的很多问题基本都能找到解决方案。

还有一个 Top Contributor 自己的网站： http://picasageeks.com/ 也是很棒，总结了各种经验。

虽然 Google 关闭 Picasa 来看，对长期使用 Picasa 的老用户来说是件悲痛的事情，就像当时 Google 关闭 Google Reader 一样。但是多少年过去了，可能新用户根本不知道曾经有一个 Google Reader 存在过。从公司的角度看关闭 Picasa 一心 Google Photos 当然也无口厚非，集中一心把一款产品打造好。只是从 Picasa 到 Google Photos 走得太快，以至于 Picasa Web Album 很多很实际的功能 Google Photos 一个都没有。而 Google Photos 一直在宣传的功能 Picasa 却很早就就拥有。这里本不想多说却还是依然写了这么多。

转到 Google Photos 本身这个产品，如果是新用户并且是移动设备使用时长较多的话，它本身是一款非常棒的产品： 1. 全备份（日期排序） 2. 简单修图工具 3. 相册以及好用的分享工具。单就这三点已经完全满足一个相册应该具备的功能了。而反过来真是因为在移动设备上的简单，以及没有对老用户的照顾，Google Photos 中的时间线，相册管理远远不及 Picasa。但是细想原本这两款产品针对的用户就是不一样的。

Picasa 这一款产品是一款云端相册，用来提供给用户分享照片，因此重在 Web ，以及相册管理
Google Photos 私人相册，云端相册，重在移动，重在备份，虽然也有分享功能却很弱。上面 Picasa Geeks 网站上有篇文章写得好，列举了 Google Photos 没有的功能。在 Web 上，缺乏排序功能，分享设置只有 Private 和 Public 两个选项，而 Picasa Web Album 有 Public，Limited(Anyone with link), Limited(Listed People), Private 四个选项，而这4个选项和 Google Drive 文件分享类似。希望 Google Photos 之后会把这些功能都添加上吧。

总之事情已经这样，结局无法改变，现在提前去适应一下 Google Photos 也好，不至于到时候慌乱。我关注的事情如下：

图片分享及直链

在之前的文章中我都是使用的 Picasa Web Album 分享出来的图片链接，Picasa 提供的免费无限图床真是赞到家，不仅没有流量限制，还能自定义大小。

比如下面两张照片，通过修改 s144-Ic42 参数就能够变换图片的大小，当然具体参数可以从这里查到。最常用的可能就是改 s0 获得原图了吧。

https://lh3.googleusercontent.com/-1vVMbu8s7d8/VlVQy4J3bDI/AAAAAAAA2vo/Npd_MTH-yLc/s144-Ic42/150724-pluto-hires.jpg

https://lh3.googleusercontent.com/-1vVMbu8s7d8/VlVQy4J3bDI/AAAAAAAA2vo/Npd_MTH-yLc/s800-Ic42/150724-pluto-hires.jpg

在 Picasa 关闭之后获取直链成为一个问题，我在 StackOverflow 上面的提问也没有任何实质性的解决。不过在后来的使用过程中发现，将照片分享到 Google+ ，这时 Google 会产生一个直接的图片 URL，点击看图片，并右击复制图片链接，就可以获取和 Picasa 分享类似的链接。

相册及分享

这要从很久很久以前说起，我原先的照片管理一直依照相册来管理，比如今天可能拍了很多照片，我会以日期-活动，例如 160311-Event 来命令相册然后通过合适的分享途径分享出去，如果我想使用某张照片到博客中，获取直链并添加到博客配图即可。可是在 Google+ Photos 时代，Google 就彻底搞乱了我的相册管理方法。Picasa 中被莫名其妙的添加了很多的相册。自此之后相册管理体系彻底崩溃，没有了清晰的相册管理，现在我已经不管相册了，按照 Google Photos 给我的时间流排布照片，适当的时候将图片添加到相册中。其他时候基本上放任 Google Photos 自己备份。

在 Google Photos App 中即使我想分享一个相册我首选的也是讲照片内容传到 Google+ ，并不会优先使用 Google Photos 的分享功能，所以至今为止，我的 Share 相册中也只有当时测试使用过的一个相册。

测试帖如上

关于容量

可能让我唯一开心一点的就是 Picasa 到 Google+ Photos 到 Google Photos 的容量变成了无限大。其实听到这个消息的时候，我的相册容量已经到到了10G，当时正愁怎么办呢。随之后面的改变就已经很吸引人了，从 Google+ 时代的 2048*2048 像素以下不算空间，到现在 Google Photos 的16MP 下不算空间，几乎已经是无限容量的节奏了，我手机最高像素也没这么大。。

最后的吐槽，真的不想管这个了，改来改去太累了。

2016-03-11 Google , Picasa , Google Photos , Blogger , 经验总结 , 产品体验

排序算法

排序算法复习，插入排序，选择排序，冒泡排序，希尔排序，[[归并排序]]，堆排序，快排。

关于排序算法的 stable 稳定性，排序保存原始数据顺序则稳定，否则不稳定。

关于原址排序，算法需要额外的空间计算或者保存数据， in-place sorting ，归并排序为非原址排序 not-in-place sorting。

关于时间复杂度，归并排序，堆排序，快排有相对较快的速度 O(n*log(n))

稳定性

排序前后两个相等的数的相对位置不变。

有一些排序算法天然是稳定的，比如 Insertion Sort, Merge Sort, Bubble Sort。

为什么需要有稳定性？

加入有一组英文名，包括 First Name 和 Last Name，要求先按照 Last Name(姓) 排序，然后按照 First Name （名）排序，这个时候可以先排序 First Name (稳定或非稳定)，然后按照稳定的排序算法排序 Last Name，这样就可以保证排序完成之后，就是最终的结果。

插入排序

每次取一个元素插入正确的位置，适合少量元素。对于未排序的数据，从已排序的序列中从后向前扫描，找到相应的位置插入，实现上通常使用 in-place 排序，只需要使用额外 O(1) 空间，但是因为插入正确的位置之后，需要反复移动已经排序的序列，为新元素提供插入空间，因而比较费时。

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤 2~5

Algorithm

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--)
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

Java 版本：

static void insert_sort(int[] array) {
    for(int i = 1; i < array.length; ++i) {
        int cur = array[i];
        for(int j = i - 1; j >= 0 && array[j] > cur; j--) {
            array[j + 1] = array[j];
            array[j] = cur;
        }
    }
}

Properties

Stable
O(1) extra space
O(n^2^) comparisons and swaps
Adaptive: O(n) time when nearly sorted
Very low overhead

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

# 升序
# 从第二个元素开始，每次循环将前 i 个元素排序
for i in range(1,len(list)):
    value = list[i]
    j = i-1
    # 将第 i 个元素的位置腾出
    while j >= 0 and list[j]>value:
        list[j+1] = list[j]
        j=j-1
    # 在排完序的 list[0...i] 中将值插入合适位置
    list[j+1]=value

# 降序
list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

for i in range(len(list)-1, -1, -1):
    value = list[i]
    j=i+1
    while j<len(list) and value < list[j]:
        list[j-1] = list[j]
        j=j+1
    list[j-1]=value

print(list)

选择排序

每次选取数组中最小（或者最大）的元素，并将其与未排序数组中首元素交换，依次进行。

选择排序拥有最小的交换次数，适合交换元素开销比较大的情况。选择排序其他情况都比较低效。

Algorithm

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

Properties

Not stable
O(1) extra space
Θ(n^2^) comparisons
Θ(n) swaps
Not adaptive

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

for i in range(0,len(list)):
    k = i
    for k in range(i+1, len(list)):
    # 没有完全按照定义写，不过这样交换的开销更大。
        if list[k] < list[i]:
            list[i], list[k] = list[k], list[i]

print(list)

Java 版：

static void selection_sort(int[] array) {
	if(array.length <= 1) return;
	for(int i = 0; i < array.length; i++) {
		int smallest = i;
		for(int j = i + 1; j < array.length; j++) {
			if (array[j] < array[smallest]) {
				smallest = j;
			}
		}
		int temp = array[i];
		array[i] = array[smallest];
		array[smallest] = temp;
	}
}

冒泡排序

[[冒泡排序]] 反复交换相邻未按次序排列的元素，一次循环之后最大的元素到数组最后。

Algorithm

for i = 1:n,
    swapped = false
    for j = n:i+1,
        if a[j] < a[j-1],
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

Properties

Stable
O(1) extra space
O(n^2^) comparisons and swaps
Adaptive: O(n) when nearly sorted

Example

def bubble_sort_1(list):
    for i in range(0, len(list)):
        for j in range(1, len(list)-i):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]

def bubble_sort_2(list):
    for i in range(0, len(list)):
        swap = False
        for j in range(len(list)-1, i, -1):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]
                swap = True
        if swap is False:
            break

相较于第一种直接冒泡，设定标志优化冒泡。

Java 版

static void bubble_sort(int[] arr) {
	int i, j, temp, len = arr.length;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}

希尔排序

分组插入排序，将数组拆分成若干子序列，由增量决定，分别进行直接插入排序，然后缩减增量，减少子序列，最后对全体元素进行插入排序。插入排序在基本有序的情况下效率最高。

Algorithm

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

Properties

Not stable
O(1) extra space
O(n^3/2^) time as shown (see below)
Adaptive: O(n·lg(n)) time when nearly sorted

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

def insertion_sort(k,h,n):
    """
    :param k: group count
    :param h: step length
    :param n: total
    :return:
    """
    for i in range(k+h, n, h):
        value = list[i]
        j = i-h
        while j >= 0 and list[j]>value:
            list[j+h] = list[j]
            j=j-h
        list[j+h]=value


h = 1       # step length
while h < len(list):
    h = 3*h +1

while h > 0:
    h = int(h / 3)
    for k in range(0, h):           # devide into k groups
        insertion_sort(k, h, len(list))

print(list)

归并排序

[[归并排序]] 是一个典型的分治算法，将数组分成两个子数组，在子数组中继续拆分，当小组只有一个数据时可认为有序，之后合并，所以重点就到了合并有序数组。

Algorithm

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

Properties

Stable
Θ(n) extra space for arrays (as shown)
Θ(lg(n)) extra space for linked lists
Θ(n·lg(n)) time
Not adaptive
Does not require random access to data

Example

From wiki

from collections import deque

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    def merge(left, right):
        merged,left,right = deque(),deque(left),deque(right)
        while left and right:
            merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
        merged.extend(right if right else left)
        return list(merged)

    middle = int(len(lst) // 2)
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)

堆排序

利用最大堆的性质，堆性质，子结点的值小于父节点的值。每次将根节点最大值取出，剩下元素进行最大堆调整，依次进行。

Algorithm

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

Properties

Not stable
O(1) extra space (see discussion)
O(n·lg(n)) time
Not really adaptive

Example

def max_heapify(lst, i):
    """
    下标为 i 的根节点调整为最大堆
    :param lst:
    :param i:
    :return:
    """
    l = 2 * i + 1
    r = 2 * (i + 1)
    if l < len(lst) and lst[l] > lst[i]:
        largest = l
    else:
        largest = i
    if r < len(lst) and lst[r] > lst[largest]:
        largest = r
    if largest != i:
        lst[i], lst[largest] = lst[largest], lst[i]
        max_heapify(lst, largest)


def build_max_heap(lst):
	"""
    建立最大堆
    """
    for i in range((len(lst)-1)/2, 0, -1):
        max_heapify(lst, i)


def heap_sort(lst):
    build_max_heap(lst)
    ret = []
    for i in range(len(lst)-1, -1, -1):
        ret.append(lst[0])
        lst.remove(lst[0])
        max_heapify(lst, 0)
    return ret

L = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
R = heap_sort(L)
print(R)

快排

从数列中挑出元素，将比挑出元素小的摆放到前面，大的放到后面，分区操作。然后递归地将小于挑出值的子数列和大于的子数列排序。

Algorithm

# choose pivot
swap a[1,rand(1,n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]

Properties

Not stable
O(lg(n)) extra space (see discussion)
O(n^2^) time, but typically O(n·lg(n)) time
Not adaptive

Example

list_demo = [2,8,7,1,3,5,6,4]

def partition(lst, p, r):
    """
    划分
    :param lst: 待排序数组
    :param p: 起始下标，子数组第一个元素
    :param r: 终止下标，子数组最后一个元素 r < len(lst)
    :return: 划分结果下标
    """
    if r >= len(lst) or p < 0:
        return
    x = lst[r]
    i = p - 1
    for j in range(p, r):
        if lst[j] <= x:
            i += 1
            lst[i], lst[j] = lst[j], lst[i]
    lst[i+1], lst[r] = lst[r], lst[i+1]
    return i + 1


def quick_sort(lst, p, r):
    if p < r:
        q = partition(lst, p, r)
        quick_sort(lst, p, q-1)
        quick_sort(lst, q+1, r)

quick_sort(list_demo, 0, len(list_demo)-1)
print(list_demo)

分配排序

箱排序

箱排序也称桶排序 (Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录 R[0]，R[1]，…，R[n-1]，把关键字等于 k 的记录全都装入到第 k 个箱子里（分配），然后按序号依次将各非空的箱子首尾连接起来（收集）。对于有限取值范围的数组来说非常有效，时间复杂度可以可达 O(n). 例如给人年龄排序，人的年龄只能在 0~100 多之间，不可能有人超过 200, 适用桶排序。

箱排序中，箱子的个数取决于关键字的取值范围。若 R[0..n-1] 中关键字的取值范围是 0 到 m-1 的整数，则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。
箱子的类型应设计成链表为宜一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。
为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

桶排序的平均时间复杂度是线性的，O(n), 但是最坏的情况可能是 O(n^2)

基数排序

基数排序是非比较排序算法，算法的时间复杂度是 O(n). 相比于快速排序的 O(nlgn), 从表面上看具有不小的优势。但事实上可能有些出入，因为基数排序的 n 可能具有比较大的系数 K. 因此在具体的应用中，应首先对这个排序函数的效率进行评估。

基数排序的主要思路是，将所有待比较数值（注意，必须是正整数）统一为同样的数位长度，数位较短的数前面补零. 然后，从最低位开始，依次进行一次稳定排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

这个算法的难度在于分离数位，将分离出的数位代表原元素的代表，用作计数排序。但是分离数位不能脱离原来的数字，计数排序的结果，还是要移动原元素。

注意计数排序的元素数值与位置的联系，引申到基数排序的从元素得到中间值然后与位置的联系。

枚举排序

通常也被叫做秩排序 (Rank Sort) ，算法基本思想是：对每一个要排序的元素，统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置，时间复杂度为 O（n^2）

reference

2016-03-09 c++ , sort , algorithm , python

每天学习一个命令：nslookup 查询调试 DNS

最近配置路由器 pdnsd，经常需要调试 DNS 信息，就离不开调试工具了。 nslookup 用来查询 DNS 记录，查看域名解析是否正常，经常被用来在网络故障时诊断网络问题。

命令

在 Ubuntu 下可以使用如下命令安装：

sudo apt install dnsutils

格式：

   nslookup [-option] [name | -] [server]

使用

nslookup 是一个查询 Internet domain name server 的工具，nslookup 有两种模式：

interactive 交互模式
non-interactive 非交互模式

交互模式

进入交互模式，总共有两种方法。

第一种方法，直接输入 nslookup 命令，不加任何参数，则直接进入交互模式，此时 nslookup 会连接到默认的域名服务器（即 /etc/resolv.conf 的第一个 dns 地址）。

第二种方法，是支持选定不同域名服务器的。需要设置第一个参数为“-”，然后第二个参数是设置要连接的域名服务器主机名或 IP 地址。

如果你直接在 nslookup 命令后加上所要查询的 IP 或主机名，那么就进入了非交互模式。当然，这个时候你也可以在第二个参数位置设置所要连接的域名服务器。

例子

交互模式下查询域名

nslookup
> www.douban.com
Server:	127.0.1.1   // 连接的 DNS 服务器
Address:	127.0.1.1#53    // DNS 服务器 IP 地址与端口

Non-authoritative answer:    // 非权威答案，从连接的 DNS 服务器本地缓存中读取，非实际查询得到
Name:	www.douban.com
Address: 115.182.201.6    // IP 地址
Name:	www.douban.com
Address: 115.182.201.7
Name:	www.douban.com
Address: 115.182.201.8

交互模式下更改 DNS

进入交互模式之后，使用 server dns-server 来改变上连 DNS 服务器地址

查询域名 IP 地址

nslookup www.douban.com [dns-server]

如果没有指定 dns-server，使用系统默认的 DNS 服务器。

2016-03-09 linux , command , nslookup , dns , network

中国美术馆一日游

本来打算去的自然博物馆，可无奈去官网看的时候已经没有预订票，于是就去了中国美术馆。北京来了快6年而似乎该去的博物馆都尚未能去，想接下来的时间里能不能用自己的脚都走遍，用自己的眼睛都看遍。借用网友的一句话，“不能也不敢说自己懂艺术，只是单纯的喜欢，喜欢美，喜欢不同的表达，喜欢安静的可以欣赏思想与灵感的地方”。上一次画画还要追溯到初中，近十年时间没有接触任何艺术，也没有接受任何艺术形式的熏陶。在最初进入的时候确实是一头雾水，幸而我们这一次去的时候正好是中华民族大团结全国美术作品展，至少还有一个主题让我们可以想象。虽然进门看到如此主旋律的主题有点失望，然而从一个展厅进到另一个展厅，除了进门见到的习大大有点恶心之外，渐渐就开始敬佩起这些画家。

喜欢画画的人可以经常上美术馆的官网看看，不定期的会举办一些展览。

下面是三幅震撼到我的画：

朝鲜族

这原本是一副很大的画，这里的两位只是画的一小部分，记得画的左边还有一位在回眸，右边也还有两位。

一家人

远看真的像是一副照片，细节部分也是栩栩如生，近看脸部的文理，光影的处理着实让我震惊了。

口爱的小狗

被萌到的小狗，哈士奇？不认识。

其他令我印象深刻的画作：

塔吉克新娘官网

美术馆馆藏作品链接

很遗憾，写这篇文章的时候中途忘记保存了，漏掉了一些内容，现在凭感觉补了一些，却再也找不到当时的感觉，虽然只仅仅相隔一天。由此可见随时保存的重要性了。

2016-03-05 经验总结 , beijing , travel , 游记

Tweets by einverne

常见用法

建表时字段区分大小写

查询区分大小写

配置表名大小写不敏感

reference

RapidJSON

boost property_tree

图片分享及直链

相册及分享

关于容量

稳定性

为什么需要有稳定性？

插入排序

Algorithm

Properties

Example

选择排序

Algorithm

Properties

Example

冒泡排序

Algorithm

Properties

Example

希尔排序

Algorithm

Properties

Example

归并排序

Algorithm

Properties

Example

堆排序

Algorithm

Properties

Example

快排

Algorithm

Properties

Example

分配排序

箱排序

基数排序

枚举排序

reference

命令

使用

交互模式

例子

交互模式下查询域名

交互模式下更改 DNS

查询域名 IP 地址

电子书

本站提供服务

文章分类

最近文章