关于intel 915集成显卡驱动的笔记

按照intel官方主页上的提示，装了n久，试验了n久，成功了一小部分，记下。
显卡驱动的安装分成4个部分：
1. 内核相关部分的drm支持，可以用三种方法安装
a) 编译内核的时候加入drm支持，一般在 Devices Drivers --> Graphic Drivers --> DRM下面，编译进内核或编译成module(即m)均可
b) 安装x11-base/x11-drm包，注意此时内核中的drm支持应该去掉，否则包安装失败(本人的是gentoo，其他的如Debian，Suse或FC也有相对应的包，安装上即可)。
c) 到代码仓库中git出源代码来安装。
# git clone git://anongit.freedesktop.org/git/mesa/drm
这个drm文件夹下包含了两个东东，一个是libdrm,步骤2要用; 一个是drm内核驱动，此部分关注。
# cd drm/linux-core
# make
# cp *.ko /lib/modules/`uname -r`/kernel/drivers/char/drm/
接着修改/libmodules/`uname -r`/modules.dep文件，照着文件的格式来作，将modules都添入，使得kernel能找到它们。a)和b)中这一步已经自动做好了，所以不用手工改这个文件。
这三种方法得到的都是如i810.ko, i915.ko, i835.ko, intel.ko之类的文件，用modprobe可以加载之。

2. libdrm的安装, 可用两种方法做：
a) 源代码安装。1 c)中的代码中包含了libdrm，所以直接编译：
# cd drm
# ./autogen.sh --prefix=/usr --exec-prefix=lib # 加上两个prefix主要是用来覆盖系统原有的libdrm.so等库文件
# make && make install
b) 包安装(同样这里是gentoo的，其它系统类似)。
# emerge libdrm
此步生成的文件是libdrm.so, libdrm.la, libdrm...等一系列库文件。

3. xorg intel显卡2D驱动的安装，同样两种方法都可以：
a) 源代码安装
# git clone git://anongit.freedesktop.org/git/drivers/xf86-video-intel
# ./configure --prefix=${XORG_DIR}
# make && make install
注意，这里XORG_DIR是xorg-server被安装的主目录，我的系统上是/usr/X11R6
b) 包安装
# emerge -av xf86-video-intel
此步生成的文件是xorg的intel显卡2D驱动，形如intel_drv.so, i810_drv.so。
还有一个要注意的问题是，如果第2步中使用的是源代码安装，第3步中的./configure或者是emerge可能会有错误，抱怨libdrm没有安装，这主要是因为虽然安装了，但package系统没有找到它。所以为了能找到它，需要
# pkg-config /lib/pkgconfig
来更新libdrm库的信息。然后用
# pkg-config --modversion libdrm
来看看libdrm库文件的版本号，输出正确版本号，说明信息更新。然后在安装3就可以了。我的系统libdrm库安装在/lib下，所以pkg信息就在目录/lib/pkgconfig下。实际上是一个.pc文件，对于libdrm库，就是libdrm.pc。

4. xorg 下显卡3D驱动
同样用包安装(emerge mesa) 或者 源代码安装(git clone git://anongit.freedesktop.org/git/mesa/mesa; ./configure; make && make install)

至此全部安装完毕，将xorg.conf文件中的显卡module的driver改成intel，将"load dri" 以及"load glx"前面的"#"去掉。重新启动X，happy
另外可以用glxgears以及glxinfo来测试显卡性能以及dri打开与否。这两个东东是要安装的(emerge mesa-util？忘掉了，差不多吧8-/)

-----------------------------------------------------------------------------------------------
另外几个问题：
1) gentoo中自动加载模块可以放到/etc/modules.autoload.d/kernel-2.6文件中，如intel-agp
2) 好相不同的内核驱动放置的目录不同，新内核如我的2.6.27-r5内核，i810.ko放在/lib/modules/`uname -r`/kernel/drivers/gpu/drm/目录下，而老内核放在/lib/modules/`uname -r`/kernel/drivers/char/drm/目录下，这个问题其实困扰了我很久。
3) 手工加内核模块进/lib/modules/`uname -r`/目录下，一定记住加完后更新/lib/modules/`uname -r`/modules.dep文件，我现在只知道手工更新文件，是否能自动更新？待求解
4) 我的intel 915G显卡glxgears测试下来，竟然只有260多fps，虽然看见dri=yes了，估计还只是software的dri，硬件dri还没有搞定，实在是太难弄了。

And now, my X can't work properly once again (after a recompilation of my kernel). Terrible thing, terrible things all!

