推荐网站之邮件签名: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*lg(n))

插入排序

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

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

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤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

中国美术馆一日游

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

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

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

朝鲜族

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

一家人

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

口爱的小狗

被萌到的小狗,哈士奇?不认识。

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

塔吉克新娘 官网

美术馆馆藏作品链接

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


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

几道 C++ 问题

Question 6

Method overriding is key to the concept of Polymorphism. 覆盖是多态的核心 True

多态可以概括成“一个接口,多个方法”,运行时决定调用函数。C++ 多态利用虚函数实现,虚函数允许子类重新定义方法,子类重新定义方法的做法称为“覆盖”,或者重写。(直接覆盖成员函数和覆盖虚函数,只有重写了虚函数的才能算作是体现了C++ 多态性)

封装可以使得代码模块化,继承可以扩展已存在的代码,而多态的目的则是为了接口重用。也就是说,不论传递过来的究竟是那个类的对象,函数都能够通过同一个接口调用到适应各自对象的实现方法。

最常见的用法就是声明基类的指针,利用该指针指向任意一个子类对象,调用相应的虚函数,可以根据指向的子类的不同而实现不同的方法。如果没有使用虚函数的话,即没有利用C++多态性,则利用基类指针调用相应的函数的时候,将总被限制在基类函数本身,而无法调用到子类中被重写过的函数。因为没有多态性,函数调用的地址将是一定的,而固定的地址将始终调用到同一个函数,这就无法实现一个接口,多种方法的目的了。

#include <iostream>  
using namespace std;  

class A  
{  
public:  
    void foo()  
    {  
        printf("1\n");  
    }  
    virtual void fun()  
    {  
        printf("2\n");  
    }  
};  
class B : public A  
{  
public:  
    void foo()  
    {  
        printf("3\n");  
    }  
    void fun()  
    {  
        printf("4\n");  
    }  
};  
int main(void)  
{  
    A a;  
    B b;  
    A *p = &a;  
    p->foo();  
    p->fun();  
    p = &b;  
    p->foo();  
    p->fun();  
    return 0;  
}  

输出
1 2
1 4

基类指针指向基类对象,调用基类函数;基类指针指向子类对象, p->foo() 指针是个基类指针,指向是一个固定偏移量的函数,因此此时指向的就只能是基类的foo()函数的代码了,因此输出的结果还是1。而p->fun() 指针是基类指针,指向的fun是一个虚函数,由于每个虚函数都有一个虚函数列表,此时p调用fun()并不是直接调用函数,而是通过虚函数列表找到相应的函数的地址,因此根据指向的对象不同,函数地址也将不同,这里将找到对应的子类的fun()函数的地址,因此输出的结果也会是子类的结果4。

上面例子,还有一种问法

B *ptr = (B *)&a;  ptr->foo();  ptr->fun();

输出
3 2

从原理上来解释,由于B是子类指针,虽然被赋予了基类对象地址,但是ptr->foo()在调用的时候,由于地址偏移量固定,偏移量是子类对象的偏移量,于是即使在指向了一个基类对象的情况下,还是调用到了子类的函数,虽然可能从始到终都没有子类对象的实例化出现。而ptr->fun()的调用,可能还是因为C++多态性的原因,由于指向的是一个基类对象,通过虚函数列表的引用,找到了基类中fun()函数的地址,因此调用了基类的函数。由此可见多态性的强大,可以适应各种变化,不论指针是基类的还是子类的,都能找到正确的实现方法。

“隐藏”是指派生类的函数屏蔽了与其同名的基类函数,规则如下: (1)如果派生类的函数与基类的函数同名,但是参数不同。此时,不论有无virtual 关键字,基类的函数将被隐藏(注意别与重载混淆)。 (2)如果派生类的函数与基类的函数同名,并且参数也相同,但是基类函数没有virtual 关键字。此时,基类的函数被隐藏(注意别与覆盖混淆)。

