最近看了一个问题，涉及到质数的判断。以前没有留意过这方面的方法。但是特意找了下资料发现自己解决这个问题的方法还是很笨的，网上有许多更好的方法。这里做个简单的总结。

生成质数表

首先最笨的办法是生成一个表来判断。以前上离散数学的时候讲过可以用筛法求这个表。把这个表先算出来显然是很划算的。但是，生成这个表也有好和不好的方法。

Eratosthenes筛法

给出要筛数值的范围\(\sqrt(n)\)，然后把范围内2的倍数划去，然后找到第一个没被划去的数。再把这个数的倍数划去，然后再找第一个没被划去的数，如此重复。。。

欧拉筛法

这个方法比上一个筛法要快很多。原因是上一个算法会重复筛某些数（尽管标记为已经筛除，但是还是要判断）。比如说6会被2和3筛去。这个方法主要思想就是每个合数只被最小的质因数筛掉。

void gen(){
    for(int i=2; i<=N; i++){
        if(!check[i]){//没被划去的i，是质数
            prime[total++]=i;
            isPrime[i] = true;
        }
        for(int j=0; j<total; j++){
            int t = i*prime[j];//i和之前所有的质数相乘
            if(t>N)break;
            check[t] = true;//筛掉
            if(i%prime[j]==0)break;
            //保证了每个合数只会被它的最小素因子筛掉
        }
    }//end enum
}

上面代码prime是保存质数的，而isPrime是一个标记数组。查表判断就靠isPrime了，N是范围。

只生成一部分质数表

上面的方法尽管高效但是浪费空间，而且要判断的数字比较大的时候，事先要准备一个比较大的表，计算起来也是比较费事的。折衷的方法是生成一部分表。表内的最大质数为可能检测的最大数的平方根。这样小于平方根的直接判断，大于平方根的可以从表头循环检查能否整除待检测的数。

拉宾-米勒测试

这种方法不用生成表。但是给出的结果不一定准确。多次测试的话，可以减小误判的概率。详细的介绍见链接

# 博客使用Mathjax

update(2020-10-18): hexo+next主题参考这里

测试公式：

$a = b + c $

\[\frac{\partial u}{\partial t} = h^2 \left( \frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} + \frac{\partial^2 u}{\partial z^2}\right)\]

公式的inline插入方法外面套2个美元符号会居中，1个则不居中。就像上面的公式一样。

开学这几天读Thinking in Java（新学期教材），正好顺便总结Java相对于C++的一些差异。太明显的语言差异就不写了（比如所有东西都放在类里，没有全局变量之类的）。另外，这不是一个总结Java或C++特性的文章，所以两者当中很多各自独有的特性是没有总结的。，

# 语言特性

• java没有运算符重载。
• 没有goto
• 可以break和continue到某个标签。但是标签后不能跟语句。常用来中断多层循环。
• 增加for each循环
• 没有const关键字，final表示不可更改的量（对基本类型可看作常量，对对象而言则是引用不能指向其他对象，但被指对象是可以修改的）。
• if、for、while等的判断条件中必须使用boolean类型，类似while(1)之类的是不允许的。

# 基本数据类型和变量

• Java的char是16位，8位的是byte
• 没有无符号类型
• short、int、liong分别是16、32、64位
• 内部大括号变量名不能覆盖外面同名变量。所以内层大括号不能有和外层变量同名的变量。
• 非基本类型的比较用equals()方法。小心String，Integer这些。
• boolean型不能被转化为其它类型。
• 数组声明时不能指定大小（类似int a[100];是不可行的），必须在声明后new出对象时给出new对象的个数，从而给出数组大小（int a[]=new int[100];）。
• java的数组是一个对象，它持有某种特定类的引用。直接new 对象[n]得到的是一个内置n个null引用的对象，若是基本类型则自动为0，多维数组同理。c++相同代码将自动调用无参数的构造函数生成对象。
• 多维数组中同一维上的各个数组可以不等长。C++必须利用指针数组和动态内存分配实现不等长数组。

# 运算符

• 增加无符号右移操作>>>和>>>=，高位补0.
• 没有sizeof()，因为无论什么平台，java的数据类型长度都是一样的。
• 不能在赋值语句里用连续的逗号（如：a=1,2,3;）。而且不能用逗号分开语句。

# 对象初始化和清除

• 不支持构造函数的初始化列表（但是可以把类内部对象的初始化代码看作初始化列表）。
• Java自己的构造方法调用自身其他构造方法必须以：this(参数列表); 的方式调用，且必须在构造方法开始处。C++只需：new (this)类名(参数列表); 就可以调用，且位置随意。
• 静态方法调用是：类名.方法， 而C++则是：类名::方法。
• Java类内有static代码块。里面内容只执行1次，在该类第一个对象生成或首次访问其静态成员时执行。
• java类内非static代码快在对象被new出来时执行，C++类内部不能写代码。所以java非static代码块可在任意处。
• java的static成员在类内直接指定初始化值，C++的static成员在类外和main外的全局区域（类型名 类名::static成员名=xxx）。
• java的方法内不能有静态变量（和内存布局有关，静态变量在data区，而方法内的属于栈区，只能存放基本类型和引用，见链接）
• java可以在类的定义里为变量赋初值，C++不行。
• Java会把类定义里变量赋初值工作放在类的代码最前面（在构造方法调用前就执行）。且初始化顺序和定义顺序相同。

