xhSong's Blog

一直用塞班的系统，这一阵子要做个Android的应用，不熟悉Android导致各种蛋疼。

Android传输协议&AirDroid

习惯了Ubuntu，于是就在Ubuntu下用eclipse开发。首先遇到的就是文件传输的问题。想看看在sd卡中存的文本文件，怎么都找不到在哪儿。Android和电脑之间的传输协议有两种——MTP，PTP。

PTP——图片传输协议(picture transfer protocol)”。最早由柯达公司与微软协商制定的一种标准，符合这种标准的图像设备在接入Windows XP系统之后可以更好地被系统和应用程序所共享，尤其在网络传输方面，系统可以直接访问这些设备用于建立网络相册时图片的上传、网上聊天时图片的传送等。（来自百度百科）

MTP——媒体传输协议（即通常所说的MTP）是“Windows Media”框架的一部分。Windows Vista中内置了对MTP的支持，Mac以及Linux系统有相应的软件包提供对MTP的支持。（来自维基百科）

看了两个协议的简介，实在想不明白，作为世界级的Google公司用了Linux的内核竟然还会用和Windows扯上这么大关系的传输协议！本以为手机接上Ubuntu可以很简单的mount上去，然后用shell管理的，看样子是泡汤了。

后来见有人推荐airDroidhttp://web.airdroid.com/，用了下，感觉很方便，能很好的解决我的需求。因为只是查看下文本文件速度也就不成问题了。这里对于个子较小的文本文件如果能在浏览器中打开就更好了，免得要下载再查看。

应用程序最大内存限制 heap growth limit

由于这个应用要做比较多的图像处理和显示，老是出现 Out of Memory的错误导致程序退出。起初以为是手机内存不够的原因，于是关了很多正在运行的其他程序以及后台服务，发现还是崩。

使用DDMS监视了下内存使用，发现heap size 60M左右的时候就有很大几率挂。突然想起来，java虚拟机有内存使用上限的限制。

google了下，发现有三个变量和java虚拟机内存使用限制有关

dalvik.vm.heapgrowthlimit #单个应用程序最大内存限制
dalvik.vm.heapstartsize #应用启动后分配的初始内存
dalvik.vm.heapsize #单个java虚拟机最大的内存限制

于是执行

adb shell getprop | grep heapgrowthlimit

果然，每个应用内存限制是64M（对于不同的机器这个数字会不一样）。这个参数被纪录在/system/build.prop中。使用adb shell进入手机shell（前提是你的手机正确连上电脑了呀）。很惊奇的发现，Android上的linux还有vi，虽然没有vim有点可惜，不过vi对于我这种菜鸟来说已经足够用了。兴致勃勃冲上去，把/system/build.prop中

dalvik.vm.heapgrowthlimit=64m

改成

dalvik.vm.heapgrowthlimit=128m

发现不能保存，报了一个如下的错

"build.prop" File is read only

（这个地方记得不是太清楚是这个错还是Permission denied，反正在此重复试验过程的时候是这个错。我感觉好像是权限的错）。

接着把手机root了后su一下，再改，发现还是有read only的错。

read only解决方案

google 了几个方案，试了下，如下的方法可用

进入android的linux shell后，执行

mount

查看挂载的设备，发现有如下一条：

/dev/block/mmcblk0p9 /system ext4 ro,relatime,errors=panic,barrier=1,data=writeback 0 0

从上面可以看出，挂载点/system挂载的是一个ext4文件系统，relatime何意暂时不知，ro是read only的意思，后面几个参数和ext4的安全性有关，不用太关心。最重要的是ro。执行下面指令，重新挂载这个块设备，设置为可读可写

mount -o remount -o rw /system 

这时候你再mount一下，发现原先的ro变成了如下的rw

/dev/block/mmcblk0p9 /system ext4 rw,relatime,errors=panic,barrier=1,data=writeback 0 0

这时候你su一下，再用vi修改/system/build.prop就可以修改了。然后重启一下手机，就ok了。同时也解决了之前用linux 命令随意“进出”android的想法。

OpenGL（全写Open Graphics Library）是个定义了一个跨编程语言、跨平台的应用程序接口（API）的规格，它用于生成二维、三维图像。

开放源代码库Mesa是一个纯基于软件的图形API，它的代码兼容于OpenGL。但是，由于许可证的原因，它只声称是一个“非常相似”的API。因此Linux要用OpenGL，需要装Mesa和freeglut（为什么叫freeglut？不晓得）