回溯法(1)

话说回溯通过剪枝可以在性能上大大高于暴力，这是很好理解的(另外，今天才知道溯读作su第四声而不是shuo)，但是比起DP来，时间复杂度还是很高的。典型的回溯解空间有子集树控件，时间复杂度为指数(如2^n)；或者排列树，时间复杂度为阶乘(n!)。回溯到思想就是走迷宫，走到死胡同了，立即退回去，走另外一条路，以此往复。
程序上，可以用递归或者非递归实现，个人认为递归实现起来简单些，只要注意将状态量适时更新就可以了。下面贴出自己的几个实现程序。

1. 递归实现0-1背包的回溯

// W 背包重量数组， V 货物价值数组，i 当前考虑货物，n 总货物数，C 背包容量
// val 当前背包装入的价值，flag 当前遍历的货物状态数组(1代表要装入背包，0表示不要)
// maxflag 能取得最大价值的货物装法，maxval 背包能装入最大价值
void backtrack_cur(int* W, int* V, int i, int n, int C, 
       int val, int* flag, int* maxflag, int& maxval)
{
 if (i == n)    // 遍历完货物一趟
 {
  if (maxval < val){      // 当前价值与已知总价值比
   maxval = val;
   copy(flag, flag+n, maxflag);   // 记下价值最大时的货物标志
  }
  return;
 }

 // 背包不装入货物i
 backtrack_cur(W, V, i+1, n, C, val, flag, maxflag, maxval);        //递归

 // 背包装入货物i，如果不能装入，则剪枝
 if (W[i] <= C) {
  val += V[i];
  C -= W[i];
  flag[i] = 1;
  backtrack_cur(W, V, i+1, n, C, val, flag, maxflag, maxval); //递归
 }
 flag[i] = 0;     // 回溯，即走回去，只是flag状态清除到以前，这样才能回溯
}

调用此函数就比较简单：backtrack_cur(W, V, 0, n, capacity, 0, flag, maxflag, maxval);

2. 非递归实现0-1背包的回溯

1) 穷举实现(其实这里非回溯)：

void enumerate(int* W, int* V, int n, int C)
{
 int space = 1 << n;   // 搜索空间，每一位代表一个货物，1代表装入背包
 int flag = space;     // 结果标记
 int weight, value, maxvalue = 0;
 for (int i = 0; i < space; ++i) {
  value = 0;  weight = 0;
  for (int j = 0; j < n; ++j) {    // 找出第j个货物是否装入背包
   weight += ((i>>j) & 1)*W[j];
   if (weight > C)
    break;
   value += ((i>>j) & 1)*V[j];
  }
  if (maxvalue < value) {        // 当前最大价值
   flag = i;
   maxvalue = value;
  }
 }
 print_rlt(flag, W, V, n, maxvalue);    // 打印结果
}

2) 迭代实现回溯：

// 非递归实现，即用迭代/循环实现回溯
int backtrack_iter(int* maxflag, int* W, int* V, int n, int C)
{
 int k = 0, val = 0, maxval = 0;    // k用来指示当前所在位置(想迷宫那样的位置)
 int rem = C;                       // 背包剩余容量
        // 访问状态，对于背包，只有1，2，3三种状态：1试图放入背包，2不放入背包，
        // 3状态访问完全，需要回溯到上一个节点。其它应用中，可以使用n+1个状态
 int* visit = new int[n];           
 int* flag = new int[n];
 memset(visit, 0, sizeof(int)*n);   // 初始化
 memset(flag, 0, sizeof(int)*n);   

 while (k >= 0) {                   // 当k<0时，回溯到初始
  for (; k < n; ++k) {       // 遍历当前路径一下的节点
   visit[k]++;        // 更新状态
   if (visit[k] == 1) {       // 第一次访问，试着装此货物到背包
    if (W[k] <= rem) {     // 能装下i货物，更新背包
     val += V[k];
     rem -= W[k];
     flag[k] = 1;
    } else {                 // 装不下，剪枝
     break;
    }
   } else if (visit[k] == 2) {      // 第二次访问，不装入背包
    if (flag[k]==1)          // 如果初次装入，则拿出
    {
     val -= V[k];
     rem += W[k];
    }
    flag[k] = 0;
   } 
                        else {     // visit[k]==3,第三次访问，状态遍历完，跳出以回溯
    visit[k]=0;  // 更新状态，下次重新访问  
    --k;
    break;
   }
  }
  if (maxval < val) {     // 此次遍历得到当前最大值？
   maxval = val;
   copy(flag, flag+n, maxflag);
  }

  if (k==n)              // 访问到叶节点？如果是，则变k，程序需要
   --k;
 }
 return maxval;
}

