AIRobot quick note

• Machine Learning
• Computer Vision
• review Network and Computer Organization
• some others
• earn some pocket money
• a hidden goal (optional)

Chapter 2 总结 (Summary)

Lisp 是一种交互式语言。如果你在顶层输入一个表达式， Lisp 会显示它的值。

Lisp 程序由表达式组成。表达式可以是原子，或一个由操作符跟着零个或多个实参的列表。前序表示法代表操作符可以有任意数量的实参。

Common Lisp 函数调用的求值规则： 依序对实参从左至右求值，接着把它们的值传入由操作符表示的函数。 quote 操作符有自己的求值规则，它完封不动地返回实参。

除了一般的数据类型， Lisp 还有符号跟列表。由于 Lisp 程序是用列表来表示的，很轻松就能写出能编程的程序。

三个基本的列表函数是 cons ，它创建一个列表； car ，它返回列表的第一个元素；以及 cdr ，它返回第一个元素之后的所有东西。

在 Common Lisp 里， t 表示逻辑 真 ，而 nil 表示逻辑 假 。在逻辑的上下文里，任何非 nil 的东西都视为 真 。基本的条件式是 if 。 and 与 or 是相似的条件式。

Lisp 主要由函数所组成。可以用 defun 来定义新的函数。

自己调用自己的函数是递归的。一个递归函数应该要被想成是过程，而不是机器。

括号不是问题，因为程序员通过缩排来阅读与编写 Lisp 程序。

基本的 I/O 函数是 read ，它包含了一个完整的 Lisp 语法分析器，以及 format ，它通过字符串模板来产生输出。

你可以用 let 来创造新的局部变量，用 defparameter 来创造全局变量。
赋值操作符是 setf 。它的第一个实参可以是一个表达式。

函数式编程代表避免产生副作用，也是 Lisp 的主导思维。

基本的迭代操作符是 do 。

函数是 Lisp 的对象。可以被当成实参传入，并且可以用 lambda 表达式来表示。

在 Lisp 里，是数值才有类型，而不是变量。

Chapter 2 习题 (Exercises)

1. 描述下列表达式求值之后的结果：

(a) (+ (- 5 1) (+ 3 7))

答案：14

(b) (list 1 (+ 2 3))

答案：(1 5)

(c) (if (listp 1) (+ 1 2) (+ 3 4))

答案：7

(d) (list (and (listp 3) t) (+ 1 2))

答案：(NIL 3)

2. 给出 3 种不同表示 (a b c) 的 cons 表达式 。

答案：

1
2
3