执行下面代码即可安装（实验了很多方法，最后才装上的，不知道这两个够不够）

sudo apt-get install freeglut3 freeglut3-dev
sudo apt-get install mesa-common-dev mesa-utils

安装完成后测试下如下的代码（人比较懒，直接到百度了段代码）

#include <GL/glut.h>
void display()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glBegin(GL_POLYGON);
     glVertex2f(-0.5,-0.5);
     glVertex2f(-0.5,0.5);
     glVertex2f(0.5,0.5);
     glVertex2f(0.5,-0.5);
    glEnd();
    glFlush();
}
int main(int argc,char **argv)
{
    glutInit(&argc,argv);
    glutCreateWindow("Hello,world!");
    glutDisplayFunc(display);
    glutMainLoop();
}

将如上代码保存成a.c 后执行如下命令编译程序

gcc a.c -o -lGL -lglut

如果出现如下错误，说明OpenGL没有装成功

a.c:1:21: 致命错误： GL/glut.h：没有那个文件或目录
编译中断。

如果出现下面的错误

/tmp/ccVGAaqV.o: In function `display':
a.c:(.text+0xa): undefined reference to `glClear'
a.c:(.text+0x14): undefined reference to `glBegin'
a.c:(.text+0x29): undefined reference to `glVertex2f'
a.c:(.text+0x3e): undefined reference to `glVertex2f'
a.c:(.text+0x53): undefined reference to `glVertex2f'
a.c:(.text+0x68): undefined reference to `glVertex2f'
a.c:(.text+0x6d): undefined reference to `glEnd'
a.c:(.text+0x72): undefined reference to `glFlush'
/tmp/ccVGAaqV.o: In function `main':
a.c:(.text+0x96): undefined reference to `glutInit'
a.c:(.text+0xa0): undefined reference to `glutCreateWindow'
a.c:(.text+0xad): undefined reference to `glutDisplayFunc'
a.c:(.text+0xb2): undefined reference to `glutMainLoop'
collect2: ld 返回 1

有人说是因为OpenGL没有装好，我又是重装freeglut，又是装各种看起来像的库。最后才发现，原来是没有装显卡驱动，囧囧的。所以你要是遇到相同的问题，先检查下显卡驱动是不是装好了。

搞定，终于可以在Linux下使用OpenGL了。考虑到每次编译带有GL的文件都需要加-lGL -lglut的参数比较麻烦，于是在~/.bashrc最后加上如下一行

alias glc="g++ -lGL -lglut"

然后编译的时候之需要像gcc/g++那样编译，执行如下代码就ok了

glc a.c -o a

nice！

PS: 我的系统被我折腾了下，发现前面的东西都装好了，然后又是上面的编译错误。今天终于解决了！解决方案是安装 binutils-gold

sudo apt-get install binutils-gold

gold是一个正在开发的新的连接器...来自http://packages.ubuntu.com/zh-cn/lucid/binutils-gold。估计是64位ubuntu的原因，装上这个就好了。

另外还找到一个比较好的学习资料，供大家参考http://ogldev.atspace.co.uk/

原题

#include <cstdio>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <iterator>
#include <algorithm>


using namespace std;


int const N = 3;
int PN = N * N, QN = PN * PN;

/***最大行***/
#define MAXROW 1001
/***最大列***/
#define MAXCOL 1001

struct DancingLinksNode {
    /***结点所在的行列位置***/
    int r, c;
    /***结点的上下左右结点指针***/
    DancingLinksNode *U, *D, *L, *R;
};

/****备用结点****/
DancingLinksNode node[MAXROW * 101];
/****行头****/
DancingLinksNode row[MAXROW];
/****列头****/
DancingLinksNode col[MAXCOL];
/****表头****/
DancingLinksNode head;
/****使用了多少结点****/
int cnt;
/****列含有多少个域****/
int size[MAXCOL];
/****表的行与列变量****/
int m, n;
/****选择的行****/
int choice[MAXROW];

/****初始化，r, c分别表示表的大小***/
void init(int r, int c) {
    /****将可以使用的结点设为第一个****/
    cnt = 0;
    /****head结点的r,c分别表示表的大小,以备查****/
    head.r = r;
    head.c = c;
    /****初始化head结点****/
    head.L = head.R = head.U = head.D = &head;

    /***初始化列头***/
    for(int i = 0; i < c; ++i) {
        col[i].r = r;
        col[i].c = i;
        col[i].L = head.L;
        col[i].R = &head;
        col[i].L->R = col[i].R->L = &col[i];
        col[i].U = col[i].D = &col[i];
        size[i] = 0;
    }


    /***初始化行头,在删除的时候，如果碰到row[i].c  == c的情形应当被跳过***/
    for(int i = r - 1; i > -1; --i) {
        row[i].r = i;
        row[i].c = c;
        row[i].U = head.U;
        row[i].D = &head;
        row[i].U->D = row[i].D->U = &row[i];
        row[i].L = row[i].R = &row[i];
    }
}