字符串匹配(2)-普通模式匹配

    主要是关于CLRS的笔记。所谓模式匹配，很好理解，就是在Emacs中crtl+s,或者Word中ctrl+f,即查找一个输入子串的位置。如找gitt在sagittarix中的位置。五中方法可以解决：1) 蛮力/朴素(两词一个意思)；2) Rabin-Karp；3)有限自动机；4)Knuth-Morris-Pratt算法(KMP)；5) Boyer-More(BM)算法
1) 朴素，老老实实一步一步做
2) 将子串转化成k进制数，比较数或者(模)
3) 有限自动机这东西不熟，希望自己能在下面给出它的代码
4) KMP的主要思想是用前缀函数来做，即用前缀函数记下某一模式前缀在模式中出现的下一位置，这样可以减少比较次数。
5) BM据说与KMP很像，但是不太清楚，有空时看看。
2)~5)之所以比1)快，是因为用到了预处理，以及充分削减了1)中的重复比较。下面给出有限自动机和KMP的代码。
有限自动机实现代码：
KMP实现代码：

字符串匹配(1) - 近似串匹配

    近似串就是并非完全相同的串(如happy和hsppy，或者pattern和patern)，它们之间或者有字母不同，或者少掉一些字母，或者多一些字母。定义近似串之间的差别数为通过“修改，删去 或者 插入”使两串达到完全一致的操作次数。如aproxiomally与approximatly之间的差别数就是3。近似串匹配就是一种特殊的模式匹配--找到与模式差别数最少的子串。差别数为0，就退化为普通的串模式匹配问题。
    问题用动态规划解决。定义差别函数D(i,j)(0<=i<=m, 0<=j<=n)表示样本前缀子串p1,...,pi与文本前缀子串t1,...,tj之间的最小差别数，则D(m,n)表示样本P与文本T的最小差别数。当p1,...,pi与t1,...,tj对应时，D(i,j)有四种情况：
1) 字符pi与tj对应且pi=tj，此时对应差别数为D(i-1,j-1);
2) 字符pi与tj对应且pi!=tj，此时对应差别数为D(i-1,j-1)+1;
3) 字符pi多余，即pi对应于tj后的空，则对应差别数为D(i-1,j)+1;
4）字符tj多余，即pi对应于t(j-1)，则对应差别数为D(i,j-1)+1;
所以，递推关系可如下表示(D矩阵大小为(m+1)x(n+1),第一行与第一列为padding，起重要作用)：
当pi=tj时，D(i,j)=min(D(i-1,j-1), D(i-1,j)+1, D(i,j-1)+1);
当pi!=tj时，D(i,j)=min(D(i-1,j-1)+1, D(i-1,j)+1, D(i,j-1)+1);
初始值设置如下：
1) D(0,j) = 0;
2) D(i,0) = i;
    特别注意，D(0,j)的设置与递推关系一样，是本方法的两个最重要的关键点。D(0,j)设置为0表明计算差别数时t1,...,tj中前面一部分是不算进去的，即差别数只是统计了t_k,...,tj的部分(这里k为某一值)！举个例子，如求D[1][10]时(假设p1=t10), D[0][9]为0，从第9或第10个字母起开始统计代价，关键关键！！

---

程序代码如下：

int mymin(int& index, int a, int b, int c)
{
 int min = a;
        index = 1;
 if (min > b){
     min = b; index = 2;
 }
 if (min > c){
     index = 3;
     min = c;
 }
 return min;
}

// 递归打印匹配的近似子串
void print_pat_match(string& text, int** dirt, int i, int j)
{
 if (i<0 || j<0)  // boundary
  return;
 
 if (dirt[i][j] == 1) {       // 1代表此处pi与tj是对应的
  print_pat_match(text, dirt, i-1, j-1);
  cout << text[j];
 }
 else if (dirt[i][j] == 2){   // 2代表往上，即pi对应空，或者说pi是多出的
  print_pat_match(text, dirt, i-1, j);
 }
 else{                        // 3代表往左，即tj对应空，或者说tj是多出的
  print_pat_match(text, dirt, i, j-1);
 }
}