# 类特性

• 增加反射机制
• 没有多重继承（但可以实现多个接口类，或者用多个内部类替代）
• Java的内部类定义位置随意，C++的必须把内部类定义放在使用内部类之前的地方。
• java的static成员只能new被static修饰的内部类，C++没有static内部类，static方法可以直接new内部类。
• C++内部类不能直接访问外部类的成员。但java可以。
• 没有友元
• 只有公共继承（extends关键字）
• 基类方法被重载后，如果在子类中重新定义这个方法不会屏蔽任何一个在基类中的版本。
• java类内的protected成员可以被同一个包内的类访问。C++类的protected成员不能被一个名字空间的类访问。所以名字空间=包的想法是不对的。
• 增加final关键字阻止覆盖方法。被指定为final的类型不能被继承。
• 重写方法自动是动态绑定的，不像C++需要virtual关键字。
• java向下转型会检查对象实际是不是被转到的类型。C++不检查。
• 增加abstract关键字，修饰方法（等价于C++纯虚函数），修饰类（这种类含有abstract方法，等价于C++抽象类）。
• 增加接口（Interface），但是接口无构造方法，接口内方法自动为public，且内部变量自动为static。C++纯虚类可以有构造方法，非静态成员等等。

# 异常处理

• C++没有finally关键字
• C++可以throw和函数的异常说明列表不同的异常，java则必须抛出和异常说明表相同的异常。
• 两者都可以在main里抛出异常，但C++的main不能有throw列表。

# 泛型

• java的泛型参数类型不能为基本类型。
• 定义java的泛型函数（方法）的泛型参数列表要放在返回值之前。C++需要用template<class T>
• 对函数（方法）显示地进行类型说明时：java在 . 操作符和方法之间插入尖括号说明（类内部用this.），C++是在方法名和参数列表之间放尖括号。
• java的父类容器存放子类，可以从容器中取出对象调用子类方法，C++的STL容器中始终调用父类方法（甚至用虚函数也是）。
• Java在泛型代码内部无法获得任何有关泛型参数的类型信息。
• Java中，若泛型参数为T，不能new T()。原因见上一条。
• java中增加了C++没有的通配符‘?’（注意? super 和? extends的用法）。

# 其它

• java的String是不可变的，C++的string可变。

以上只是初步的总结，如果总结的有问题请留下评论。大概以后还会更新这篇文章。

使用KNN算法，需要找到样本点周围最近的N个点。最简单的方法是求出所有距离，然后找出前K大。然而点的数量巨大时，计算量会非常大。为了优化KNN算法，可以采用kd-tree（k维树）。它可以在各个维度的空间内对较大量的点进行检索。

kd树是二叉树，构造过程简单来说就是不断用垂直于坐标轴的超平面将k维空间切分，构成许多超矩形区域。每个节点都对应一个超平面，这个超平面过节点中存储的点并且将k维空间分成两部分。

平衡kd树的构建是递归的，每次选择一个区间内的中位数大（后面解释）的点为根节点，然后中位数点左侧和右侧区间递归这个构建过程。直到区间大小为一。

中位数大的点就是指如果按照一定规则给点排序，排序后下标是中位数的那个点（中间的那个点）。构建kd树时给某区间点的排序规则是：位于第x层的节点比较第(x%k+1)维坐标的大小。比如：如果是构建整个树的根节点，则所有点都参与排序，比较的是它们的第一维的大小。位于中间的点就是根节点。

查询前n近的算法简单来说就是：用一个大小位n的大顶堆保存前n近的点。先从根节点出发找到给定点所在空间对应的kd树的叶子节点，并且在找这个点的时候把路途经过的点加入堆里。如果堆满了，而且新经过的点离待查询点更近一些，那就把堆顶的点去掉，并添加进这个点（注意新的点不一定还在堆顶）。这时候，堆中所有点都包含在以给定点为圆（球）心，以给定点到堆顶点为半径的圆（球）内。之后从叶子节点一层层返回，每到一层的一个父节点，就看另一个叶子节点所在的区域是不是与这个圆相交。如果相交说明这一侧可能有更近的点，那么就进入这一侧搜寻更近的点。

查询过程也可以用递归实现。判断与圆（球）相交的方法：圆（球）心到超平面的距离小于半径。

在网上看到的资料大多没有简单的代码，而且缺少注释。许多代码是复制一个开源C++库的，作为学习来说源代码的结构有点复杂，不太适合学习。维基上有更详细的解释和许多有用的学习资料连接，而且有python版的实现。

为了自己实现一个简单的kd树练练手，我从网上搜了一道杭电OJ上的题。对于KNN算法来说很实用的题目，要求就是给一些点，找离目标点前M近的点。只涉及树的建立和查询。

这道OJ题的代码：

#include <bits/stdc++.h>

using namespace std;

#define MAX_DIM 5
#define DIS(X) ((X)*(X))

int n_dim;    //当前所比较的维度，分割面分割的维度

struct Point{
    int coord[MAX_DIM]; //坐标
    Point *lft, *rgt;   //树的左右节点指针

    Point(int k){
        lft=rgt=NULL;
        for(int i=0; i<k; i++)
            scanf("%d", &coord[i]);
    }

    Point(){
        lft=rgt=NULL;
    }