/****增加一个结点,在原表中的位置为r行,c列***/
inline void addNode(int r, int c) {
    /****找一个未曾使用的结点****/
    DancingLinksNode *ptr = &node[cnt++];

    /****设置结点的行列号****/
    ptr->r = r;
    ptr->c = c;

    /****将结点加入双向链表中****/
    ptr->L = row[r].L;
    ptr->R = &row[r];
    ptr->L->R = ptr->R->L = ptr;

    ptr->U = col[c].U;
    ptr->D = &col[c];
    ptr->U->D = ptr->D->U = ptr;

    /****将size域加1****/
    ++size[c];
}

/****删除ptr所指向的结点的左右方向****/
inline void delLR(DancingLinksNode * ptr) {
    ptr->L->R = ptr->R;
    ptr->R->L = ptr->L;
}

/****删除ptr所指向的结点的上下方向****/
inline void delUD(DancingLinksNode * ptr) {
    ptr->U->D = ptr->D;
    ptr->D->U = ptr->U;
}

/****重置ptr所指向的结点的左右方向****/
inline void resumeLR(DancingLinksNode * ptr) {
    ptr->L->R = ptr->R->L = ptr;
}

/****重置ptr所指向的结点的上下方向****/
inline void resumeUD(DancingLinksNode * ptr) {
    ptr->U->D = ptr->D->U = ptr;
}

/****覆盖第c例***/
inline void cover(int c) {
    /**** c == n 表示头****/
    if(c == n) {
        return;
    }

    /****删除表头****/
    delLR(&col[c]);

    DancingLinksNode *R, *C;
    for(C = col[c].D; C != (&col[c]); C = C->D) {
        if(C->c == n)
            continue;
        for(R = C->L; R != C; R = R->L){
            if(R->c == n)
                continue;
            --size[R->c];
            delUD(R);
        }
        delLR(C);
    }

}

/****重置第c列****/
inline void resume(int c) {
    if(c == n)
        return;
    DancingLinksNode *R, *C;
    for(C = col[c].U; C != (&col[c]); C = C->U) {
        if(C->c == n)
            continue;
        resumeLR(C);
        for(R = C->R; R != C; R = R->R) {
            if(R->c == n)
                continue;
            ++size[R->c];
            resumeUD(R);
        }
    }

    /****把列头接进表头中****/
    resumeLR(&col[c]);
}

/****搜索核心算法,k表示搜索层数****/
int search(int k ＝ 0) {

    /***搜索成功,返回true***/
    if(head.L == (&head)) {
        return k;
    }
    /***c表示下一个列对象位置,找一个分支数目最小的进行覆盖***/
    int INF = (1<<30), c = -1;

    for(DancingLinksNode * ptr = head.L; ptr != (&head); ptr = ptr->L) {
        if(size[ptr->c] < INF) {
            INF = size[ptr->c];
            c = ptr->c;
        }
    }
    /***覆盖第c列***/
    cover(c);

    DancingLinksNode * ptr;

    for(ptr = col[c].D; ptr != (&col[c]); ptr = ptr->D) {
        DancingLinksNode *rc;
        ptr->R->L = ptr;
        choice[k] = ptr->r;
        for(rc = ptr->L; rc != ptr; rc = rc->L) {
            cover(rc->c);
        }
        ptr->R->L = ptr->L;
        int ans = search(k + 1);
        if(ans) {
            return ans;
        }
        ptr->L->R = ptr;
        for(rc = ptr->R; rc != ptr; rc = rc->R) {
            resume(rc->c);
        }
        ptr->L->R = ptr->R;
    }

    /***取消覆盖第c列***/
    resume(c);
    return 0;
}


void addPoss(int i, int j) {
    int x = i / PN, y = i % PN;
    addNode(i * PN + j, i);
    addNode(i * PN + j, QN * 1+ x * PN + j);
    addNode(i * PN + j, QN * 2 + y * PN + j);
    addNode(i * PN + j, QN * 3 + (x / N * N + y / N) * PN + j);
}