纯虚函数,virtual ReturnType Function()= 0;

C++支持两种多态性:编译时多态性,运行时多态性。

  • 编译时多态性:通过重载函数实现
  • 运行时多态性:通过虚函数实现。

虚函数是在基类中被声明为virtual,并在派生类中重新定义的成员函数,可实现成员函数的动态覆盖(Override) 包含纯虚函数的类称为抽象类。由于抽象类包含了没有定义的纯虚函数,所以不能定义抽象类的对象。

Q16

Which objected oriented design concept is key to the factory design pattern?

Inheritance

Q23

Which of the following describe the C++ programming language?

Compiled Declarative

Q25

The friend keyword is used to grant access to private class members. True

  1. 友元函数:普通函数对一个访问某个类中的私有或保护成员。
  2. 友元类:类A中的成员函数访问类B中的私有或保护成员。

友元函数

friend <类型><友元函数名>(<参数表>);  

友元函数只是一个普通函数,并不是该类的类成员函数,它可以在任何地方调用,友元函数中通过对象名来访问该类的私有或保护成员

#include <iostream>
using namespace std;

class Base{
public:
    Base(int _data):data(_data){};

    friend int getData(Base& _base);
private:
    int data;
};

int getData(Base& _base){
    return _base.data;
}

int main() {
    Base b(2);
    std::cout << getData(b) << endl;
    return 0;
}

友元类

friend class <友元类名>;

友元类的声明在该类的声明中,而实现在该类外。

#include <iostream>
using namespace std;

class Base{
public:
    Base(int _data):data(_data){};

    friend class FClass;
private:
    int data;
};

class FClass{
public:
    int getData(Base _base){
        return _base.data;		// call friend class private data
    }
};

int main() {
    Base b(2);
    FClass c;
    cout << c.getData(b) << endl;
    return 0;
}

Q38

Choose word or words to describe UML language.

  • Picture
  • Relational
  • Interpreted
  • Abstract
  • None of the answers are correct.

只有 Picture 正确

The Unified Modeling Language (UML) is a general-purpose, developmental, modeling language in the field of software engineering, that is intended to provide a standard way to visualize the design of a system.

为啥没有 Relation 有点神奇~ UML 图能够看出类与类的关系的啊

Q40

Generalization is used by UML to describe Inheritance and the deriving of one class from another.

Generaliztion 是从属关系,可以表示继承,或者派生

http://www.uml-diagrams.org/generalization.html

Q44

#include <iostream>

void f0(int& sum){
    sum = 3+2*7;
}

int main() {
    int *p, sum = 0;
    (*p)++;
    sum = sum * 3;
    f0(sum);
    std::cout << sum << ",";
    return 0;
}

(*p)++ 一行有问题

具体问题内容请看这里


2016-03-03

Nexus 6 刷机及电信 3G/4G 破解

adb and fastboot

从 Android 开发官网下载 Android SDK,从事过 Android 开发的应该知道 adb 和 fastboot 工具,在完整 SDK 中这两个工具在 platform-tools 文件夹下。如果想要方便的使用这两个工具,可以将文件路径加入到系统环境变量中,这样以后就可以在任何目录使用 adb 和 fastboot 命令。

flash factory image

救砖,或者在 recovery 下没有备份又无法开机的情况下只能刷回原厂镜像救砖机。因此折腾需谨慎,刷机前请一定使用 recovery 备份系统及数据。可以从 Google 官网下载镜像。

下载镜像

https://developers.google.com/android/nexus/images#shamu

解压之后应该会有如下文件

bootloader-shamu-moto-apq8084-71.15.img  2016/01/06  07:19        10,636,288
flash-all.bat                            2016/01/06  07:19               985
flash-all.sh                             2016/01/06  07:19               856
flash-base.sh                            2016/01/06  07:19               814
image-shamu-mmb29q.zip                   2016/01/06  07:19     1,009,825,337
radio-shamu-d4.01-9625-05.32+fsg-9625-02.109.img      2016/01/06  07:19       118,272,512

