Verne in GitHub

排序算法

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

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

切换 Linux 内核版本

Linux 内核是开源类 Unix 系统宏内核。仅仅一个内核并不是一套完整的操作系统。有一套基于 Linux 内核的完整操作系统叫作 Linux 操作系统。Kernel 是 Linux 系统的核心，主要负责硬件的支持。

Linux 内核提供了安全补丁， bugfix 和新特性。

Linux 内核在 GNU 通用公共许可证第 2 版之下发布。

修改启动内核版本需要谨慎，每一步在确认知道自己在做什么的情况下再操作。Linux 内核版本变更可能导致网络访问异常，声音异常，甚至是桌面环境无法启动。在安装和移除内核时，确保已经已经阅读过相关帮助，确保自己知道如何选择不同版本的内核，如何恢复之前的版本，以及如何检查 DKMS 状态。

Linux 内核版本号的意义

Linux 内核版本号由 3 组数字组成：第一个组数字。第二组数字。第三组数字

  • 第一个组数字：目前发布的内核主版本。
  • 第二个组数字：偶数表示稳定版本；奇数表示开发中版本。
  • 第三个组数字：错误修补的次数。

查看内核版本

在 Linux 机器上执行如下命令查看当前正在使用的内核版本

uname -r

使用如下命令查看当前系统安装的内核版本

dpkg -l | grep linux-image

如果使用的是 Linux Mint 那么在 Update Manager 中，选择 View -> Linux Kernels 可以查看当前安装的版本和正在使用的版本，或者选择安装新的版本切换。

安装和卸载内核版本

sudo apt search linux-image
sudo apt install xxx
sudo apt-get purge xxx

选择内核版本

一个系统可以同时安装多个内核，但是运行时只能选择一个，当启动电脑时，在显示 grub 菜单时可以选择加载哪一个内核。（当只有一个系统安装时，grub 菜单可能被跳过，强制显示 grub 菜单可以在启动电脑时一直按住 Shift 按键）

在 Advanced options 选项中，可以选择系统上安装的内核版本，在启动时选择一个即可。

DKMS

DKMS 全称是 Dynamic Kernel Module Support，它可以帮我们维护内核外的这些驱动程序，在内核版本变动之后可以自动重新生成新的模块。

sudo apt-get install dkms

内核包含了所有的开源驱动，一般都可以正常工作，私有的驱动（DVIDIA，AMD，Broadcom… 等等）不包含在其中。这些私有驱动（proprietary drivers）需要在安装时手动编译到每一个内核中。这个操作可以用 dkms 来完成。如果私有驱动无法正常编译到内核中，可能导致启动异常，所以需要提前检查

dkms status

reference


2016-03-02 linux , kernel , versions

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 命令速查手册》读书记录。

系统

uname -a               # 查看内核 / 操作系统 /CPU 信息
head -n 1 /etc/issue   # 查看操作系统版本
cat /proc/cpuinfo      # 查看 CPU 信息
hostname               # 查看计算机名
lspci -tv              # 列出所有 PCI 设备
lsusb -tv              # 列出所有 USB 设备
lsmod                  # 列出加载的内核模块
env                    # 查看环境变量

资源

监视系统资源，包括跟踪正在运行的程序 （ps，top）终止进程（kill），列出打开的文件（lsof），报告系统内存占用（free），磁盘空间占用（df，du）等等。

ps aux                  # 查看系统正在运行的进程
ps -ef                  # 查看所有进程
ps f                    # 查看进程树
top                     # 实时显示进程状态
kill -9 PID             # 终止正在运行的进程 -9 强制中断， -15 正常中止
lsof                    # 列出打开的文件
free -m                 # 查看内存使用量和交换区使用量
df -h                   # 查看各分区使用情况
du -sh 《目录名》        # 查看指定目录的大小
grep MemTotal /proc/meminfo   # 查看内存总量
grep MemFree /proc/meminfo    # 查看空闲内存量
uptime                  # 查看系统运行时间、用户数、负载
cat /proc/loadavg       # 查看系统负载

磁盘和分区