    inline bool operator<(const Point &b)const{
        return coord[n_dim]<b.coord[n_dim];
    }
};

struct kdTree{
    vector<Point> allp; //全体点
    priority_queue<pair<double, Point*> > *resultq; //查到的点
    int dim;    //空间的维度
    Point *root;    //树根指针

    kdTree(int n, int k){
        resultq=NULL;
        root=NULL;
        dim=k;
        for(int i=0; i<n; i++){
            allp.push_back(Point(k));
        }
        build(0, allp.size()-1, 0, root);
    }

    void query(int m, Point &p){
        Point res[20];
        resultq=new priority_queue<pair<double, Point*> >;
        queryInner(p, m, 0, root);
        //给出查询结果
        printf("the closest %d points are:\n", m);
        for(int n=0; !resultq->empty(); n++){
            res[n]=*(resultq->top().second);
            resultq->pop();
        }
        for(int n=m-1; n>=0;n--){
            for(int i=0; i<dim; i++)
                printf("%d%c", res[n].coord[i], i==dim-1?'\n':' ');
        }
        delete resultq;
        resultq=NULL;
    }

    void build(int l, int r, int dep, Point* &rt){
        if(l>r)return;
        int mid=(l+r)>>1;
        n_dim=dep%dim;  //存储分割面分割的是那个维度
        nth_element(allp.begin()+l, allp.begin()+mid, allp.begin()+r+1);

        rt=&allp[mid];  //把空间的点接到树上
        build(l, mid-1, dep+1, rt->lft);
        build(mid+1, r, dep+1, rt->rgt);
    }

    void queryInner(Point &p, int m, int dep, Point *rt){
        if(rt==NULL)return;
        pair<double, Point*> tmp=make_pair(0.0, rt); //计算到被查点的距离，准备构建结果队列
        for(int i=0; i<dim; i++)
            tmp.first+=DIS(rt->coord[i]-p.coord[i]);

        int now_dim=dep%dim;
        bool flg=false;
        Point *go=rt->lft, *go_another=rt->rgt;

        if(p.coord[now_dim]>=rt->coord[now_dim])
            swap(go, go_another);   //go代表被查点所在的一侧
        if(go)
            queryInner(p, m, dep+1, go);
        if((int)resultq->size()<m){
            resultq->push(tmp);
            flg=true;
            //查到的结果不够，一定向另一侧递归
        }else{
            if(tmp.first<resultq->top().first){
                resultq->pop();
                resultq->push(tmp);
            }//发现了更近的点
            /*待查询点与最远点形成的超球
                与分割空间的超平面相交，向不是所在的一侧递归
            */
            if(DIS(p.coord[now_dim] - rt->coord[now_dim]) < resultq->top().first)
                flg=true;
        }
        if(go_another && flg)
            queryInner(p, m, dep+1, go_another);
    }
    
};


int main(){
    //freopen("1.txt", "r" ,stdin);
    int n, k;
    while(scanf("%d%d", &n, &k)!=EOF){
        kdTree *tree = new kdTree(n, k);
        int t;
        scanf("%d", &t);
        while(t--){
            Point tmp=Point(k);
            int m;
            scanf("%d", &m);
            tree->query(m, tmp);
        }
        delete tree;
    }
    return 0;
}

过段时间会再尝试一下用python写一个kd树。了解到kd树也是从《统计学习方法》上看到的。但是sklearn库还提供了ball-tree。据说比kd树还好。sklearn上现成的算法确实很高效，要远远比自己写的算法快，而且还提供了不少额外功能。但我估计可能是它底层有C/C++优化的原因。

网上搜OJ题解的时候看到所有的人都是开了四倍最大点数的定长数组写的，代码非常短。但其实根本没有必要（也许做比赛有必要吧，但我只求完成功能）。实际上，上面这份代码无论是消耗的内存空间还是执行时间都比开数组的方法小。

头一次在Kaggle上做比赛。网上说从101类型的开始，都是教学类型的比赛，于是就找了一个好做的做做先。

不知道为什么，Numpy不能自动并行矩阵运算。然后python的多线程不能同时在多核环境上跑。所以写了一个多进程的版本。

放代码：

import multiprocessing
import csv
from numpy import*

def readTrainFile():
    m=[]
    with open('train.csv', 'rb') as trainer:
        rawfile=csv.reader(trainer)
        for row in rawfile:
            m.append(row)
    m.remove(m[0])
    for row in m:
        row[0]=int(row[0])
        for i in xrange(1,size(row)):
            if(row[i]!='0'):
                row[i]=1
            else:
                row[i]=0
    return mat(m)
    
def readTestFile():
    m=[]
    with open('test.csv', 'rb') as tester:
        rawfile=csv.reader(tester)
        for row in rawfile:
            m.append(row)
    m.remove(m[0])
    for row in m:
        for i in xrange(size(row)):
            if(row[i]!='0'):
                row[i]=1
            else:
                row[i]=0
    return mat(m)
    
