排序算法

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

关于排序算法的 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

django web framework 学习笔记

这两天大概看了一下Python的web框架—-Django,顺带复习一下Python。从刚开始的一无所知,到现在对Django中MVC的一些了解,感觉收获颇丰,还顺带回想起来以前学习过程中的一些MVC的知识,虽然Django不是完全按照MVC的命名模式 Model,View,Controller,但是它依然遵循类似的开发模式,Django自己说自己是 MTV 模式, Model,Template,View。

在看 Django 之前也了解了一些 Python 的Web框架,在之前的写字应用中用 webpy 作了一个简单的接口,webpy 实现很简单,用它当然也能做一些大项目,但是可能需要自己Custom的东西比较多。而Django可以快速上手。

Installation

安装非常简单,先安装 virtualenv

$ pip install virtualenv
$ cd my_project_folder
$ virtualenv .			# create virtual env in current folder
$ source bin/activate

再安装 Django , 创建工程,然后就可以开工了。

$ pip install django  	# install latest version
# pip install django==1.9 或者指定某一版本
# pip install django --upgrade
$ django-admin startproject projectname

几个很常用的命令,在 manage.py 目录下:

$ python manage.py help
$ python manage.py runserver [port]
$ python manage.py makemigrations # 每一次修改 model 之后需要运行,之后需要运行 migrate
$ python manage.py migrate   # 已经代替了 python manage.py syncdb 数据库相关,创建表
$ python manage.py createsuperuser
$ python manage.py startapp appname

几个文件

几个文件解释:

  • models.py 和数据库表相关

    model 中需要用到的 Field ,关键字:[Model field reference]

  • views.py 显示相关

    处理HttpRequest请求,通过模板生成HTML网页返回

  • urls.py 匹配URL模式

    通过正则匹配请求URL,将对应URL导向相应的view。Django 1.9 中可以引用三种对应的URL匹配模式,Function views,Class-based viewsIncluding another URLconf 方式来定义URL。

  • settings.py 项目设置

    项目地址,安装应用,数据库,静态文件地址,等等都在此文件中配置。

学习方式

我觉得最好的教程就是官方的Getting started with Django,但是唯一的坏处就是不够视频直观,这个时候上 Google 搜Django tutorial 能够找到很多视频教程,先行入门之后,再去回头看官方的教程或者文档,会很轻松的加快学习进度。

个人觉得几个很重要的文档,在新建 model 的时候, Django 自带了一些 Field, 这些变量的定义直接影响到数据库中保存的数据,在我刚开始学习的时候经常查看Model field reference. 在定义完 model 之后需要执行 python manage.py makemigrationspython manage.py migrate 来同步自定义的 model 和 数据库中内容。

在 view 中需要 render 模板的时候,常用的方式就是在 工程下app 的同级目录增加 templates 目录,将html模板放到该目录下。并且需要在 settings.py 文件中 TEMPLATES 设置中增加 'DIRS': [os.path.join(BASE_DIR, "templates")],. 可以参考 官方文档 .

而接下来是网页的表单,可以自定义表单,也可以通过 Model 直接生成对应的表单,官方都有详细的介绍。

至此生成一个自己的简单页面应该没有任何问题了。下面就是学习一些深入的内容,在之前的视频中有用到 django-registration-redux 一个第三方的注册登陆的实现。能够快速实现一个网站的注册邮箱验证以及登录验证。然后因为 Django 生成的网页表单太丑,所以还用了 django-crispy-forms 这样一个第三方生成表单的应用。快速生成带CSS样式的表单。具体的使用看文档都能够快速使用。

到此,可以看一些教程实现一些自定义的表单 validation,可以看一下第三方应用的实现来充实一下自己的 django 知识,甚至可以实现一个具体的应用来锻炼一下。

参考

  • 官方参考 其中有很详细的文档、教程、已经一些基本的网页应用实现,缓存,分页,RSS,消息,Sessions 等等
  • YouTube 教程 一步一步教你用 Django 实现一个简单的个人博客。

2016-01-31 Django , Python , 学习笔记 , Web

boost 学习笔记 11:总结

至此boost一本书基本看完,很多内容粗略的扫过,大概知道了boost的能力,书中最后的总结很好,不仅指出boost的作用,同时把boost 力所不能及的地方指明,并且给了相应的解决方案。如此当遇上相同的需求时就能够快速的找到对应的解决方案。

boost 的缺点:没有达到 Java 和 Python 标准库“包罗万象”的程度:没有 GUI 库,没有 RPC 库,没有 COM+ CORBA 支持……