int approx_match(string& text, string& pat)
{
 int m = pat.size();          // 模式串长度
 int n = text.size();         // 文本串长度
 int i,j;
 int** cost = new int*[m+1];  // 代价表
 for (i = 0; i <= m; ++i)
     cost[i] = new int[n+1];
 
 int** dirt = new int*[m];  // 用于追踪匹配时的选择，值为1，2或者3，代表3方向
 for (i = 0; i < m; ++i)
     dirt[i] = new int[n];
 for (i = 0; i < m; i++)
     for (j = 0; j < n; j++)
  dirt[i][j] = 0;
 
 for (j = 0; j <= n; ++j) //  代价初始化
  cost[0][j] = 0;
 for (i = 0; i <= m; ++i)
  cost[i][0] = i;

 int index;   int min_n = n, min_cost=100;
 // 动态规划
 for (i = 1; i <= m; ++i){
     for (j = 1; j <= n; ++j){
  if (text[j-1] == pat[i-1]){
      cost[i][j] = mymin(index, cost[i-1][j-1], 
                                 cost[i-1][j]+1, cost[i][j-1]+1);
  }
  else{
      cost[i][j] = mymin(index, cost[i-1][j-1]+1, 
                                 cost[i-1][j]+1, cost[i][j-1]+1);
  }
  dirt[i-1][j-1] = index;  // 方向，方法可参看CLRS中解LCS的方法
     }
 }

 for (j = 0; j <= n; j++){
     if (min_cost > cost[m][j]){
  min_n = j;
  min_cost = cost[m][j];
     }
 }
 print_pat_match(text, dirt, m-1, min_n-1);  // 打印子串
 cout << endl;
 return min_cost;                                // 返回最小差别数
}

int main()
{
 string text("Have a hsssppy day!");   // 文本串
 string pat("happy");                  // 模式
 int diff = approx_match(text, pat);   // 近似串差别数
 cout << "diff = " << diff << endl;
}

空间复杂度仍然可以改进到O(n)，不在赘述。

最长连续公共子序列

最长公共子序列可以分成连续的子序列和非连续的子序列，后者在CLRS中称为LCS。这里主要给出的连续的公共子序列的算法及其程序。

主要有3种解法：1) 暴力法； 2) DP(矩阵型—>线型)；3) 后缀树。

1) 简单，不用赘述。

2) Dynamic Programming (连续与不连续情况都适用)

\	e	d	c	e	d	n
n	0	0	0	0	0	1
c	0	0	1	0	0	0
e	1	0	0	1	0	0
d	0	1	0	0	1	0
t	0	0	0	0	0	0

我们把两个字符串看作矩阵的x-y轴：首先遍历字符串时，把两个字符相同的位置标记成1，不相同的地方标记成0。很容易证明，如果能形成公共子序列，则最长子序列一定是从某个位置开始的对角线的长度，所以我们需要做的就是统计对角线的长度。

例如str1=”ncedt”与str2=”edcedn”生成的矩阵如左矩阵，遍历找到最长的对角线即可。

	e	d	c	e	d	n
n	0	0	0	0	0	1
c	0	0	1	0	0	0
e	1	0	0	2	0	0
d	0	2	0	0	3	0
t	0	0	0	0	0	0

其实这里还可以优化，即在生成表格的时候，加上对角线上比它前面的元素，这样一遍遍历就可以生成左图所示矩阵，中间记下最大值便可，省下最后一趟比较，降低时间复杂度；空间复杂度也可降低，其实只要一维的数组便可以了，因为每次更新只用到上面一行(或左边一列，看你程序怎么写了，都可以)。

这个直观上很好理解，但拆分到子问题的思想表达起来比较绕，就转一下别人的文字：

---------------------------------------------------------------------------------------------------------------------

定义f(m, n)为串Xm和Yn之间最长的子字符串的长度并且该子字符串结束于Xm 和 Yn。因为要求是连续的，所以定义f的时候多了一个要求，即字符串结束于Xm 和 Yn。

于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 则f(m, n) = 0
如果xm = yn, 则f(m, n) = f(m-1, n-1) + 1
因为最长字符串不一定结束于Xm 和 Yn末尾，所以这里必须求得所有可能的f(p, q) | 0 <>最大的f(p, q)就是解。依照公式用Bottom-up DP可解。

代码就不写了，简单。但是它与其它的DP填表又有所不同，不是直接得出最大的填到表格最后一格中，而是找出格子中的最大值，其中差别，细细体会。刚开始我在想的时候，就是受了之前的做法的影响，迟迟得不到思路，唉～～

3) 广义后缀树(generalized )

关于后缀树(suffix tree)的材料：

http://www.allisons.org/ll/AlgDS/Tree/Suffix/#demoForm

http://www.answers.com/suffix-tree