def worker(trainMat, unknownMat, k, cpu_id, pipe):
    trainSize=trainMat.shape[0]
    unknownSize=unknownMat.shape[0]
    
    comMat=mat(zeros((trainSize, trainMat.shape[1]-1)))
    sample=mat(zeros((trainSize, trainMat.shape[1]-1)))
    sorter=mat(zeros((trainSize,2)))
    sortedId=zeros((trainSize,1)) 
    result=[]
    voter=zeros((10,1))
    
    for no in xrange(unknownSize):
        voter=zeros((10,1))
        sample=unknownMat[no,:]
        comMat=tile(sample, (trainSize,1)) - trainMat[:,1:]
        comMat=mat(array(comMat)**2)
        sorter[:,0]=trainMat[:,0]
        sorter[:,1]=comMat.sum(axis=1)
        sortedId=sorter[:,1].argsort(axis=0)
        for i in xrange(k):
            vote=int(sorter[:,0][sortedId[i]])
            voter[vote]=voter[vote]+1
        result.append(voter.argmax())
        print "This is ",no," th sample in CPU No.", cpu_id
    pipe.send(array(result))

def saveRes(result):
    with open('res.csv', 'wb') as resFile:
        writer=csv.writer(resFile)
        writer.writerow(['ImageId', 'Label'])
        r=zeros((result.shape[0],2))
        r[:,0]=array(range(1,result.size+1))
        r[:,1]=result
        for i in r.tolist():
            i[0]=int(i[0])
            i[1]=int(i[1])
            writer.writerow(i)

def collector(r_pipe, pipes):
    res=[]
    for p in pipes:
        res.extend(p.recv().tolist())
    res=array(res)
    r_pipe.send(res)

if __name__ == "__main__":
    train_set=readTrainFile()
    test_set=readTestFile()
    k=1
    print "Read file ok! k= ",k
    
    cpu_n=multiprocessing.cpu_count()
    b_size=test_set.shape[0]/cpu_n
    process=[]
    pipes=[]
    print b_size, cpu_n
    for i in xrange(cpu_n):
        pipe=multiprocessing.Pipe()
        p = multiprocessing.Process(target = worker, 
            args = (train_set, test_set[i*b_size:(i+1)*b_size,:], k, i, pipe[0], ))
        process.append(p)
        pipes.append(pipe[1])
        p.start()
    
    pipe=multiprocessing.Pipe()
    r_pipe=pipe[1]
    collect_process=multiprocessing.Process(target = collector, args=(pipe[0], pipes,))
    collect_process.start()
    res=r_pipe.recv()
    saveRes(res)
    
    command=raw_input("Press a to terminate processes!")
    if(command=='a'):
        for p in process:
            p.terminate()
            

所有的训练样本用上大概需要跑4个小时。大概占用2.5G内存，并且运行时有500MB的波动（可能python写得太搓了，中间有对象不断生成然后释放，以后还会改这份代码）。比单进程的版本要快3倍。我的电脑是AMD A8的四核笔记本，内存8G。Numpy用的是Ubuntu包管理器里的。会不会用Intel的MKL重新编译一下会好些呢？这个以后也可以尝试一下。这份代码跑出来的准确率是0.96271，这个准确率比较靠后了。不管是k值取1还是3准确率都相同。难道取更大些好？因为KNN算法效率实在太渣，所以不打算继续在这个方法上再做尝试了。也许应该换些别的算法。看见有人把准确率弄到100%，简直丧心病狂。

头一次做kaggle还是挺有收获的，主要体验了一把python的多进程还有实际应用场景。这只是个尝试性的测验，以后还可以再做改进。

时间过得非常快。随着这个学期考试的结束我已经在大学完成了一半的学习时间。更为准确说应该是一半多的时间，毕竟大四就没什么课了。还是梳理下吧。

# 这个学期

先说这个学期吧。这个学期简单讲就是没忙出什么名堂。而且也没再去工作室了。工作室的人是我大学里见过的非常nice的一群人（说最nice其实也不过分）。上学期我去了几次工作室发现他们都在弄安卓。尽管当时我也在学安卓，但是将来并不打算把这个作为职业方向，而且我一直很想弄的Web还有服务器还有高大上的机器学习啥的一直还没弄过啥名堂，所以后来就自己研究了。到了这个学期本以为会轻松些，可是课程非常多。另外学院的选修课程考试也非常恶心，六月后就只有复习了（从6月17考第一门到7月5号考了最后一门）。4月末的时候接了銀杏黄项目，任务是开发安卓APP恶意分析工具。因为当时我正在看Coursera的课程，感觉能用机器学习做分类，而且寒假弄的那个东西没弄成，所以又和寒假时弄信息安全竞赛没弄成的小伙伴一起接了这个项目。

项目进展的很慢，因为指导老师希望发论文，所以还要做出点创新来。事实是，一搜论文才发现，用机器学习做恶意应用检测五六年前国外就有很多人在做了，而且这些人的工作涉及很多方面，因此我们不大可能有大的创新。期末考试前的时间除了折腾立项，就是看了些论文。

开学初的超算竞赛还算可以，主要是大家对这个事情是有一定投入的，从寒假几个人自费参加主办方的培训这点就能看出来。可惜团队分工不是很好，中途还有一个人退出。最后还是差了一点点。

后来了解了一下LZW算法，写了个压缩文本的Demo，不过个人认为没什么用。好多时候学算法就如同背菜谱，长期不用就忘了。而且背住菜谱不代表你能够把菜做好。

中间有一段时间做了做Leetcode，做了两场Codeforces（被虐惨了，以前没做过，这比赛还有时差），感觉做题能力不行，估计考CCF证会有点问题，可能要专门像应付考试一样看书刷题。