RPC是指远程过程调用,也就是说两台服务器A,B,一个应用部署在A服务器上,想要调用B服务器上应用提供的函数/方法,由于不在一个内存空间,不能直接调用,需要通过网络来表达调用的语义和传达调用的数据。

推荐书目

  • 设计模式 可复用面向对象软件的基础
  • C++标准程序库 自修教程与参考手册
  • C++ 语言的设计与演化
  • C++ Primer 第三版
  • Effective C++
  • Effective STL
  • C++网络编程 卷 1 运用 ACE 和模式消除复杂性
  • C++网络编程 卷 2 基于 ACE 和框架的系统化复用
  • C++ STL 中文版
  • UNIX 网络编程 第1卷 套接口 API
  • Python 简明教程

2016-01-18 boost , C++

boost 学习笔记 10:设计模式

设计模式是一个面向对象的通用解决方案,是一套被反复使用,多数人知晓的代码设计经验总结。

一般分为:创建型模式、机构型模式和行为模式

创建型模型

抽象工厂 Abstract Factory

提供统一的创建接口。

生成器 Builder

将复杂对象的构建与表示分离,使得同样的构建过程可以创建不同的表示。

工厂方法

定义接口用于创建对象。

原型 Prototype

原型模式使用类的实例通过拷贝的方式创建对象,具体的拷贝行为可以定制。最常见的用法为类实现一个 clone() 成员函数,这个函数创建一个与原型相同或者相似的新对象。

单件 Singleton

运行时,类有且仅有一个实例。

结构性模型

如何组合类或者对象,更而形成更大更有用的新对象。

适配器 Adapter

把一个类的接口转换成另一个接口,在不改变原有代码的基础上复用原代码。

桥接 Bridge

将抽象部分与实现部分分离,使它们都可以独立的变化。

组合 Composite

将小对象组合成树形结构。

装饰 Decorator

运行时动态地给对象增加功能。

外观 Facade

为系统中大量对象提供一个一致的对外接口,简化系统使用。

享元 Flyweight

使用共享的方式节约内存的使用

代理 Proxy

它的意图不是改变接口插入新系统(适配),也不是为对象增加职责(装饰),而是要控制对象。

智能指针库,利用代理模式将原始指针包装,代理原始指针的职能。

行为模式

职责链 Chain of Responsibility

把对象连成一条链,使链上的每个对象都有机会处理请求。

命令 Command

将一个请求封装为一个对象,从而使你可用不同的请求对客户进行参数化。

解释器 Interpreter

给定一个语言, 定义它的文法的一种表示,并定义一个解释器, 该解释器使用该表示来解释语言中的句子。

迭代器 Iterator

提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。

中介者 Mediator

包装了一系列对象相互作用的方式,使得这些对象不必相互明显作用,从而使它们可以松散偶合。当某些对象之间的作用发生改变时,不会立即影响其他的一些对象之间的作用,保证这些作用可以彼此独立的变化。

备忘录 Memento

备忘录对象是一个用来存储另外一个对象内部状态的快照的对象。备忘录模式的用意是在不破坏封装的条件下,将一个对象的状态捉住,并外部化,存储起来,从而可以在将来合适的时候把这个对象还原到存储起来的状态。

观察者 Observer

定义对象间一对多的联系,当一个对象的状态发生变化时,所有与它有联系的观察者对象都会得到通知。

状态 State

允许对象在状态发生变化时行为也同时发生改变。

策略 Strategy

封装不同的“算法”,使它们可以在运行时相互替换。

模板 Template method

模板方法模式准备一个抽象类,将部分逻辑以具体方法及具体构造子类的形式实现,然后声明一些抽象方法来迫使子类实现剩余的逻辑。不同的子类可以以不同的方式实现这些抽象方法,从而对剩余的逻辑有不同的实现。先构建一个顶级逻辑框架,而将逻辑的细节留给具体的子类去实现。

访问者 Visitor

分离类的内部元素和访问它们的操作,可以在不改变内部元素的情况下增加作用于它们的新操作。

其他模式

空对象

用于返回无意义的对象时,它可以承担处理null的责任。

包装外观

通过外观的包装,使应用程序只能看到外观对象,而不会看到具体的细节对象,这样无疑会降低应用程序的复杂度,并且提高了程序的可维护性。

前摄器模式 Proactor

用于为异步事件多路分离和分派处理器的对象行为模式