http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm#substring

http://www.nist.gov/dads/HTML/suffixtree.html

http://blog.csdn.net/love_apple/archive/2007/02/12/1508758.aspx

广义后缀树只是简单修改，如str1和str2一起建一棵后缀树，然后每个子串标记其出处，最长的来自两个串的子串相连就是最长公共连续子串。后缀树的构建比较复杂，现在还没有时间实现。

Dynamic Programming(2)

可以用动态规划解决的几个常见问题：

---

• 组合问题中的动态规划：
  
  1. 0-1背包问题；
  2. 最长公共子序列(包括连续的和非连续的两种，都可以用DP做，不过连续的用suffix tree做可以达到O(n)的时间复杂度)；
  3. 最大子段和问题，即求一个数列中和为最大的一个连续子段(DP需要O(n)就可以解决，brute force最少要O(n^2), 分治要O(nlgn)，DP费时最短)；
  4. 硬币找换问题
  
  
• 图问题中有：
  1. TSP问题(travelling salesman problem)：旅行n个城市，要求各个城市经历且仅经历一次，然后回到出发城市，要求所走的路程最短；
  2. 多段图的最短路径
  
  
• 查找问题：
  1. 最优二叉查找树(注意与Hofmann编码树区别开)；
  2. 近似串匹配问题
  
  
• 其他：
  1. 装配线调度问题；
  2. 矩阵连乘法问题
  
  

     【注：学习DP，《算法导论》和《算法设计与分析》都是不错的教材。】
     其实能用DP解决的问题很多都可以用回朔剪枝或分治解决。

Dynamic Programming(1)

连续的笔试面试，碰到了好几次动态规划的题，都没有写全，终于下定决心来搞定它，权当笔记，行家莫笑。
有DP解的算法问题要求两个条件：1) 最优子结构 2)重叠子问题，这是DP的核心。一下分别列出几个经典的DP问题。

---

1. 0-1背包问题
在一定容量的背包中放物品，求得到价值最大的情况，代码如下所示：

int set_package(int* W, int* V, int n, int C);
int main()
{
   int W[] = {35, 30, 60, 50, 40, 10, 25};      // 物体重量
   int V[] = {10, 40, 30, 50, 35, 40, 30};      // 物体价值
   int n = 7;                                   // 几个物体
   int capacity = 150;                          //  背包容量
   int value = set_package(W, V, n, capacity);  // 动态规划
   cout << "Total max value is: " << value << endl;
}  

// W: 重量,  V: 价值,  n: 物体种类  C: 背包容量 
int set_package(int* W, int* V, int n, int C) 
{     
    int i, j;     
    int** tabv = new int*[C+1];  
    // 存放动态规划临时结果     
    for (i = 0; i <= C; i++)
         tabv[i] = new int[n+1];
    bool* index = new bool[n];    // 某一物体是否被放入背包      
    for (i = 0; i <=C; i++)       // 初始化最左一列和最下一行  
         tabv[i][0] = 0;     
    for (j = 0; j <= n; j++)  
         tabv[0][j] = 0;          
    
    // 在每个容量i下，去装前j个物体所能达到的最大价值放入tabv[i][j]中     
    for (i = 1; i <= C; i++){         
        for (j = 1; j <= n; j++) {      
            if (i >= W[j-1]) // 若背包能装下j物体，W[j-1]代表j物体重量
         tabv[i][j] = cal_max(V[j-1]+tabv[i-W[j-1]][j-1], tabv[i][j-1]);
     else
  tabv[i][j] = tabv[i][j-1]; 
               // 若装不下，则最大价值就是前j-1个物体最大价值
 }
    }

   // 从tabv数组反求物体列表
   i = C;
   for (j = n; j > 0; --j) {
   // 如果i容量下，装前j个物体价值大于前j-1个物体最大价值，则第j个物体肯定被装到包里
        if (tabv[i][j] > tabv[i][j-1]) {    
              index[j-1] = true;
              i -= W[j-1];  // substract weight of the jth object
         }
         else
              index[j-1] = false; //
   }

   // 打印结果，省略...
   return tabv[C][n];   //返回结果
}

    这里中间过程的表格其实可以缩减到一维，因为tabv[i][j]只用到j-1列的值，所以可以改进空间复杂度为O(C)而非O(nC)，这个比较简单，就不贴上来了。值得注意的是这样要找到哪几个物体被选中就变得复杂一些，需要中间记下一些变量。

从此，这个就是我的技术博了

三分薄田，可以耕耘，不求收获，只求记忆。