解锁bootloader

解锁 bootloader 会抹去手机一切内容,需谨慎,总之只需要一句命令

 fastboot oem unlock

然后利用音量键及电源键来确认解锁 bootloader, 之后运行

 fastboot reboot

重启手机。

刷镜像

  1. 关机并进入 fastboot 也就是 bootloader模式,在关机状态下,同时按住“电源键”+“音量下”
  2. 数据线连接手机与电脑,在驱动安装正确之后
  3. 执行 flash-all.bat (Windows 下) 或者 flash-all.sh (MAC或者 Linux 下)
  4. 等待执行完毕,手机恢复成出厂镜像

root

root 工具及教程来自 @Chainfire ,在此由衷的感谢他。

  • 下载ZIP工具
  • 解压文件,并将手机进入 bootloader/fastboot 模式
  • 连接数据线,并运行 root-windows.bat (Windows 下)或者 chmod +x root-linux.sh 并运行 root-linux.sh (Linux下) Mac下同Linux

Recovery

第三方的 Recovery 有以下的功能:

  • Wipe your phone’s data (Factory reset) and cache
  • Make, restore and manage backups of your phone’s operating system and software
  • Mount, unmount and format your phone’s internal as well as external storage partitions
  • Install a custom ROM or application from a zip file to your phone
  • Wipe Dalvik cache and battery statistics
  • Make logs for error reporting and debugging

刷入 recovery

  • 官网 下载 Nexus 6 TWRP 的 recovery 文件
  • 进入 bootloader/fastboot 模式
  • 执行以下命令

    fastboot flash recovery recovery.img

    recovery.img 即下载的 Recovery 镜像。

  • 利用音量键选择 recovery ,点击电源键选择,可以进入 “Recovery Mode”.

安装完 recovery 之后就能够快速的备份系统,恢复出厂设置,恢复备份数据,刷入新ROM,刷入ZIP

kernel

一张图解释什么是 kernel

android kernel

Nexus 6 第三方的 kernel 有很多选择 比如 franco.kernel,这里推荐 ElementalX,有如下功能

  • Easy installation and setup with Aroma installer
  • overclock/underclock CPU
  • user voltage control
  • Advance color control
  • MultiROM support
  • optional USB fastcharge
  • optional sweep2wake and doubletap2wake
  • optional sweep2sleep
  • sound control
  • init.d support
  • NTFS r/w and exFAT support
  • option to disable fsync
  • adjustable vibration
  • does not force encryption

安装 ElementalX kernel

  • ElementalX 官网下载,并保存到手机
  • 进入 Recovery Mode
  • 刷入 ZIP ,选择下载的文件,安装

Nexus 6 破解电信3G/4G

6.0.1 (MMB29Q) 有效

下载文件,教程中需要用的软件及文件 https://yunpan.cn/cxCaHyqkKPwg9 提取码 db02

  • DFS
  • QPST

还有这里

  • moto x qc diag interface - 64bit.zip
  • carrier_policy.xml

具体步骤参考nexus6破解电信教程

简单来说破解4G步骤:

  • 用QPTS工具里面的EFS Explorer, 添加/policyman/carrier_policy.xml,nexus6 默认没有这个文件
  • 进入BP TOOLS模式,安装好后,必须确认好你的设备管理器 端口(COM和LPT)中BP驱动的端口号
  • 从开始菜单中,打开QPST configuration
  • 先点Ports标签,然后点Add New Prot 输入你的设备端口号
  • 点StartClient菜单中的EFS Explorer选项
  • 连接上手机后,在EFS 根目录创建policyman目录
  • 把carrier_policy.xml(见附件)拖进policyman目录中
  • 完成后重启手机

破解完成后请在手机拨号面板那输入 *#*#4636#*#* 看下首选网络是不是LTE/GSM/CDMA auto(prl)