2016-01-18 boost , C++

国家博物院一日游

说了很久想去国家博物院,只是迟迟没有动脚,终于熬到今天。本不是旅游旺季,早上9点出门到那边依然能够领到票进去,排队人数也不是很多,几乎就是去了拿票直接进。如果想要预约门票的话,提早电话或者网上预定,可参见官网文章

去的时候没有查攻略,也没有看任何文章,进到博物馆才发现那边这么大,一时间竟然不知道从那边逛起,幸而查了一眼马蜂窝,看到有人建议到地下一层从《古代中国》开始看。于是开始一段非常漫长的游览史,不是知道是因为走得太慢还是看的太认真,当走到“三国魏晋南北朝”开始已经开始寻找座位想要快速结束这段旅程了。而此后一遍又一遍的感慨中国历史太长,沉浸其中容易无法自拔。

参观的时候没有导游,所以大部分时间就是在读文物的介绍,然后自己维基百科查看,夏商周时候那些青铜器皿,几乎没有知道作用的,于是和小伙伴开始了异想天开,这是洗澡用的,这是喝酒用的,等等,不过倒也知道了一些知识:

  • ”匜“,拼音yí,是先秦的礼器,客人洗手之用。当时还在讨论,如果是,盛水,洗手器,为什么不写成半包围,中间加个手字,多形象
  • 瓦当,已经忘记了在哪个朝代看到的了,后来查看维基才知道,发明于战国时期的鲁班。是屋檐最前面的圆形瓦片,古人会在上面雕刻图案或者神兽。
  • 知道了三国中的魏国并不是曹操建立的,而是他儿子废了汉,看三国的时候没注意呢。
  • 知道了竹林七贤,除了嵇康,阮籍之外多记住了一个刘伶,其他的还是没记住
  • 知道了原来王守仁就是王阳明,他的书法还很不错

后来的后来真的没怎么看了,几乎都是快速浏览过,就这样快速的走过,光是看了一个到1912年的《古代中国》,走出展厅就已经到了下午,后来休息了一下,又粗粗的看了书法展,国博建筑概览就匆匆过去了,很多展厅也没去看,总之以后有机会再过去看看吧。以后有了小孩,应该做好充分的准备工作再去看看,回来之后看到维基上列举的一些国家级文物,印象是有的,只是当时也没有仔细的看,四羊方尊,金缕玉衣,等等当时历史教科书中存在的图片展现到眼前是还是会激动一下的。只是后来倦于拍照片,回来整理也就只几张。

给后人的参考,其之前可以大概的浏览这个维基页面,在其中的古代中国中,列举了一些文物,有一些还是很值得一看的。比如远古时期的”人面鱼纹彩陶盆“,”玉琮“等等;夏商周的青铜器;秦汉的兵马俑,石刻;到后期的瓷器等等。

人面鱼纹彩陶盆 人面鱼纹彩陶盆

大禹治水 大禹治水图

四羊方尊 著名的四羊方尊

金边玉杯 金边玉杯,得此一杯,此生足矣

金制头饰 金制头饰,匆匆路过,突然看到这个饰品,太美了。

可爱的神兽 可爱的神兽,没想到古人也是挺萌的嘛

又一只萌萌的神兽 又一只萌萌的神兽

说不上名字的青铜器 说不上名字的青铜器,已经忘了他叫什么了,应该也是尊吧。

请工作人员不要这么摆设啊,会吓死人的 最后!!!请工作人员不要这么摆设啊,会吓死人的


2016-01-17 博物院 , travel , beijing , 游记 , 经验总结

Google+

最近文章

  • vim presentation 大纲
  • Vim 寄存器 Vim 的寄存器可以看成 Vim 中额外用来存储信息的区域,虽然看不见,但是如果使用 x, s, y, p 等等命令的时候都无意识的使用到了 Vim 的寄存器(register).
  • vim normal 命令 替换::%s/^/#/g visual block:ggI# 注释第一行后用.重复执行每一行 我们可以在第三种方法之上用normal命令实现上述需求,步骤:
  • Vim 中的宏命令 Vim 的设计哲学中有这样一句话:”if you write a thing once, it is okay. However if you’re writing it twice or more times, then you should find a better way to do it”.
  • headless chrome puppeteer Headless 最早的时候在 PhantomJS 听说过这个概念,后来在 GitHub 各种项目中总有人不断提起这个概念,而最新看到的新闻便是 Chrome 开始支持 Headless,也正激起了我了解的欲望。