int main(int argc, char** argv) {
    char s[100];
    while(1) {
        scanf("%s", s);
        if(strcmp(s, "end") == 0) {
            break;
        }
        m = PN * QN, n = 4 * QN;
        init(m, n);
        for(int i = 0; i < QN; ++i) {
            if(s[i] == '.')  {
            	for(int j = 0; j < PN; ++j) addPoss(i, j);
            } else {
            	addPoss(i, s[i] - '1');
            }	
        }
        search();
        for(int i = 0; i < QN; i ++) {
            s[choice[i] / PN] = choice[i] % PN + '1';
        }
        puts(s);
    }
    return 0;
}

之前也接触过遗传算法，只是没有实践，正巧这次模式识别的课程上老师提到，并布置了一个小练习题，便拿来做做吧。

题目本来要求是求Rosenbrock函数f(x, y) = (x-1)² + 100(y-x²)²在[-2,-2,2,2]之间的最大值，稍加分析，或者看下面的图就会发现，其实当(x, y) = (-2, -2)时，f(x,y)即可取到最大值。

觉得这样没什么意思，于是自己稍微把题目改了下，把x，y都变成sin x，sin y，函数就变成f(x, y) = (sin x-1)² + 100(sin y-sin²x)²

这是一个很漂亮的双峰函数。下面我们来讨论如何用遗传算法来求这个函数的极大值。

编码方式

由于x,y的范围都是[-2,2]，那么可以考虑使用11个二进制的定点小数来编码0.000到2.047这2048个定点小数。在加上1个二进制位符号为，即可表示[-2.047, 2.047]，刚好可以覆盖[-2,2]并且精度为0.001。x和y都采用相同的方法编码，然后拼接在一起，形成一个24位的二进制整数。实现过程中可以使用整数保存，位运算做遗传和变异。

原始个体生成方式

根据编码方式，每一个个体可以用24个二进制位表示，于是可以很简单的随机生成一个[0,1<<24)的整数表示一个个体。生成30个祖先个体

确定遗传、变异方式

遗传方式：任取两个个体(A,B)进行交配，生成两个子个体(C,D)。C基因序列的低k个二进制位来自于A，高24-k个二进制位来自于另一个父本B，其中0<k<24。D基因序列和C的情况真好相反，其低k个二进制位来自于B，高24-k个二进制位来自于A。用python语言表示为

k = randint(1, 23)
mask = (1<<k) - 1
C = A & mask | B & ~mask
D = B & mask | A & ~mask

变异方式：随机选取24个二进制位中的某一个，如果该位0变成则变成1，否则变成0

from random import randint
from numpy import sin

def decode(g):
    return [((g&0xfff) - 2048) * 0.001, ((g>>12) - 2048) * 0.001]

def function_g(g):
    x = decode(g)
    return function(x[0], x[1])
    
def function(x, y):
    return 100 * (sin(x) ** 2 - sin(y)) ** 2 + (1 - sin(x)) ** 2

def cmp(g1, g2):
    key = function_g(g1) - function_g(g2)
    if key > 0: return 1
    elif key < 0: return -1 
    else: return 0

def GA(num = 30, round = 10):
    gene = [randint(0, (1<<24) - 1) for i in range(num)]
    rnd = 0
    while rnd < round:
        rnd += 1
        gene_c = [g ^ (1<<randint(0, 23))  for g in gene]
        gene_h = []
        for g1 in gene:
            for g2 in gene:
                mask = (1<<randint(1, 23)) - 1
                gene_h.append(g2 & ~mask | g1 & mask)
                gene_h.append(g1 & ~mask | g2 & mask)
        gene_tot = gene + gene_h + gene_c
        gene_tot.sort(cmp = cmp, reverse = True)
        gene = gene_tot[:num]
        print "round", rnd, ":", decode(gene[0]), function_g(gene[0]) 
    return decode(gene[0]) + [function_g(gene[0])]
    
if __name__ == '__main__':
    print GA(30, 10), 

round 1 : [1.571, -1.464] 397.724305554
round 2 : [1.571, -1.539] 399.797824716
round 3 : [-1.605, -1.548] 403.426161017
round 4 : [-1.605, -1.556] 403.486264841
round 5 : [-1.541, -1.591] 403.561685598
round 6 : [-1.541, -1.575] 403.639747518
round 7 : [-1.573, -1.579] 403.984587994
round 8 : [-1.573, -1.571] 403.998039526
round 9 : [-1.569, -1.571] 403.998694536
round 10 : [-1.569, -1.571] 403.998694536