注册了Coursera的课程，看了看前几讲，老师讲得很好理解。可惜后面因为考试就没看了，希望暑假好好补补。

中间有一个星期跟着网上的博客在看python，写出漂亮的python程序估计还不行，但看懂代码基本是可以的。

总之弄的东西很杂，平时时间碎片化很严重。。。

# 前两年大事回顾

第一年上半学期其实没什么意思。当时太听学校的忽悠话了没带电脑，我估计很多年后想起来我还是会遗憾的。附带的“好处”是玩和娱乐的时间非常多，现在想想真是浪费生命。唯一干的事就是把Thinking in C++卷一看完了，寒假回去C++连带Java还有mySQL（寒假看的）敲了敲。

第二学期干了不少事，大概是最充实的了。学了Linux，数据结构，正则表达式，参加数学建模比赛，看了看Java web培训视频（没什么用，感觉现在忘得差不多了）。

第三学期学了点Android，做了一个难看的播放器（但是很干净，我现在用它听歌）。之前跟工作室的人说的要做的Linux指令检索工具也写好了（代码效率有点低，以后会重写）。王爽的8086汇编大概了解了一下，计算机底层的知识扫了个盲，最后看了看OpenMP和MPI（比赛时候MPI没用上，所以这个也忘得差不多了）。春节前后学了Qt，做了一个很搓的游戏。

学的很杂，但大部分都是我认为必须要会的。有些东西虽然会忘掉，但是再拿起书本肯定是可以想起来的。

# 写在最后

大学本科还是偏向基础和通识，正因为如此我们才要额外自己培养自己更加专门的知识，并深入钻研。这是我目前做的不好，应该改进的地方，因为总感觉自己现在还没有特别突出的技术方向。另外时间不要虚度，应该把碎片化的时间整理好。

也许几年之后，大学里学的大部分知识都会忘掉。我觉得最重要的是掌握快速学习的方法，还有良好的思维习惯。最终留在我们头脑中的应该是知识的精简和抽象。我管这个叫做有关某个领域知识的知识或者知识的索引。

记个流水账，就当是日记，并非总结技术。

假期一直到3月中下旬一直都在弄并行计算方面的事情。虽然之前和班上同学一起打算水一水信息安全竞赛（他们打算做安卓方向，但都没有基础，正好我上过学校开的安卓课程，可以帮帮他们），而且假期有那么一周确实埋头做了很多事，但是最后大家都水过去了（我是在看并行计算的东西，其他人在我研究完Xposed框加后就啥都没往下弄了）。结果可想而知，开学要选指导老师，我们因为没有成品，而且老师问了几个很切中要害的问题（大二有没有时间做这个，学习成绩怎么样，做项目有过需求调查没有，点子有人做过没），于是大家就放弃了。

ASC15超级计算机竞赛听起来很不错，但是我们参赛学生并没有获得很多学院和学校的支持，因为这个竞赛才举办几届。去年寒假我就听说了有这个竞赛。本来想去，但是当时还是太听话，遵循学校的规定第一学期不带电脑，所以C和C++靠的是C4Droid学的。这样的水平当然不会贸然参赛。现在想来遵循校规实在毫无必要，因为我平时不用电脑来打游戏，不带电脑也只是怕辅导员查而已（其实若被查到编程什么事都不会有）。若是当时带了电脑，现在不知道技术水平会是什么样。有的时候就是应该做自己想做的事，不去考虑别人想让你做什么。

今年感觉基础可以了，偶然机会找到了校竞赛的群，加了进去找老师报了名。当时离期末停课还有一个月，感觉还来得及准备。以前折腾过一段时间Linux，写程序基本上C++多，所以看并行计算的东西没什么问题。当时让我负责的是MPI这部分（真是太看得起我了，不进决赛根本用不到MPI的）。也许以后有时间我会总结MPI和OpenMP编程。

假期搞了一周的Xposed框架，然后大部分时间看并行计算。主办方在北京弄了一个2天的培训，我和另外三个小伙伴自费过去听的。题目拿到了以后第一件事就是搜索串改并那题的背景，第一天居然就翻到了论文！春节那几天还是偷了点懒，开小差去弄QT去了。

假期期间整个团队的效率其实很低的，开学后发现大家基本都对题目没啥进展。不过经过讨论还是有些眉目的。不得不承认我们的组织还是有问题，应该多找人参加，制定学习计划。本来6个人的团队，参加开学讨论的只有4个人了，而且除了我另外三位第一年都参加过比赛（比赛要求5人，最后几天我们又找来了一个人）。另外，老师也没申请到学校的设备，所以只能ssh到主办方提供的远程平台上测试。不过大家只管干！而且留下来的人确实都挺厉害：带队的是学校里非常活跃的技术牛人，一起和我做串改并的是校ACM队员，还有一位貌似非常熟悉计算机硬件体系，我自己好歹第一年也拿了个国奖：）。所以说能坚持做一件事的人必有过人之处。

一直到初赛截止前，大家都在忙。截止的前一天晚上，我们把英文的方案提交了上去。

然后等待结果出来，发现是第18名，可是只有16支队能进决赛。。。http://www.asc-events.org/ASC15/index15.php