mount | column -t      # 查看挂接的分区状态
fdisk -l               # 查看所有分区
swapon -s              # 查看所有交换分区
hdparm -i /dev/hda     # 查看磁盘参数（仅适用于 IDE 设备）
dmesg | grep IDE       # 查看启动时 IDE 设备检测状况

网络

这里列举了常用和网络相关的命令，包括查看本地 IP（ifconfig），判断网络连通性（ping，traceroute) 等等。其中 ifconfig, iwconfig ，route 等等命令都有双重用途，不仅能够查看网络连接属性，也能够进行配置。

ifconfig               # 查看所有网络接口的属性
ifup eth0              # 开启网络
ifdown eth0            # 关闭 eth0 网卡
iwconfig               # 查看无线接口属性
iptables -L            # 查看防火墙设置
ping                   # 网络连通性
route -n               # 查看路由表
netstat -lntp          # 查看所有监听端口
netstat -antp          # 查看所有已经建立的连接
netstat -s             # 查看网络统计信息
traceroute https://google.com  # 显示数据包从计算机路由到指定的主机经过的每一步
mtr                    # traceroute 更好的代替
host                   # 查看网站 DNS 结果
dhclient -r eth0       # 使用 DHCP 获得新网络地址

mtr 使用介绍

用户

w                      # 查看活动用户
id 《用户名》            # 查看指定用户信息
last                   # 查看用户登录日志
cut -d: -f1 /etc/passwd   # 查看系统所有用户
cut -d: -f1 /etc/group    # 查看系统所有组
crontab -l             # 查看当前用户的计划任务

服务

chkconfig --list       # 列出所有系统服务
chkconfig --list | grep on    # 列出所有启动的系统服务

2016-03-01 commands , linux , network , cpu , collection

每天学习一个命令：multitail 同时监控多个日志

MultiTail是一个开源的ncurses的实用工具，可用于在一个窗口或单一外壳，显示实时一样的尾巴命令，该命令拆分控制台为更多子窗口的日志文件的最后几行（很像显示多个日志文件到标准输出屏幕命令 ）。 它还支持颜色突出显示，过滤，添加和删除窗口等。

他和tail的区别就是他会在控制台中打开多个窗口，这样可以同时监控多个日志。

安装

apt install multitail

如果要在 CentOS，基于 Red Hat 的发行版中使用，需要开启 EPEL repository，然后安装

yum install -y multitail

使用

监控两个日志文件，窗口上下

multitail /var/log/syslog /var/log/auth.log

如果要让窗口左右排布

multitail -s 2 /var/log/syslog /var/log/auth.log

同理，-s num 来表示后接多少个文件

进入 multitail 之后，有一些交互式命令

  • h 来打开帮助
  • 使用 b 来选择打开的文件，使用上下键选择文件，一旦选择文件 multitail 会显示文件最后 100 行，使用 jk 移动光标，或者 gg/G 来快速移动到文件顶部或者最后，q 退出
  • a 用来添加另外的监控日志文件

reference


2016-02-24 multitail , tail , linux , command , log

Google Guava 中本地缓存 LoadingCache 使用

Cache 在实际场景中有着非常广泛的使用，通常情况下如果遇到需要大量时间计算或者获取值的场景，就应当将值保存到缓存中。Cache 和 ConcurrentMap 类似，但又不尽相同。最大的不同是 ConcurrentMap 会永久的存储所有的元素值直到他们被显示的移除，但是 Cache 会为了保持内存使用合理，而配置自动将一些值移除。

通常情况下，Guava caching 适用于以下场景：

  • 花费一些内存来换取速度
  • 期望一些 key 会被不止一次被调用
  • 缓存内容不会缓存超过内存空间的值，Guava caches 不会存储内容到文件，或者到服务器外部，如果有此类需求考虑使用 Memcached 类似工具

Cache 通过 CacheBuilder 类的 Builder 模式获取：

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
       .maximumSize(1000)
       .expireAfterWrite(10, TimeUnit.MINUTES)
       .removalListener(MY_LISTENER)
       .build(
           new CacheLoader<Key, Graph>() {
             public Graph load(Key key) throws AnyException {
               return createExpensiveGraph(key);
             }
           });