参考


2016-03-01 Android , Nexus 6

Linux 启动项管理

Linux 启动项管理

Debian/Ubuntu/Linux Mint 系利用 update-rc.d 来管理 Linux 自启动服务。RedHat/Fedora/CentOS 下貌似有一个 chkconfig 来管理。

而我使用的 Linux Mint 自带的启动服务管理配置地址在 ~/.config/autostart 目录下。

Linux 中的服务通常利用 /etc/init.d/ 目录下的脚本进行启动,停止或者重新加载等操作。一般情况下如果安装完服务之后,该服务会自动启动。比如安装完 apache2 之后, apache 服务会在下次启动时自动启动。如果不需要 apache2 随机启动,可以你禁用自启动,然后在需要的时候手动的启动 apache 服务

# /etc/init.d/apache2 start

先看一下启动脚本的内容

# ls -l /etc/rc?.d/*apache2
lrwxrwxrwx 1 root root 17 Feb  5 21:47 /etc/rc0.d/K09apache2 -> ../init.d/apache2
lrwxrwxrwx 1 root root 17 Feb  5 21:47 /etc/rc1.d/K09apache2 -> ../init.d/apache2
lrwxrwxrwx 1 root root 17 Feb  5 21:47 /etc/rc2.d/K09apache2 -> ../init.d/apache2
lrwxrwxrwx 1 root root 17 Feb  5 21:47 /etc/rc3.d/K09apache2 -> ../init.d/apache2
lrwxrwxrwx 1 root root 17 Feb  5 21:47 /etc/rc4.d/K09apache2 -> ../init.d/apache2
lrwxrwxrwx 1 root root 17 Feb  5 21:47 /etc/rc5.d/K09apache2 -> ../init.d/apache2
lrwxrwxrwx 1 root root 17 Feb  5 21:47 /etc/rc6.d/S09apache2 -> ../init.d/apache2

运行级别(run level) 从 0,1到6,在每一个链接前有K和S区别,K 表示 Kill 停止一个服务,而 S 表示 Start 启动一个服务。

不同的运行级别定义如下:

# 0 - 停机
# 1 - 单用户模式
# 2 - 多用户,没有 NFS
# 3 - 完全多用户模式(标准的运行级)
# 4 – 系统保留的
# 5 - X11 (x window)
# 6 - 重新启动

Debian (Ubuntu/Linux Mint)

rcconf

Debian 系Linux下利用 rcconf 管理自启动脚本,rcconf的全称是 Debian Runlevel Configuration tool, 运行级别配置工具。作用和 update-rc.d 类似,但是更加直观简洁。他是一个 TUI(Text User Interface)。

rcconf

sudo apt-get install rcconf
sudo rcconf

运行之后就会出现非常直观的配置界面,用方向键,空格,Tab就能够实现配置。如果熟悉命令依然可以通过 rcconf 命令来进行快速配置。

update-rc.d

如果想要完全禁止 apache2 服务,需要删除 /etc/rcX.d/ 目录下所有的链接,而使用 update-rc.d

# update-rc.d -f apache2 remove

添加自启动服务

# update-rc.d apache2 defaults
Adding system startup for /etc/init.d/apache2 ...
/etc/rc0.d/K20apache2 -> ../init.d/apache2
/etc/rc1.d/K20apache2 -> ../init.d/apache2
/etc/rc6.d/K20apache2 -> ../init.d/apache2
/etc/rc2.d/S20apache2 -> ../init.d/apache2
/etc/rc3.d/S20apache2 -> ../init.d/apache2
/etc/rc4.d/S20apache2 -> ../init.d/apache2
/etc/rc5.d/S20apache2 -> ../init.d/apache2

从上面的log中可以看到,默认的优先级是20(K和S后面数字)和 91 有很大区别。 S20 链接早于 S91 启动, K91 在 K20 之前停止。