老师对这个结果还算满意，因为比赛的条件并不好。听队友说去年只是临近截止3天前才开始干，只弄了三天就交上去了，当时还都是大一。准备写文档时我看了去年的方案，发现串改并只有9倍多的加速。然而今年的结果是51倍的加速，进步很大。老师向主办方问了，大概也是后面串改并做的好，前面搭建超算平台的设计方案失分多（因为大家没设备，只是简单分析了一下）。

总的来说我们都尽力了，只能来年再战了！

尽管没进决赛，我还是学到了挺多东西。我觉得一个团队要做成一件事情必须要有凝聚力，不管发生什么情况都不会散才行。这凝聚力的来源就是大家对这件事本身的热情。如果团队中的人把这件事当成自己的很重要的事去做，而不是只想水过去，那么即使条件很不好，也可以把事情做得很精彩。

春节放假到开学前几天学了学Qt。主要是想了解下Linux下开发带图形界面的程序。我是跟着教Google搜索到的教程学的（Qt3），然后又通过查资料和Qt Assistant学了一点Qt creator算是初步入门。

然后离开学一周前写了一个射击游戏（美工不行，就随便画几个图形上去代替了）。算是自己写的第一个C++图形界面程序。

代码比较简单，就不详细分析了。主要就是：目标(target)、炮(cannon)、游戏判定区(judgement)、游戏界面（gameboard）这几个类。游戏开始时生成10个目标（原来是15个，后来自己玩了几次发现根本赢不了）。目标会匀速向下移动。目标全清就胜，否则当目标到达炮台高度就算输。

用到的相关知识点：在Qt绘图的一系列函数、Qt自定义快捷键、信号和槽、QTimer使用（控制游戏物理过程）、STL库（不想写数据结构偷懒用的）、Qt creator的使用。

开发Xposed模块必须用到XposedBridge。这个jar包提供了Xposed的功能。代码很少。现在来分析它的功能：

# 工具类

IXUnhook

接口类，内部有待实现的unhook()方法。

XCallback

抽象类。内部声明Param静态类。

# 类

IXposed

这些都是接口类。实现具体的Xposed模块必须先实现这些接口。IXposedMod是空的接口。另外几个接口都实现这个接口。

IXposedHookZygoteInit

内有待实现的public void initZygote(StartupParam startupParam)方法，每次zygote启动时调用。StartupParam是接口内的静态类，实际类型是String，存放类的路径。

IXposedHookLoadPackage

主要的hook操作由它进行。内有public abstract void handleLoadPackage(LoadPackageParam lpparam)每次调用app的包时发挥作用（在官方教程中也是以这个作为的例子）。内部静态类Wrapper

本文分析一个权限管理类Xposed模块的源代码，主要分析权限管理功能实现的原理。完全按照本人看代码的顺序写成。写此文主要不是为了分析代码，而是总结这种分析代码的思路。所以，懒得看过程可以直接跳到代码分析。

# 准备工作

下载好源代码，还要在手机上把这个程序安装好，这样能直观感受它的功能。

# 大致思路

我们最关键的任务是找到权限控制的核心代码并弄明白它的功能。但是这么多的文件无从下手。我的想法是结合程序的实际操作，然后翻出来相应的代码。

直奔主题

先看AndroidManifest.xml，因为我们要找程序启动界面。除了xposed的meta data，有个定义launcher activity的代码：

<activity
    android:name=".XposedModActivity"
    android:label="@string/app_name"
    android:configChanges="orientation|screenSize">
    <intent-filter>
        <action android:name="android.intent.action.MAIN" />
        <category android:name="android.intent.category.LAUNCHER" />
    </intent-filter>
</activity>

就是说类de.robv.android.xposed.mods.appsettings.XposedModActivity包含启动界面的代码。

在手机上打开程序，会看到启动界面主要是一个ListView，每项里面放着app的名称和包名。点击其中某项会跳到新的Activity里。那么目标明确了，找这个跳转代码。

我用startAcitivity为关键词找到了：

list.setOnItemClickListener(new AdapterView.OnItemClickListener() {

            @Override
            public void onItemClick(AdapterView<?> parent, View view, int position, long id) {
                // Open settings activity when clicking on an application
                String pkgName = ((TextView) view.findViewById(R.id.app_package)).getText().toString();
                Intent i = new Intent(getApplicationContext(), ApplicationSettings.class);
                i.putExtra("package", pkgName);
                startActivityForResult(i, position);
            }
});

可见，ApplicationSettings这个类包含了新的Activity的代码。

新界面只有一个switch，打开switch后所有的选项都出来了。我手机的左下角出现了一个叫”权限管理“的按钮。点开以后是一个对话框，里面的ListView罗列了所有的应用权限让我们修改。单击List里的某项，权限就被禁用了,同时权限的字体由白变紫。

所以我先找这个按钮的代码:

btnPermissions.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                // set up permissions editor
                try {
                    final PermissionSettings permsDlg = new PermissionSettings(ApplicationSettings.this, pkgName, allowRevoking, disabledPermissions);
                        permsDlg.setOnOkListener(new PermissionSettings.OnDismissListener() {
                        @Override
                        public void onDismiss(PermissionSettings obj) {
                            allowRevoking = permsDlg.getRevokeActive();
                            disabledPermissions.clear();
                            disabledPermissions.addAll(permsDlg.getDisabledPermissions());
                        }
                    });
                    permsDlg.display();
                } catch (NameNotFoundException e) {
                }
            }
});

看来PermissionSettings就是权限管理界面的类。在这个类中唯一被我发现的和ListView有关的代码：