如果使用的场景中对应着 key 的值有默认的值，那么可以选择使用 CacheLoader，如果没有默认值，那么仍然可以原子的 get-if-absent-compute 方法，在 get 方法中提供一个 Callable，或者元素也可以通过 Cache.put 来直接插入到缓存中。

LoadingCache

LoadingCache 是一个附加着 CacheLoader 的 Cache。LoadingCache<K,V> 在 Guava 中是一个 interface，通常是用来本地 Cache 缓存 k-v 数据，value 会一直保存在内存中直到被移除或者失效。实现这个接口的类期望是线程安全的，能够安全的在多线程程序中被访问。

当第一次调用 get() 方法时，如果 value 不存在则会触发 load() 方法，load 方法不能返回 null，否则会报错。

get() vs getUnchecked()

最正统的查询 LoadingCache 的方法是调用 get(k) 方法，这个方法如果查询到已经缓存的值会立即返回，否则使用缓存的 CacheLoader 自动加载一个新值到缓存并返回。因为 CacheLoader 可能会抛出异常，那么如果有异常，则LoadingCache.get(k) 会抛出 ExecutionException 异常。而如果 CacheLoader 抛出 unchecked 未检查的异常，则 get(k) 方法会抛出 UncheckedExecutionException 异常。

此时可以选择使用 getUnchecked(k) 方法，这个方法会将所有的异常包装在 UncheckedExecutionException 异常中。需要注意的是，如果 CacheLoader 声明了检查异常，也就是 CacheLoader 显式的定义了异常，就不能调用 getUnchecked(k) 方法

定时回收

CacheBuilder 在构建 Cache 时提供了两种定时回收的方法

  • expireAfterAccess(long, TimeUnit) 缓存项在给定时间内没有被读或写访问，则回收
  • expireAfterWrite(long, TimeUnit)：缓存项在给定时间内没有被写访问（创建或覆盖），则回收

reference


2016-02-24 google , guava , cache , local-cache , java

使用 certbot 自动生成 SSL 证书并自动续期

Let’s Encrypt 是一个免费 SSL 证书发行项目，自动化发行证书，证书有 90 天的有效期。于是有了另外一个项目可以自动安装，自动续期。

直接上网站

选择 WEB 服务器版本，系统版本，然后执行脚本即可。

执行完成之后执行 certbot run 跟着步骤就行了。

在 crontab -e 编辑文件

0 0 1 * * /usr/bin/certbot renew --force-renewal

定时每天检查，如果要过期则自动延期。


2016-02-23 certbot , ssl , https

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 , 学习笔记

电子书

文章分类

最近文章

  • MySQL 中的日志配置和管理 MySQL 中默认是没有开启日志记录的，所以需要手动修改配置文件开启日志。而在 MySQL 中我们需要关心的有三类日志：
  • Java 查漏补缺之：ThreadLocal 使用 ThreadLocal 线程本地变量，每个线程保存变量的副本，对副本的改动，对其他的线程而言是透明的。
  • 为知笔记导出和备份 WizNote 已经用了好几年，虽然也一直在续费，但总感觉将死不死，基于整理这几年近 4000 条的笔记的目的，也一方面为迁移出 WizNote 的目的，研究一下 WizNote 笔记导出和备份的方法。
  • Nginx location 匹配规则 之前的关于 Nginx Config 的文章是当时看 Nginx 书记录下来的笔记，很大略，没有实际操作，等终究用到 location 的时候发现还是有很多需要注意的问题，比如匹配的优先顺序，比如 root 和 alias 的区别等等，所以单独拿一篇文章来记录一下目前遇到的问题，并来解决一下。
  • koajs 简单使用 Koa 是一个背靠 Express 的团队设计的全新的 Web 框架，旨在使之成为一个更轻量，更丰富，更加 robust 的基础框架。通过促进异步方法的使用，Koa 允许使用者抛弃 callback 调用，并且大大简化了错误处理。Koa 并没有将中间件绑定到核心代码，而是提供了一组优雅的方法让编写服务更加快速，通过很多第三方的扩展给 Koa 提供服务，从而实现更加丰富完整的 HTTP server。