如果想要 apache2 服务以 91 优先级启动或者停止,可以使用

# update-rc.d apache2 defaults 91
Adding system startup for /etc/init.d/apache2 ...
/etc/rc0.d/K91apache2 -> ../init.d/apache2
/etc/rc1.d/K91apache2 -> ../init.d/apache2
/etc/rc6.d/K91apache2 -> ../init.d/apache2
/etc/rc2.d/S91apache2 -> ../init.d/apache2
/etc/rc3.d/S91apache2 -> ../init.d/apache2
/etc/rc4.d/S91apache2 -> ../init.d/apache2
/etc/rc5.d/S91apache2 -> ../init.d/apache2

如果需要为启动和停止设置不同的优先级,则可以

# update-rc.d apache2 defaults 20 80
Adding system startup for /etc/init.d/apache2 ...
/etc/rc0.d/K80apache2 -> ../init.d/apache2
/etc/rc1.d/K80apache2 -> ../init.d/apache2
/etc/rc6.d/K80apache2 -> ../init.d/apache2
/etc/rc2.d/S20apache2 -> ../init.d/apache2
/etc/rc3.d/S20apache2 -> ../init.d/apache2
/etc/rc4.d/S20apache2 -> ../init.d/apache2
/etc/rc5.d/S20apache2 -> ../init.d/apache2

这样启动为20,停止为80. 而如果需要自定义不同的运行级别,则可以

# update-rc.d apache2 start 20 2 3 4 5 . stop 80 0 1 6 .
Adding system startup for /etc/init.d/apache2 ...
/etc/rc0.d/K80apache2 -> ../init.d/apache2
/etc/rc1.d/K80apache2 -> ../init.d/apache2
/etc/rc6.d/K80apache2 -> ../init.d/apache2
/etc/rc2.d/S20apache2 -> ../init.d/apache2
/etc/rc3.d/S20apache2 -> ../init.d/apache2
/etc/rc4.d/S20apache2 -> ../init.d/apache2
/etc/rc5.d/S20apache2 -> ../init.d/apache2

如此之后,在运行级别 2, 3, 4, 5 为S20 ,运行级别 0, 1, 6 则是 K80.

同样可以更加复杂

# update-rc.d apache2 start 20 2 3 4 . start 30 5 . stop 80 0 1 6 .
Adding system startup for /etc/init.d/apache2 ...
/etc/rc0.d/K80apache2 -> ../init.d/apache2
/etc/rc1.d/K80apache2 -> ../init.d/apache2
/etc/rc6.d/K80apache2 -> ../init.d/apache2
/etc/rc2.d/S20apache2 -> ../init.d/apache2
/etc/rc3.d/S20apache2 -> ../init.d/apache2
/etc/rc4.d/S20apache2 -> ../init.d/apache2
/etc/rc5.d/S30apache2 -> ../init.d/apache2

RedHat/Fedora/CentOS

chkconfig

sudo chkconfig --add apache2

or

sudo chkconfig -- level 35 apache2 on

关于 chkconfig 更多的用法可以参考这里

reference


2016-02-09 linux , 学习笔记

Genymotion 安装

在Linux下安装 Genymotion Android 模拟器。最近拾起 Android Development,Android 模拟器必不可少,用来用去 Genymotion 模拟器算是速度和效率最棒的模拟器了。

事前准备

Genymotion 依赖 VirtualBox 运行,在安装之前确保已经安装 VirtualBox. 在Linux Mint下直接去 Software Manager 搜索 VirtualBox 然后点击安装即可。

Genymotion 安装需要一个 Genymotion 的个人账号,Genymotion 高级功能需要付费,所以去官网注册一个个人账号使用。 官网地址:https://www.genymotion.com

下载安装包,在注册账号登陆之后去首页按照自己的系统选择 32bit 或者 64bit 的安装包下载。目前最新的版本为 2.6.0.