// Load the list of permissions for the package and present them
    loadPermissionsList(pkgName);

    final PermissionsListAdapter appListAdapter = new PermissionsListAdapter(owner, permsList, disabledPerms, true);
    appListAdapter.setCanEdit(revokeActive);
    ((ListView) dialog.findViewById(R.id.lstPermissions)).setAdapter(appListAdapter);
    

所以说处理单击ListView项并改变程序权限的代码应该在别的地方。

只能是在Adapter的代码里了：

if (allowEdits) {
    row.setOnClickListener(new View.OnClickListener() {
        @Override
        public void onClick(View v) {
            if (!canEdit) {
                return;
            }

            TextView tv = (TextView) v.findViewById(R.id.perm_name);
            if ((tv.getPaintFlags() & Paint.STRIKE_THRU_TEXT_FLAG) != 0) {
                disabledPerms.remove(tv.getTag());
                tv.setPaintFlags(tv.getPaintFlags() & (~Paint.STRIKE_THRU_TEXT_FLAG));
                tv.setTextColor(Color.WHITE);
            } else {
                disabledPerms.add((String) tv.getTag());
                tv.setPaintFlags(tv.getPaintFlags() | Paint.STRIKE_THRU_TEXT_FLAG);
                tv.setTextColor(Color.MAGENTA);
            }
        }
    });
}

在这里disabledPerms是一个Set<String>类型的对象。顾名思义，这里面方的可能是被禁用的权限。上面代码并没有直接处理权限的部分。结合Diaglog界面有“确定”按钮，推测最后程序先将权限添加到Set中，然后统一禁止权限。

那么disabledPerms怎么传递出去的呢？搜索整个Adapter的代码，看到构造函数里有一句：this.disabledPerms = disabledPerms;。再回头看该才找到的PermissionSettings类里和List唯一有关的代码里有：

final PermissionsListAdapter appListAdapter = new PermissionsListAdapter(owner, permsList, disabledPerms, true);

所以disabledPerms就是我们要找的。下一步可以找PermissionSettings里的这个disabledPerms里的结果怎么返回回去的。搜索这个类里的代码，找到了get方法：

/**
* Get the list of permissions in the disabled state
 */
public Set<String> getDisabledPermissions() {
    return new HashSet<String>(disabledPerms);
}

我们之前找到的ApplicationSettings里面的btnPermissions.setOnClickListener里有这么一行：disabledPermissions.addAll(permsDlg.getDisabledPermissions());。

另外disabledPermissions只有声明没有定义。在onCreate()方法里它才被赋值：

// Setting for permissions revoking
allowRevoking = prefs.getBoolean(pkgName +   Common.PREF_REVOKEPERMS, false);
disabledPermissions = prefs.getStringSet(pkgName + Common.PREF_REVOKELIST, new HashSet<String>());

同时在private Map<String, Object> getSettings()这个方法结尾处有这么两行：

if (disabledPermissions.size() > 0)
    settings.put(pkgName + Common.PREF_REVOKELIST, new HashSet<String>(disabledPermissions));
    

方法的返回值就是settings。如果再看看整个方法的代码，可知这个应用的所有被修改内容全放到这个settings里了。

在onOptionsItemSelected里出现了getSettings()的调用，同时还有很多sharedPreference的操作。在手机上，我们修改应用权限，然后单击右上角的保存按钮，弹出提示对话框，询问是否结束进程以便下次启动时采用新设置。根据这点找到代码：

prefsEditor.commit();

// Update saved settings to detect modifications later
initialSettings = newSettings;

// Check if in addition to saving the settings, the app should also be killed
AlertDialog.Builder builder = new AlertDialog.Builder(this);
builder.setTitle(R.string.settings_apply_title);
builder.setMessage(R.string.settings_apply_detail);
builder.setPositiveButton(android.R.string.yes, new DialogInterface.OnClickListener() {
    @Override
    public void onClick(DialogInterface dialog, int which) {
        // Send the broadcast requesting to kill the app
        Intent applyIntent = new Intent(Common.MY_PACKAGE_NAME + ".UPDATE_PERMISSIONS");
        applyIntent.putExtra("action", Common.ACTION_PERMISSIONS);
        applyIntent.putExtra("Package", pkgName);
        applyIntent.putExtra("Kill", true);
        sendBroadcast(applyIntent, Common.MY_PACKAGE_NAME + ".BROADCAST_PERMISSION");

        dialog.dismiss();
    }
});

整个工程只有一个PackagePermissions类是BroadcastReceiver类。打开后发现这个类有大量的Xposed的hook函数。那么问题来了：

• 广播接受器什么时候开始工作的？
• 哪些是hook权限的操作？
• hook是如何在开机时就开始了（否则没办法监控权限）

在BroadcastReceiver里叫initHooks()的静态方法里找到：

final Class<?> clsPMS = findClass("com.android.server.pm.PackageManagerService", XposedMod.class.getClassLoader());

// Listen for broadcasts from the Settings part of the mod, so it's applied immediately
findAndHookMethod(clsPMS, "systemReady", new XC_MethodHook() {
    @Override
    protected void afterHookedMethod(MethodHookParam param) throws Throwable {
        Context mContext = (Context) getObjectField(param.thisObject, "mContext");
        mContext.registerReceiver(new PackagePermissions(param.thisObject),
                new IntentFilter(Common.MY_PACKAGE_NAME + ".UPDATE_PERMISSIONS"),
                Common.MY_PACKAGE_NAME + ".BROADCAST_PERMISSION",
                null);
    }
});