(cons 'a '(b c))
(cons 'a (cons 'b '(c)))
(cons 'a (cons 'b (cons 'c nil)))

3. 使用 car 与 cdr 来定义一个函数，返回一个列表的第四个元素。

答案：

1
2

(defun get-forth(lst)
  (car (cdr (cdr (cdr lst)))))

4. 定义一个函数，接受两个实参，返回两者当中较大的那个。

答案：

1
2
3
4

(defun get-max(x y)
  (if (< x y)
    y
    x))

5. 这些函数做了什么？

(a)

1
2
3
4

(defun enigma (x)
  (and (not (null x))
       (or (null (car x))
           (enigma (cdr x)))))

答案：判断 x 列表中是否有 nil 元素

(b)

1
2
3
4
5
6
7

(defun mystery (x y)
  (if (null y)
    nil
    (if (eql (car y) x)
      0
      (let ((z (mystery x (cdr y))))
        (and z (+ z 1))))))

答案：查找 x 在列表 y 中的下标，如果没有则为 nil

6. 下列表达式， x 该是什么，才会得到相同的结果？

(a)

1
2
3

> (car (x (cdr ‘(a (b c) d))))

B

答案：car

(b)

1
2
3

> (x 13 (/ 1 0))`

13

答案：or

(c)

1
2
3

> (x #’list 1 nil)

(1)

答案：or ‘(1) 或 apply

7. 只使用本章所介绍的操作符，定义一个函数，它接受一个列表作为实参，如果有一个元素是列表时，就返回真。

答案：

非递归版本

1
2
3
4
5

(defun has-child-list (lst)
  (let ((x nil))
    (dolist (obj lst)
      (setf x (or x (listp obj))))
    x))

递归版本

1
2
3
4
5
6

(defun has-child-list-re (lst)
  (if (null lst)
    nil
    (if (listp (car lst))
      t
      (has-child-list-re (cdr lst)))))

8. 给出函数的迭代与递归版本：

a. 接受一个正整数，并打印出数字数量的点。

答案：

非递归版本

1
2
3
4

(defun print-dots (n)
  (do ((i 0 (+ i 1)))
    ((= i n ) 'done)
    (format t ".")))

递归版本

1
2
3
4
5
6

(defun print-dots-re (n)
  (if (= n 0)
    'done
    (progn
      (format t ".")
      (print-dots-re (- n 1)))))

b. 接受一个列表，并返回 a 在列表里所出现的次数。

答案：

非递归版本：

1
2
3
4
5

(defun print-a-times (lst)
   (let ((flag 'a)(x 0))
     (dolist (obj lst)
       (setf x (+ x (if (eql obj flag) 1 0))))
     x))

递归版本：

1
2
3
4
5
6

(defun print-a-times-re (lst)
  (if (null lst)
    0
    (let ((flag 'a))
      (+ (if (eql flag (car lst)) 1 0)
         (print-a-times-re (cdr lst))))))

9. 一位朋友想写一个函数，返回列表里所有非 nil 元素的和。他写了此函数的两个版本，但两个都不能工作。请解释每一个的错误在哪里，并给出正确的版本。

(a)

1
2
3

(defun summit (lst)
  (remove nil lst)
  (apply #'+ lst))

答案：因为 remove 并不会改变 lst 本身。正确的程序：

1
2
3

(defun summit (lst)
  (let ((newlst (remove nil lst)))
    (apply #'+ newlst)))

(b)

1
2
3
4
5

(defun summit (lst)
  (let ((x (car lst)))
    (if (null x)
      (summit (cdr lst))
      (+ x (summit (cdr lst))))))

答案：因为递归没有边界退出分支。正确的程序：

1
2
3
4
5
6
7

(defun summit (lst)
  (if (null lst)
    0
    (let ((x (car lst)))
      (if (null x)
        (summit (cdr lst))
        (+ x (summit (cdr lst)))))))

前言

OpenMp和MPI是常用并行计算库，OpenMP相对简单适合单机多核多线程，MPI适合集群，但复杂。

OpenMp是由OpenMP Architecture Review Board牵头提出的，并已被广泛接受的，用于共享内存并行系统的多处理器程序设计的一套指导性的编译处理方案(Compiler Directive)。OpenMP支持的编程语言包括C语言、C++和Fortran；而支持OpenMp的编译器包括Sun Compiler，GNU Compiler和Intel Compiler等。OpenMp提供了对并行算法的高层的抽象描述，程序员通过在源代码中加入专用的pragma来指明自己的意图，由此编译器可以自动将程序进行并行化，并在必要之处加入同步互斥以及通信。当选择忽略这些pragma，或者编译器不支持OpenMp时，程序又可退化为通常的程序(一般为串行)，代码仍然可以正常运作，只是不能利用多线程来加速程序执行。

使用

基本使用很简单。G++编译时加上-fopenmp

以下为引用：

1.
OpenMP是一种API，用于编写可移植的多线程应用程序，无需程序员进行复杂的线程创建、同步、负载平衡和销毁工作。
使用OpenMP的好处：

• 1）CPU核数扩展性问题
• 2）方便性问题
• 3）可移植性问题

OpenMP指令和库函数介绍:

在C/C++中，OpenMP指令使用的格式为:#pragma omp 指令 [子句[子句]…]

用法详见OpenMP编程指南。

2.

1
2
3
4
5

#pragma omp parallel for
       for(i=0;i<length;i++)
       {
           //没有循环迭代相关的语句,如把图像数组中的RGB值转为灰度值。
       }

3.
对可以以多线程执行的循环的约束：

• 1）循环变量必须是有符号整型，如果是无符号整型，就无法使用
• 2）比较操作必须是<,>,<=,>=
• 3）循环步长必须是整数加或整数减操作，加减的操作必须是一个不变量
• 4）如果是<,<=，循环变量的值每次迭代时必须增加，否则减小
• 5）循环内部不允许有能够到达循环之外的跳转语句，也不允许有外部的跳转语句到达循环内部。exit语句例外，goto 和break的跳转范围必须在循环内部，异常处理也必须在循环内部处理

4.
数据相关（以下假设为语句S2与语句S1存在数据相关）：
相关的种类（相关不等于循环迭代相关）：

• 1）流相关：S1先写某一存储单元，而后S2又读该单元
• 2）输出相关：两个语句写同一存储单元
• 3）反相关：一个语句先读一单元，然后另一语句写该单元

相关产生的方式：

• 1）S1在循环的一次迭代中访问存储单元L，S2在随后的一次迭代中访问L（是循环迭代相关）
• 2）S1和S2在同一循环迭代中访问同一存储单元L，但S1的执行在S2之前。（非循环迭代相关）

5.
数据竞争：

数据竞争可能是由于输出相关引起的，编译器不会进行数据竞争的检测，Intel线程检测器可以检测数据竞争。
用类似于互斥量的机制进行私有化和同步，可以消除数据竞争。

1
2
3
4
5
6
7

#pragma omp parallel for private(x)
       for(i=0;i<80;i++)
       {
         x=sin(i);
         if(x>0.6)x=0.6;
         printf("sin(%d)=%f\n",i,x); 
       }

6.
管理共享数据和私有数据：

• private:每个线程都拥有该变量的一个单独的副本，可以私有的访问
  • 1）private：说明列表中的每个变量对于每个线程都应该有一个私有副本。这个私有副本用变量的默认值进行初始化
  • 2）firstprivate:见13数据的Copy-in 和Copy-out
  • 3）lastprivate:见13数据的Copy-in 和Copy-out
  • 4）reduction:
  • 5）threadprivate:指定由每个线程私有的全局变量
• 有三种方法声明存储单元为私有：
  • 1）使用private,firstprivate,lastprivate,reduction子句
  • 2）使用threadprivate
  • 3）在循环内声明变量，并且不使用static关键字
• shared:所有线程都能够访问该单元，并行区域内使用共享变量时，如果存在写操作，必须对共享变量加以保护
• default:并行区中所有变量都是共享的，除下列三种情况下：
  • 1）在parallel for循环中，循环索引时私有的。
  • 2）并行区中的局部变量是私有的
  • 3）所有在private,firstprivate,lastprivate,reduction子句中列出的变量是私有的

7.
循环调度与分块

为了提供一种简单的方法以便能够在多个处理器之间调节工作负载，OpenMP给出了四种调度方案：
static,dynamic,runtime,guided.

默认情况下，OpenMP采用静态平均调度策略，但是可以通过调用schedule(kind[,chunksize])子句提供循环调度信息

如：#pragma omp for schedule (kind[,chunk-size]) //chunk-size为块大小

guided根据环境变量里的设置来进行对前三种的调度

在windows环境中，可以在”系统属性|高级|环境变量”对话框中进行设置环境变量。

8.
有效地使用归约：

1
2
3
4
5

sum=0;
for(k=0;k<100;k++)
{
    sum=sum+func(k);
}

为了完成这种形式的循环计算，其中的操作必须满足算术结合律和交换律，同时sum是共享的，这样循环内部都可以加给这个变量，同时又必须是私有的，以避免在相加时的数据竞争。

reduction子句可以用来有效地合并一个循环中某些关于一个或多个变量的满足结合律的算术归约操作。reduction子句主要用来对一个或多个参数条目指定一个操作符，每个线程将创建参数条目的一个私有拷贝，在区域的结束处，将用私有拷贝的值通过指定的运行符运算，原始的参数条目被运算结果的值更新。

1
2
3
4
5
6

sum=0;
#pragma omp parallel for reduction(+:sum)
for(k=0;k<100;k++)
{
    sum=sum+func(k);
}

9.
降低线程开销：

当编译器生成的线程被执行时，循环的迭代将被分配给该线程，在并行区的最后，所有的线程都被挂起，等待共同进入下一个并行区、循环或结构化块。
如果并行区域、循环或结构化块是相邻的，那么挂起和恢复线程的开销就是没必要的。

举例如下：

1
2
3
4
5
6
7
8
9
10
11

#pragma omp parallel //并行区内
{
   #pragma omp for // 任务分配for循环
   for(k=0;k<m;k++){
     fun1(k);
   }
   #pragma omp for
   for(k=0;k<m;k++){
     fun2(k);
   }
}

10.任务分配区：

现实中应用程序的所有性能敏感的部分不是都在一个并行区域内执行，所以OpenMP用任务分配区这种结构来处理非循环代码。

任务分配区可以指导OpenMP编译器和运行时库将应用程序中标示出的结构化块分配到用于执行并行区域的一组线程上。

举例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#pragma omp parallel //并行区内
{
  #pragma omp for // 任务分配for循环
  for(k=0;k<m;k++){
    fun1(k);
  }
  #pragma omp sections private(y,z)
  {
    #pragme omp section//任务分配section
    {y=sectionA(x);}
    #pragme omp section
    {z=sectionB(x);}
  }                   
}

11.
使用Barrier和Nowait:

栅障（Barrier）是OpenMP用于线程同步的一种方法。线程遇到栅障是必须等待，直到并行区中的所有线程都到达同一点。

注意：在任务分配for循环和任务分配section结构中，我们已经隐含了栅障，在parallel,for,sections,single结构的最后，也会有一个隐式的栅障。
隐式的栅障会使线程等到所有的线程继续完成当前的循环、结构化块或并行区，再继续执行后面的工作。可以使用nowait去掉这个隐式的栅障

去掉隐式栅障，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#pragma omp parallel //并行区内
{
  #pragma omp for nowait // 任务分配for循环
  for(k=0;k<m;k++){
    fun1(k);
  }
  #pragma omp sections private(y,z)
  {
    #pragme omp section//任务分配section
    {y=sectionA(x);}
    #pragme omp section
    {z=sectionB(x);}
  }                   
}

因为第一个 任务分配for循环和第二个任务分配section代码块之间不存在数据相关。

加上显示栅障，例如：

1
2
3
4
5
6
7
8
9
10
11
12

#pragma omp parallel shared(x,y,z) num_threads(2)//使用的线程数为2
{
  int tid=omp_get_thread_num();
  if(tid==0)
    y=fun1();//第一个线程得到y
  else 
    z=fun2();//第二个线程得到z
  #pragma omp barrier //显示加上栅障，保证y和z在使用前已有值
  #pragma omp for
  for(k=0;k<100;k++)
    x[k]=y+z;
}

12.
单线程和多线程交错执行：

当开发人员为了减少开销而把并行区设置的很大时，有些代码很可能只执行一次，并且由一个线程执行，这样单线程和多线程需要交错执行

举例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#pragma omp parallel //并行区
{
  int tid=omp_get_thread_num();//每个线程都调用这个函数，得到线程号
  //这个循环被划分到多个线程上进行
  #pragma omp for nowait
  for(k=0;k<100;k++)
    x[k]=fun1(tid);//这个循环的结束处不存在使所有线程进行同步的隐式栅障
  #pragma omp master
  y=fn_input_only(); //只有主线程会调用这个函数
  #pragma omp barrier   //添加一个显示的栅障对所有的线程同步，从而确保x[0-99]和y处于就绪状态
  //这个循环也被划分到多个线程上进行
  #pragma omp for nowait
  for(k=0;k<100;k++)
    x[k]=y+fn2(x[k]); //这个线程没有栅障，所以不会相互等待
  //一旦某个线程执行完上面的代码，不需要等待就可以马上执行下面的代码
  #pragma omp single //注意：single后面意味着有隐式barrier
  fn_single_print(y);
  //所有的线程在执行下面的函数前会进行同步
  #pragma omp master
  fn_print_array(x);//只有主线程会调用这个函数
}

13.
数据的Copy-in 和Copy-out:

在并行化一个程序的时候，一般都必须考虑如何将私有变量的初值复制进来（Copy-in ），以初始化线程组中各个线程的私有副本。

在并行区的最后，还要将最后一次迭代/结构化块中计算出的私有变量复制出来（Copy-out），复制到主线程中的原始变量中。

firstprivate:使用变量在主线程的值对其在每个线程的对应私有变量进行初始化。一般来说，临时私有变量的初值是未定义的。

lastprivate:可以将最后一次迭代/结构化块中计算出来的私有变量复制出来，复制到主线程对应的变量中，一个变量可以同时用firstprivate和lastprivate来声明。

copyin:将主线程的threadprivate变量的值复制到执行并行区的每个线程的threadprivate变量中。

copyprivate:使用一个私有变量将某一个值从一个成员线程广播到执行并行区的其他线程。该子句可以关联single结构(用于single指令中的指定变量为多个线程的共享变量)，在所有的线程都离开该结构中的同步点之前，广播操作就已经完成。

14.
保护共享变量的更新操作：

OpenMP支持critical和atomic编译指导，可以用于保护共享变量的更新，避免数据竞争。包含在某个临界段且由atomic编译指导所标记的代码块可能只由一个线程执行。

例如：

1
2
3
4

#pragma omp critical
{
  if(max<new_value) max=new_value;
}

15.
OpenMP库函数（#include <omp.h>）：

1
2
3
4
5
6
7

int omp_get_num_threads(void); //获取当前使用的线程个数

int omp_set_num_threads(int NumThreads);//设置要使用的线程个数

int omp_get_thread_num(void);//返回当前线程号

int omp_get_num_procs(void);//返回可用的处理核个数

16.
编译OpenMP要需要一个支持OpenMP的编译器和线程安全的运行时库。vs2005的配置属性C/C++语言里提供对OpenMP的支持。

编译时假如出现”没有找到vcompd.dll,因此这个应用程序未能启动。重新安装应用程序可能会修复此问题”，
可能的原因是该项目有可能是从VC移植过来的，如果由VS创建，一般不会出现该问题，因为VS会解决在清单文件的调用dll问题。

解决方法如下：

StdAfx.h中加入

1

#pragma comment(linker, "\"/manifestdependency:type='Win32' name='Microsoft.VC80.DebugOpenMP' version='8.0.50608.0' processorArchitecture='X86' publicKeyToken='1fc8b3b9a1e18e3b' language='*'\"")

或者在Linker -> Manifest File -> Additional Manifest Dependencies -> 中加入：

1

"type='Win32' name='Microsoft.VC80.DebugOpenMP' version='8.0.50608.0' processorArchitecture='X86' publicKeyToken='1fc8b3b9a1e18e3b' language='*'"

资料

http://www.openmp.org/

A - An easy problem A

Time Limit: 1000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

N个数排成一列，Q个询问，每次询问一段区间内的数的极差是多少。

Input

第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ….an,(1≤ai≤1000000000)。接下来Q行，每行两个整数L,R(1≤L≤R≤N)。

Output

对于每个询问输出一行，一个整数表示区间内的极差。

Sample input and output

Sample Input

1
2
3
4
5

5 3
3 2 7 9 10
1 5
2 3
3 5

Sample Output

1
2
3

8
5
3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50000;

typedef struct
{
    int left,right,maxv,minv;
}Node;
Node rt[MAXN<<2];
int a[MAXN+5];

void build(int x, int L, int R)
{
    rt[x].left = L; rt[x].right = R;
    if(L==R)
    {
        rt[x].maxv = rt[x].minv = a[L];
        return ;
    }
    int mid = L + R >>1;
    build(x<<1,L,mid); build((x<<1)+1,mid+1,R);
    rt[x].maxv = max(rt[x<<1].maxv,rt[(x<<1)+1].maxv);
    rt[x].minv = min(rt[x<<1].minv,rt[(x<<1)+1].minv);
}

Node query(int x, int L, int R)
{
    Node t,tt;
    int mid = (rt[x].left + rt[x].right)>>1;
    if(L == rt[x].left && R == rt[x].right)
    {
        return rt[x];
    }
    else if(R<=mid)
    {
        tt = query(x<<1,L,R);
        t.maxv = tt.maxv;
        t.minv = tt.minv;
        return t;
    }
    else if(L>mid)
    {
        tt = query((x<<1)+1,L,R);
        t.maxv = tt.maxv;
        t.minv = tt.minv;
        return t;
    }
    else
    {
        t = query(x<<1,L,mid);
        tt = query((x<<1)+1,mid+1,R);
        t.maxv = max(t.maxv,tt.maxv);
        t.minv = min(t.minv,tt.minv);
        return t;
    }

}

int main()
{
    int n,q,l,r;
    Node t;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    build(1,1,n);
    //for(int i=1;i<=9;++i)
        //printf("%d,%d\t",rt[i].maxv,rt[i].minv);
    while(q--)
    {
        scanf("%d %d",&l,&r);
        t = query(1,l,r);
        printf("%d\n",t.maxv-t.minv);
    }

    return 0;
}