安装

假设安装包下载到 ~/Downloads 目录下,在终端:

# cd ~/Downloads/
# Move the downloaded file to ~/Android/ directory #
mv genymotion-2.6.0_x64.bin ~/Android/

# Set executable permission
chmod +x genymotion-2.6.0_x64.bin

# Install genymotion by running the file
./genymotion-2.6.0_x64.bin

# Navigate into genymotion directory
cd genymotion

# launch the genymotion #
./genymotion

运行 genymotion 之后,添加设备,此时需要登陆账号,有的时候会遇到 “unknown generic error” 错误,在我的观察下可能就是因为 genymotion 服务器挂了,等些时候再尝试即可。或者有的时候是因为代理的关系。

unknown generic error

下载对应的镜像,然后就能够运行模拟器了。

为了方便使用可以将 Genymotion 的地址加入到 PATH 中,这样就能快速启动 Genymotion. 类似:

$ PATH=$PATH:/home/einverne/Android/genymotion/

使用

在使用 Genymotion 的时候,有时会遇到 ”INSTALL_FAILED_NO_MATCHING_ABIS“ 错误。一些时候是因为 APP 和模拟器CPU架构的问题,但是在 Genymotion 这里需要额外安装一个文件。点击这里 去xda 下载 Genymotion-ARM-Translation_v1.1.zip 这个文件。并拖到模拟器中。这样就不会出现问题了。如果需要在模拟器中安装 GApps ,可以在上面的链接中找到对应的方法。

如果使用过程中出现 “An error occured while deploying the file. INSTALL_FAILED_CPU_ABI_INCOMPATIBLE” 这样的错误,利用上面的方法也能解决。造成这个错误的原因是因为 Genymotion 是一个基于 x86 的虚拟环境,不是一个 ARM 的模拟器。而 Genymotion 在更新过程中移除了 ARM Translation 和 Google Play Apps , 这样对开发者和使用者造成了一定的困扰,不过还好依然可以通过其他方法解决。

reference


2016-02-08 Android , AndroidDev , Genymotion

Google+

最近文章

  • 使用 pyenv 管理 Python 版本 记录一下使用过程,留备以后使用。
  • 电影网站评分机制 年前的时候喉舌媒体批评豆瓣,猫眼等评分太低影响了票房,而导致16年的年度票房目标没有达到,广电很生气,后果很严重。可是豆瓣存在了那么多年,那么多的电影,在院线上映的,还是不上映的,从来也没有听说过 IMDB 或者 烂番茄的评分会影响到总体的票房。虽然得分的多少或多或少的会对票房有所影响,可这难道是豆瓣,或者 IMDB 或 烂番茄这样的影评网站应该承担的责任吗? 制片公司,发行商,甚至细化到导演,演员,剧本,在国内甚至可以拉上审查来负责,动不动删掉个14分钟,谁还愿意花了冤枉钱去大荧幕看一个不完整的片子呢?真正的影迷 大概会愿意花个机票钱去看一个完整版吧。
  • Openwrt 平均负载 Openwrt 在 Luci 后台很显眼的位置有三个不断刷新的数字,其实这个数字是“平均负载”(Load Average)的意思,这是 Linux 操作系统衡量系统负载和稳定性的重要参数。
  • Openwrt 设置 在上一篇中讲了如何刷Openwrt,这一篇主要讲一些 Openwrt 的东西,以及配置相关的内容。我有一个主路由器,设置分配的局域网地址为 192.168.1.x,给内网中分配的地址也是 192.168.1.x 开头。
  • TP LINK MR12U 刷 openwrt 今天翻箱倒柜竟然找出了我的 TP-LINK MR12U,很早之前因为3G上网卡而买的便携式路由,突然脑袋一热,干嘛不试试刷个 Openwrt 呢。记得当时是没有支持的,但是一搜竟然发现了 Openwrt 有官方支持了。于是开始动手。