// if the user has disabled certain permissions for an app, do as if the hadn't requested them
findAndHookMethod(clsPMS, "grantPermissionsLPw", "android.content.pm.PackageParser$Package", boolean.class,
        new XC_MethodHook() {
    @SuppressWarnings("unchecked")
    @Override
    protected void beforeHookedMethod(MethodHookParam param) throws Throwable {
        String pkgName = (String) getObjectField(param.args[0], "packageName");
        if (!XposedMod.isActive(pkgName) || !XposedMod.prefs.getBoolean(pkgName + Common.PREF_REVOKEPERMS, false))
            return;

        Set<String> disabledPermissions = XposedMod.prefs.getStringSet(pkgName + Common.PREF_REVOKELIST, null);
        if (disabledPermissions == null || disabledPermissions.isEmpty())
            return;

        ArrayList<String> origRequestedPermissions = (ArrayList<String>) getObjectField(param.args[0], "requestedPermissions");
        param.setObjectExtra("orig_requested_permissions", origRequestedPermissions);

        ArrayList<String> newRequestedPermissions = new ArrayList<String>(origRequestedPermissions.size());
        for (String perm: origRequestedPermissions) {
            if (!disabledPermissions.contains(perm))
                newRequestedPermissions.add(perm);
            else
                // you requested those internet permissions? I didn't read that, sorry
                Log.w(Common.TAG, "Not granting permission " + perm
                        + " to package " + pkgName
                        + " because you think it should not have it");
        }

        setObjectField(param.args[0], "requestedPermissions", newRequestedPermissions);
    }

    @SuppressWarnings("unchecked")
    @Override
    protected void afterHookedMethod(MethodHookParam param) throws Throwable {
        // restore requested permissions if they were modified
        ArrayList<String> origRequestedPermissions = (ArrayList<String>) param.getObjectExtra("orig_requested_permissions");
        if (origRequestedPermissions != null)
            setObjectField(param.args[0], "requestedPermissions", origRequestedPermissions);
    }

分析代码

BroadcastReceiver里的注释说：

/* Hook to the PackageManager service in order to
* - Listen for broadcasts to apply new settings and restart the app
* - Intercept the permission granting function to remove disabled permissions
*/

也就是说监听器hook到了Android系统的包管理器类com.android.server.pm.PackageManagerService，并且hook了里面的方法。所以上面提到的哪些是hook权限的操作基本上解决了，代码之后详细分析。那么广播什么时候开始接收的？在IntelliJ里搜索BroadcastReceiver被用到的地方，发现：

1. XposedMod类中initZygote方法里出现PackagePermissions.initHooks();
2. 刚才贴出的大段BroadcastReceiver里出现mContext.registerReceiver里面有它的构造函数。

initZygote是Xposed框架IXposedHookZygoteInit接口中要自己实现的方法。接口的源代码为：

/**
* Hook the initialization of Zygote (the central part of the "Android OS")
*/
public interface IXposedHookZygoteInit extends IXposedMod {
/**
 * Called very early during startup of Zygote
 * @throws Throwable everything is caught, but will prevent further initialization of the module
 */
    public void initZygote(StartupParam startupParam) throws Throwable;

    public static class StartupParam {
        public String modulePath;
 }
}

这就意味着每当启动一个进程，都会执行initZygote里监听器的initHooks()方法来给包管理器挂钩。权限监听的钩子应该挂到com.android.server.pm.PackageManagerService这个类的名为的grantPermissionsLPw方法上。程序用了Xposed框架提供的findAndHookMethod方法。通过这个方法接收的参数，我们得知被hook的grantPermissionsLPw方法接收两个参数，分别是Package类型（android.content.pm.PackageParser的内部类），和boolean。initHooks()方法还顺带注册监听器来接受来自appSettings这个app自己发出的广播。再进一步查看工程代码和安卓源代码，就知道，appSettings的权限拦截原理是这样的：

原来的权限授权以前先：从之前appsSettings存储的sharedPreferences里取得对应应用的权限列表，放到Set<String> disabledPermissions里。并用ArrayList<String> origRequestedPermissions存放应用索要的权限，并利用Xposed自带的方法存储一份这个权限列表到param对象里。然后通过for each循环，对比两个ArrayList，生成第三张表newRequestedPermissions,并用setObjectField方法替换掉了原来Package对象的requestedPermissions对象。

之后，安卓系统会按照被我们“调包”的权限清单执行程序。

被hook过的方法执行以后：从param对象取出我们刚刚保存的原始的权限列表，然后再次用setObjectField把这个原始列表复原回去。

于是第二个问题，哪些是hook操作，怎么hook的问题就解决了。

最后，我们打开工程目录下assets/xposed_init文件，看到de.robv.android.xposed.mods.appsettings.XposedMod。所以，Xposed框架开始执行的就是这个类里的代码。它实现了IXposedHookZygoteInit与 IXposedHookLoadPackage接口。所以能：1.在zygote启动时执行，从而管理权限。2.在应用app的包加载前执行hook操作，替换应用资源（这是appSettings另一个功能，但本文不分析）。

所以，为何启动时就能hook的问题也解决了。