可以看到，结果收敛得非常快，并且经过10次迭代，结果基本稳定。

这段时间在上算法课，有些作业题目要求写出伪代码。正好这段时间在学习latex，于是就收集整理了下latex描写算法的包。latex下描写算法的包主要有algorithmic, algorithmicx和algorithm2e

algorithmic和algorithmicx

介绍下algorithmic和algorithmicx，这两个包很像，很多命令都是一样的，只是algorithmic的命令都是大写，algorithmicx的命令都是首字母大写，其他小写(EndFor两个大写)。下面是algorithmic的基本命令

\STATE <text>

\IF{<condition>} \STATE{<text>} \ENDIF

\FOR{<condition>} \STATE{<text>} \ENDFOR

\FOR{<condition> \TO <condition> } \STATE{<text>} \ENDFOR

\FORALL{<condition>} \STATE{<text>} \ENDFOR

\WHILE{<condition>} \STATE{<text>} \ENDWHILE

\REPEAT \STATE{<text>} \UNTIL{<condition>}

\LOOP \STATE{<text>} \ENDLOOP

\REQUIRE <text>

\ENSURE <text>

\RETURN <text>

\PRINT <text>

\COMMENT{<text>}

\AND, \OR, \XOR, \NOT, \TO, \TRUE, \FALSE

对比看一下，下面是algorithmicx包的基本命令

\State <text>

\If{<condition>} <text> \EndIf

\If{<condition>} <text> \Else <text> \EndIf

\If{<condition>} <text> \ElsIf{<condition>}  <text> \Else <text> \EndIf

\For{<condition>} <text> \EndFor

\ForAll{<condition>} <text> \EndFor

\While{<condition>} <text> \EndWhile

\Repeat <text> \Until{<condition>}

\Loop <text> \EndLoop

\Require <text>

\Ensure <text>

\Function{<name>}{<params>} <body> \EndFunction

\State \Return <text>

\Comment{<text>}

另外，还有3个修改algorithm标签，require标签，ensure标签显示的三个命令：

\floatname{algorithm}{算法}

\renewcommand{\algorithmicrequire}{\textbf{输入:}} 

\renewcommand{\algorithmicensure}{\textbf{输出:}}

algorithmicx例子

正好学着用algorithmicx写了下归并排序求逆序数，代码如下

\documentclass[11pt]{article}
\usepackage{CJK}
\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{amsmath}

\floatname{algorithm}{算法}
\renewcommand{\algorithmicrequire}{\textbf{输入:}}
\renewcommand{\algorithmicensure}{\textbf{输出:}}

\begin{document}
\begin{CJK*}{UTF8}{gkai}
    \begin{algorithm}
        \caption{用归并排序求逆序数}
        \begin{algorithmic}[1] %每行显示行号
            \Require $Array$数组，$n$数组大小
            \Ensure 逆序数
            \Function {MergerSort}{$Array, left, right$}
                \State $result \gets 0$
                \If {$left < right$}
                    \State $middle \gets (left + right) / 2$
                    \State $result \gets result +$ \Call{MergerSort}{$Array, left, middle$}
                    \State $result \gets result +$ \Call{MergerSort}{$Array, middle, right$}
                    \State $result \gets result +$ \Call{Merger}{$Array,left,middle,right$}
                \EndIf 
                \State \Return{$result$}
            \EndFunction
            \State 
            \Function{Merger}{$Array, left, middle, right$}
                \State $i\gets left$
                \State $j\gets middle$
                \State $k\gets 0$
                \State $result \gets 0$
                \While{$i<middle$ \textbf{and} $j<right$}
                    \If{$Array[i]<Array[j]$}
                        \State $B[k++]\gets Array[i++]$
                    \Else
                        \State $B[k++] \gets Array[j++]$
                        \State $result \gets result + (middle - i)$
                    \EndIf
                \EndWhile
                \While{$i<middle$}
                    \State $B[k++] \gets Array[i++]$
                \EndWhile
                \While{$j<right$}
                    \State $B[k++] \gets Array[j++]$
                \EndWhile
                \For{$i = 0 \to k-1$}
                    \State $Array[left + i] \gets B[i]$
                \EndFor
                \State \Return{$result$}
            \EndFunction
        \end{algorithmic}
    \end{algorithm}
\end{CJK*}
\end{document}

最后的排版结果如下

algorithm2e还没有学习，待以后再更新吧