Joyce' Blog
0%

发表于

Translation

近年来,中国越来越多的博物馆免费向公众开放。博物馆展览次数和参观人数都明显增长。在一些广受欢迎的博物馆门前,排长队已很常见。这些博物馆必须采取措施限制参观人数。如今,展览形式越来越多样。一些大型博物馆利用多媒体和虚拟现实等先进技术,使展览更具吸引力。不少博物馆还举办在线展览,人们可在网上观赏珍稀展品。然而,现场观看展品的体验对大多数参观者还是更具吸引力。

In recent years, more and more museums in China have been opened to the public for free. The number of museums exhibitions and visitors have increased significantly. Queuing up in front of some popular museums is very common, and these museums must take measures to restrict the number of visitors. Today, the form of exhibitions is becoming more diverse. Some large museums use advanced technologies such as multimedia and virtual reality, to make exhibitions more attractive. Many museums also hold online exhibitions where people can view rare exhibits on the Internet. However, the experience of viewing exhibits on site is still more attractive to most visitors.

notes

exhibit [ɪɡˈzɪbɪt] v.展览;展出;表现，显示，显出(感情、品质或能力)
n.(一件)展览品，陈列品;(在法庭上出示的)物证，证据

on site 在现场;临场

发表于

一个表中的 FOREIGN KEY 指向另一个表中的 UNIQUE KEY(唯一约束的键)。

在创建表的时候指定外键约束：

1
2
3
CONSTRAINT 外键约束名 FOREIGN KEY  (column1,column2,... column_n) 
        REFERENCES 外键依赖的表 (column1,column2,...column_n)
        ON DELETE CASCADE--级联删除

在创建表后增加外键约束:

1
2
3
4
5
ALTER TABLE 表名
    ADD CONSTRAINT 外键约束名
    FOREIGN KEY (column1, column2,...column_n) 
    REFERENCES 外键所依赖的表 (column1,column2,...column_n)
    ON DELETE CASCADE;--级联删除

顺便记录yii框架使用过程中发现的一个疑问，以后解决：

在调用存储过程时，delete()中使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public function actionDelete($id)
{

    $username=Yii::$app->user->identity->username;
    $model = $this->findModel($id);
    if (!$model->load(Yii::$app->request->post())) {

        $command= Yii::$app->db
            ->createCommand('call proc_delete(:p0,:p1)')
            ->bindValues([":p0" =>$model->catid,":p1"=>$username]);
        $res=$command->execute();
        if($res>=0)
        {             
            return $this->redirect(['index']);
        }
    }
    return $this->redirect(['index']);
}

update()中使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public function actionUpdate($id)
    {
        $model = $this->findModel($id);
        if ($model->load(Yii::$app->request->post())) {

            $command= Yii::$app->db
                ->createCommand('call proc_update(:p0,:p1)')
                ->bindValues([":p0" =>$model->catid, ":p1" =>$model->price]);
            $res=$command->execute();
            if($res>=0)
            {             
                return $this->redirect(['view', 'id' => $model->catid]);
            }
        }
        return $this->render('update', [
            'model' => $model,
        ]);
    }

帮jz同学看了很久他的语句，才发现if条件语句中，delete()和update()差了一个感叹号，但具体原因现在先不探寻了。

发表于 更新于

分治策略

归并排序

递推关系

$$
T(n)=\begin{cases}
2T(n/2)+cn,\quad n>2 \\
c,\quad n=2
\end{cases}
$$

用归纳法可证：
$$
T(n)=O(nlogn)
$$

其他递推关系

$$
T(n)=\begin{cases}qT(n/2)+cn,\quad n>2 \\c,\quad n=2\end{cases}
$$

对于q>2，$T(n)=O(n^{log_2q})$

对于q=1，$T(n)=O(n)$
$$
T(n)=\begin{cases}2T(n/2)+cn^2,\quad n>2 \\c,\quad n=2\end{cases}
$$

$$
T(n)=O(n^2)
$$

计数逆序 $O(nlogn)$

Merge-and-Count(A,B)

1
2
3
4
5
6
7
8
9
10
11
12
维护一个Current指针指向每个表，初始化指向首元素
维护一个变量Count用于逆序的计数，初始为0
While两个表都不空
	令ai和bj是由Current指针指向的元素
	把这两个表中娇小的元素输出到表中
	If bj是较小的元素 then
		把Count加上在A中的剩余元素数
	Endif
	把较小元素选出的表中的Current指针前移
EndWhile
一旦一个表为空，把另一个表剩余所有元素加到输出中
返回Count和合并后的表

Sort-and-Count(L)

1
2
3
4
5
6
7
8
9
10
11
If这个表中有一个元素 then
	没有逆序
Else
	把这个表划分成两半
	A包含前n/2个元素
	B包含剩下的n/2个元素
	(rA,A)=Sort-and-Count(A)
    (rB,B)=Sort-and-Count(B)
    (r,L)=Merge-and-Count(A,B)
Endif
返回r=rA+rB+r以及排好序的L

最邻近点对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Closest-Pair(p1, …, pn) { 
    //O(n log n)
    Compute separation line L such that half the points are on one side and half on the other side.      
    //2T(n / 2)
	δ1= Closest-Pair(left half) 
    δ2= Closest-Pair(right half) 
    δ= min(δ1, δ2)
    //O(n) 
	Delete all points further than δ from separation line L
	//O(n log n)  改进时，通过预处理去掉这一步排序
    Sort remaining points by y-coordinate.
    //O(n)
	Scan points in y-order and compare distance between each point and next 7 neighbors. If any of these distances is less than δ, update δ.
	return δ.
}

上面算法的时间复杂度为$T(n)=O(nlog^2n)$

改进后时间复杂度为$T(n)=O(nlogn)$

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
Closest-Pair-Rec(Px,Py) {
    If |P|<=3 then 
    	进行简单穷举排序 
        //在这里按y坐标将点排序，方便下面直接对窄带内的点归并排序
    End if
        
	构造Qx,Qy,Rx,Ry(O(n)时间) 
    （q0*,q1*）=Closest-Pair-Rec(Qx,Qy) 
    （r0*,r1*）=Closest-Pair-Rec(Rx,Ry)
        
	Delta=min(d(qo*,q1*),（r0*,r1*）) 
    x*=集合Q中的点的大的x坐标 
    L={(x,y):x=x*} 
	S=P中与L相距在Delta之内的点集

    构造Sy(O(n)时间) 
    For每个点Sy中的点s, 计算从s到跟着Sy的7个点中每个点的距离 
    令s,s'是达到其中小距离的点对(O(n)时间)

    If d(s,s')<Delta then 
         Return (s,s') 
    Else if d(q0*,q1*)<d(r0*,r1*) then
        Return (q0*,q1*) 
    Else 
        Return（r0*,r1*） 
    End if
}

整数乘法

公式

$x=x_12^{n/2}+x_0$

$y=y_12^{n/2}+y_0$

$xy=2^nx_1y_1+2^{n/2}(x_1y_0+x_0y_1)+x_0y_0$

$=2^nx_1y_1+2^{n/2}((x_1+x_0)(y_1+y_0)-x_1y_1-x_0y_0)+x_0y_0$

把4个乘法变成3个.

Recursive-Multiply(x,y) [Karatsuba-Ofman]

令$x=x_12^{n/2}+x_0，y=y_12^{n/2}+y_0$，

计算$x_1+x_0，y_1+y_0$，

p=Recursive-Multiply($x_1+x_0，y_1+y_0$)

x1y1=Recursive-Multiply(x1,y1)

x0y0=Recursive-Multiply(x0,y0)

return $x_1y_12^n+(p-x_1y_1-x_0y_0)2^{n/2}+x_0y_0$

在两个n位因数上的运行时间是 $T(n)=O(n^{log_23})=O(n^{1.59})$

矩阵乘积 (Strassen)

P1=A11×(B12−B22)

P2=(A11+A12)×B22

P3=(A21+A22)×B11

P4=A22×(B21−B11)

P5=(A11+A22)×(B11+B22)

P6=(A12−A22)×(B21+B22)

P7=(A11−A21)×(B11+B12)

$C_{22}=A_{22}B_{2*2}$

C11=P 5+P4−P 2+P 6

C12=P1+P2

C21=P3+P4

C22=P5+P1−P3−P7

7 次乘法，18 = 10 + 8 次加减法

$T(n)=O(n^{log_27})=O(n^{2.81})$

类Strassen算法上每获得一点理论上的改进， 实际上的可用性就会降低。 （需要n达到一定规模，例：两个70×70分块矩阵乘法可以用143,640次向量乘法 ）

卷积与快速傅立叶变换

多项式

系数表示 点值表示
求值 O(n) (采用Horner方法) O(n^2)
加法 O(n) arithmetic operations O(n) arithmetic operations
乘法(卷积) 采用直接算法O(n^2) 需要2n-1 个点 O(n)

系数表达到点值表达

把多项式表达分成奇偶部分。选择$x_k= ω^k$，其中ω是n次单位根。求$A(x) = a_0+ … + a_{n-1}x^{n-1}$在n次单位根$ω^0, ω^1, …, ω^{n-1}$处的值。

1559642308319

如果n是偶数，那么n/2次单位根可以表 示为$ν^0, ν^1, …, ν^{n/2-1}$，其中$ν= e ^{4πi / n}$.

$A(x) =A_{even}(x^2) + xA_{odd}(x^2)$. $A(-x) =A_{even}(x^2) - xA_{odd}(x^2)$.

分别计算多项式：

$A_{even}(x)$ ，$A_{odd}(x)$在$½n$th单位根$ν^0, ν^1, …, ν^{n/2-1}$处的值.

组合：

$A(ω^k) = A_{even}(ν^k) + ω^kA_{odd}(ν^k), 0 ≤k < n/2$

$A(ω^{k+n/2}) = A_{even}(ν^k) - ω^kA_{odd}(ν^k), 0 ≤k < n/2$

$ω^{k+n/2}= -ω^k，ν^k = (ω^k)^2 = (ω^{k+n/2})^2$

FFT算法 O(n log n)

fft(n,$a^0,a^1, …, a^{n-1}$) {

​ if(n == 1) return $a_0$

​ $(e_0,e_1,…,e_{n/2-1}) ←FFT(n/2, a_0,a_2,a_4,…,a_{n-2}) $

​ $(d_0,d_1,…,d_{n/2-1}) ←FFT(n/2, a_1,a_3,a_5,…,a_{n-1})$

​ for k = 0 to n/2 -1 {

​ $ω^k←e^{2πik/n}$

​ $y_k←e_k+ ω^kd_k$

​ $y_{k+n/2}←e_k-ω^kd_k$}

​ return ($y_0,y_1,…,y_{n-1}$)

}

傅立叶变换逆变换

1559642268376

$F_n×G_n=I_n$

把 $ω^{-1}=e^{-2πi / n}$看成是n次单位根的生成元.

IFFT算法 O(n log n)

ifft(n,$a^0,a^1, …, a^{n-1}$) {

​ if(n == 1) return $a_0$

​ $(e_0,e_1,…,e_{n/2-1}) ←FFT(n/2, a_0,a_2,a_4,…,a_{n-2}) $

​ $(d_0,d_1,…,d_{n/2-1}) ←FFT(n/2, a_1,a_3,a_5,…,a_{n-1})$

​ for k = 0 to n/2 -1 {

​ $ω^k←e^{-2πik/n}$

​ $y_k←(e_k+ ω^kd_k)/n$

​ $y_{k+n/2}←(e_k-ω^kd_k)/n$}

​ return ($y_0,y_1,…,y_{n-1}$)

}

发表于

复习时没有理解为什么使用优先队列的dijkstra和prim算法时间复杂度为O(mlogn)，专门拿出来学习一下。

dijkstra

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
#define INF  0x3f3f3f3f   //定义一个很大的数

struct Node{
int num,val;   //存放结点编号和到初始点的距离 
}nod;
 
priority_queue<Node> qq;  //优先从小到大
bool operator < (Node a,Node b){
if(a.val == b.val) return a.num>b.num;
return a.val>b.val;              //先出小 
} 
int book[100];  //检查这个点是否用过 
int dis[100];     //到原点最短距离 
int D[100][100];  //记录路径长度
int V,E; 
 
int main(){
int a,b,d;
while(cin>>V>>E && V&& E)  //输入顶点数和边数 
{
while(!qq.empty()) qq.pop(); //清空
memset(book,0,sizeof(book));
memset(D,-1,sizeof(D));  
for(int i=0;i<E;i++){
cin>>a>>b>>d;
D[a][b] = D[b][a] = d;
}
for(int i=2;i<=V;i++)
dis[i]=INF;
 
dis[1]=0;
nod.num=1;
nod.val=0;
qq.push(nod);   //将起点放入队列 
 
while(!qq.empty()){ //每次排序需要logn的时间
for(int i=2;i<=V;i++){//更新距离
if(D[qq.top().num][i] != -1  &&dis[i]>dis[qq.top().num] + D[qq.top().num][i]) 
{//qq.top()的点与i连通并且有了更短的路径，这个条件最多进来m次，因为每条边只会被用最多一次。
dis[i]=dis[qq.top().num] + D[qq.top().num][i];
nod.num=i; nod.val=dis[i];
qq.push(nod);
}} 
qq.pop();
}
 
for(int i=1;i<=V;i++){
cout<<"初始点到"<<i<<"点的距离为："<<dis[i]<<endl;
}}
return 0;
}

原文：https://blog.csdn.net/jobsandczj/article/details/49962557

prim

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
#include <bits/stdc++.h>
using namespace std;

const int N = 50 + 5, M = 5000 + 5;
int n, m;

struct Edge {
    int to, w;
    bool operator<(const Edge &other) const {
        return w > other.w;
    }
};

vector<Edge> v[N];
bool vis[N];

int Prime() {
    priority_queue<Edge> q;
    int cnt = 0, x, ans = 0;
    for (int i = 0; i < v[1].size(); ++i)q.push(v[1][i]);
    vis[1] = 1;
    while (cnt < n - 1) {
        Edge e = q.top();//排序每次需要logn的时间
        q.pop();
        x = e.to;
        if (!vis[x]) {//最多走m条边
            vis[x] = 1;
            ans += e.w, cnt++;
            for (int i = 0; i < v[x].size(); ++i)q.push(v[x][i]);
        }
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, w;
        cin >> x >> y >> w;
        v[x].push_back(Edge{y, w});
        v[y].push_back(Edge{x, w});
    }
    cout << Prime() << endl;
    return 0;
}

发表于

Translation

中国越来越重视公共图书馆,并鼓励人们充分加以利用。新近公布的统计数字表明,中国的公共图书馆数量在逐年增长。许多图书馆通过翻新和扩建,为读者创造了更为安静、舒适的环境。大型公共图书馆不仅提供种类繁多的参考资料,而且定期举办讲座、展览等活动。近年来,也出现了许多数字图书馆,从而节省了存放图书所需的空间。一些图书馆还推出了自助服务系统,使读者借书还书更加方便,进一步满足了读者的需求。

China is paying more and more attention to public libraries, and people are encouraged to make full use of them. The newly published statistics show that the number of public libraries in China is increasing year by year. Many libraries have created a quieter and more comfortable environment for readers through refurbishment and expansion. Large public libraries not only provide a wide variety of reference materials, but also regularly hold activities such as lectures, exhibitions and so on. In recent years, there have been many digital libraries which can save the space to store books. Some libraries have also introduced self-services systems, making it more convenient for readers to borrow and return books, which further meets the needs of readers.

notes

refurbishment [ˌriːˈfɜːrbɪʃmənt] n. 翻新;整修
The office looks so much better following its refurbishment.办公室翻新后看上去好多了。

发表于 更新于
名称 控制对象
RegDst 选择目的寄存器
RegWr 读或写寄存器
ExtOp 立即数扩展方式
ALUSrc ALU单元的输入
MemWr 读或写存储器
MemToReg 选择要写回的寄存器数据
ALUctr ALU单元的操作
Branch 是否分支指令
Jump 是否跳转指令
Zero 分支条件是否为真

ori 逻辑与 指令，其中一个操作数为立即数。

程序计数器PC：存放下一条将要执行的指令在内存中的地址。

堆栈指针寄存器sp：指向堆栈中的栈顶。（返回地址保存在此，return返回指令将保存在栈顶地址弹到PC中）

练习

第一章

假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50%，I/O速度不变，则运行基准程序A所耗费的时间是70秒。(注意提高50%，表示现在速度是原来的1.5倍)

冯诺依曼计算机根据指令周期的不同阶段区分从存储器中取出的是指令还是数据，在取指周期根据PC所指示的地址，取出的是指令；在执行周期根据指令中所指示的地址，取出的是数据。

概要

影响性能的因素：

  1. 算法（语句条数）
  2. 编程语言、编译器、体系结构（每条语句对应的指令条数）
  3. 处理器、存储系统（指令执行速度）
  4. I/O系统（I/O执行速度）

八个伟大思想：

  1. 面向摩尔定律的设计：预测设计完成时的工艺水平
  2. 使用抽象简化设计：高级语言、MIPS指令集
  3. 加速大概率事件：寻址附近的指令
  4. 通过并行提高性能
  5. 通过流水线提高性能
  6. 通过预测提高性能
  7. 存储器层次
  8. 通过冗余提高可靠性

计算机部件：输入、输出、存储器、数据通路（运算器）、控制器。后两者合称处理器。

性能：执行时间的倒数，提高性能的因素可从公式分析：

CPU Time=CPU Clock Cycles * Clock Cycle Time=CPU Clock Cycles / Clock Rate

Clock Cycles=Instruction Count * Cycles per Instruction

CPU Time=Instruction Count CPI Clock Cycle Time=Instruction Count * CPI / Clock Rate

MIPS=Instruction Count/(Execution time 10^6)=Clock rate/(CPI 10^6)

功率墙——多核微处理器，通过并行提高性能

指令

指令设计的四个基本原则

  1. 简单源于规整(算数运算的固定格式)
  2. 越小越快(MIPS仅有32个寄存器)
  3. 加速大概率事件(立即数、零号寄存器、PC相对寻址)
  4. 折中(没有“小/大于则跳转”的指令，只有小于置位，和(不)等则跳转，因为硬件难度；在指令中提供更大的地址与常数并且保持所有的指令具有相同的长度)

MIPS指令集

算术运算（两个源操作数一个地址）

0(\$zero)用于寄存器间数据移动 ）

存储器操作：

主存按字节寻址，按字对齐，找地址时，数组的下标要*4。MIPS大端对齐，数据高位在地址低位。load和store指令将低16位作为偏移地址，rs为基址。

立即数操作：

有符号数1000 0000 … 0000表示最小的负数$-2^{31}$，0000 0000 … 0000表示0；

逻辑操作：

rs未使用，被置为全0；与0异或，等同取反；

决策指令：

C代码：

1
while (save[i]==k)i+=1;

MIPS代码：

1
2
3
4
5
6
7
loop: sll $t1,$s3,2
	  add $t1,$t1,$s6
	  lw $t0,0($t1)
	  bne $0,$s5,exit
	  addi $s3,$s3,1
	  j loop
exit: ...

“基本块”

过程调用

6个步骤

寄存器分配

\$a0 – $a3: arguments (reg’s 4 – 7)

\$zero: (0)用于寄存器间数据移动

\$v0, $v1: result values (reg’s 2 and 3)

\$t0 – $t9: temporaries(reg’s 8 – 15，reg’s24 –25) Can be overwritten by callee

\$s0 – $s7: saved (reg’s 16 and 23) Must be saved/restored by callee

\$gp: global pointer for static data (reg 28)

\$sp: stack pointer (reg 29)

\$fp: frame pointer (reg 30)

\$ra: return address (reg 31)

例

叶程序：

1
2
3
4
5
6
int leaf(int g,int h,int i,int j)
{
    int f;
    f=(g+h)-(i+j);
    return f;
}

Arguments g, …, j in \$a0, …, $a3

f in \$s0 (hence, need to save $s0 on stack)

Result in $v0

1
2
3
4
5
6
7
8
9
10
leaf:
	addi $sp,$sp,-4
	sw $s0,0($sp)
	add $t0,$a0,$a1
	add $t1,$a2,$a3
	sub $s0,$t0,$t1
	add $v0,$s0,$zero
	lw $s0,0($sp)
	addi $sp,$sp,4
	jr $ra

非叶程序：

1
2
3
4
5
int fact (int n)
{
    if (n < 1) return 1;
    else return n * fact(n - 1);
}

Argument n in $a0

Result in $v0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fact: addi $sp,$sp,-8
	  sw $ra,4($sp)
	  sw $a0,0($sp)
	  slti $t0,$a0,1
	  beq $t0,$zero,L1
	  addi $v0,$zero,1
	  addi $sp,$sp,8
	  jr $ra
L1:   addi $a0,$a0,-1
	  jal fact
	  lw $a0,0($sp)
	  lw $ra,4($sp)
	  addi $sp,$sp,8
	  mul $v0,$v0,$a0
	  jr $ra

字符串复制

1
2
3
4
5
6
7
void strcpy(char x[],char y[])
{
    int i;
    i=0;
    while((x[i]=y[i])!='\0')
        i+=1;
}

Addresses of x, y in \$a0, $a1

i in $s0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
strcpy:
	addi $sp,$sp,-4
	sw $s0,0($sp)
	add $s0,$zero,$zero
L1: add $t1,$s0,$a1
	lbu $t1,0($t1)
	add $t3,$s0,$a0
	sb $t2,0(t3)
	beq $t2,$zero,L2
	addi $s0,$s0,1
	j L1
L2: lw $s0,0($sp)
	addi $sp,$sp,4
	jr $ra

分支和跳转中的寻址

PC相对寻址：因为MIPS指令都是4字节长，所以抛出相对寻址时所加的地址被设计为字地址而不是字节地址，跳转范围扩大4倍。

直接跳转：PC高四位不变

动态链接库(DLL)的晚过程链接：在随后的调用中，查找例程、重映射例程、链接例程被跳过

即时编译器JIT：选择性的将一些方法编译成宿主机上的本地机器语言

在字节寻址的机器中，连续的字地址相差4；

Instruction class MIPS examples
Arithmetic add, sub, addi
Data transfer lw, sw, lb, lbu, lh, lhu, sb, lui
Logical and, or, nor, andi, ori, sll, srl
Cond. Branch beq, bne, slt, slti, sltiu
Jump j, jr, jal

计算机的算术运算

乘法

高位HI，低位LO

Instructions

mult rs, rt / multu rs, rt 64-bit product in HI/LO

mfhi rd / mflo rd Move from HI/LO to rd，Can test HI value to see if product overflows 32 bits

mul rd, rs, rt Least-significant 32 bits of product –> rd

除法

浮点运算

数值表示

尾数精度=尾数位数+1

单精度规格化数：阶码取值范围在1~254之间；尾数可以取任何值。

对于float型，特殊的值：

符号位 阶码/指数 尾数 数值
+/- 全0 全0 0
+/- 全1(=255) 全0 +无穷/-无穷
+/- 全0 非0 非规格化数
+/- 全1(=255) 非0 非数NaN

移码

范围

精度：float（$2^{-23}$）

例

表示-0.75：

float: 1 01111110 100 … 00

double: 1 01111111110 1000…00

高级语言中可以定义多种数据类型，因此需要存取不同长度操作数的数据传输指令。

浮点数加法

对阶的时候，需要小阶向大阶看齐，因为大阶如果向小阶看齐，那么就要左移，不符号规格化的要求。

浮点数乘法

浮点数乘法运算结果规格化：不需要左移，最多需要一次右移；除法：不需要右移，最多需要一次左移。正常的运算过程下，若尾数为0，则结果的阶码也置为0.

浮点加法不满足结合律

子字并行

Matrix Multiply

未优化：

1
2
3
4
5
6
7
8
9
10
11
void dgemm (int n, double* A, double* B, double* C)
 {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
    {
     double cij = C[i+j*n]; /* cij = C[i][j] */
     for(int k = 0; k < n; k++ )
      cij += A[i+k*n] * B[k+j*n]; /* cij += A[i][k]*B[k][j] */
      C[i+j*n] = cij; /* C[i][j] = cij */
   }
}

优化后：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <x86intrin.h>
void dgemm (int n, double* A, double* B, double* C)
{
	for ( int i = 0; i < n; i+=4 )
    for ( int j = 0; j < n; j++ ) {
    	__m256d c0 = _mm256_load_pd(C+i+j*n); /* c0 = C[i][j] */
    for( int k = 0; k < n; k++ )
    	c0 = _mm256_add_pd(c0, /* c0 += A[i][k]*B[k][j] */
              _mm256_mul_pd(_mm256_load_pd(A+i+k*n),
             _mm256_broadcast_sd(B+k+j*n)));
    	_mm256_store_pd(C+i+j*n, c0); /* C[i][j] = c0 */
    }
}

发表于 更新于

ER-Model

Relationships

实体——矩形，属性——椭圆，二者直线相连；

关系ralationship——菱形，连接多个实体；

Relations——两个集合的笛卡尔积的子集；

关系多对多、多对一、一对一；圆箭头表示有且仅有一个，尖箭头表示至多一个；

关系的属性可以转化为一个与关系相连的新实体的属性

如果在一个关系中两次用到同一个实体：

多路关系转二路

Subclasses子类~isa：一对一关系，三角形的顶点与父类(superclass)相连，底边与子类相连。(与powerdesigner正好相反)

主键：每个实体至少有一个属性集合作为键。isa情况下，只有根实体有键，且作为所有子类的键。选择一个键作为主键。

弱实体集合：弱实体集合用双边矩形。与其他实体有一个或多个 多对一的关系，关系用双边菱形，但并不是与它相连的关系都是supporting relationship。它的键等于自身下划线属性加上supporting entity sets的键。

成为实体应满足以下两个条件之一：1、有一个不属于键的属性；2、是多对一或多对多关系的“多”端。

练习

Question 1: If entity set A currently has 100 entities, which of the following could be the number of B entities?

​ Ⅰ. 1

​ Ⅱ. 100

​ Ⅲ. 200

(a) Ⅰor Ⅱ (b) Ⅱ or Ⅲ (c) Ⅱ only (d)Ⅰ,Ⅱor Ⅲ

一个百货公司有若干连锁店，每家连锁店经营若干商品，同一种商品可以在任何一家连锁店中销售；每家连锁店有若干职工，但每个职工只能服务于一家商店。现该百货公司准备建一个计算机管理系统，请你帮助它设计一个数据库模式，基于该数据库模式百货公司经理可以掌握职工信息、连锁店信息和商品销售信息。已知基本信息有：

连锁店：连锁店名、地址、经理职工号；

职工：职工号、职工名、年龄、性别；

商品：商品号、商品名、价格、生产厂家；

Relational Data Model

实体完整性（主属性(主键中的属性)不能为空）、参照完整性（外键）和用户定义的完整性

Schema 模式：

关系的模式：关系名+属性名，每个属性可加上数值类型

Product(Name, Price, Category, Manufacturer)

Product(Name:string, Price:real, Category:string, Manufacturer:string)

数据库的模式：关系模式的集合

Instance 实例：（注意值与属性位置相对应）

ER图转关系图

实体—>关系表；关系—>关系表

特殊情形

关系表合并：多对一关系，将关系与多端合并；多对多关系不能合并。

弱实体集合：它的表中要有完整的键（可能来自其他实体的属性），支持关系不需要表。

子类：Product有两个子类EducationalProduct、SoftwareProduct

1、OO，面向对象：4张表

Product(name, price, category, manufacturer)

EducationalProduct( name, price, category, manufacturer, ageGroup, topic)

SoftwareProduct( name, price, category, manufacturer,platforms, requiredMemory)

EducationalSoftwareProduct( name, price, category, manufacturer, ageGroup, topic, platforms, requiredMemory)

2、E/R方法：3张表

Product(name, price, category, manufacturer)

EducationalProduct( name, ageGroup, topic)

SoftwareProduct( name, platforms, requiredMemory)

3、空值方法：1张表

Product ( name, price, category, manufacturer, age-group, topic, platforms, required-memory)

练习

Question2: If we convert the E/R diagram to relations in the standard way, which set of attributes would not appear in the schema of some relation?（图同Q1）

​ (a) (b,c,e) (b) (a,b) (c) (a,d) (d) (c,f)

注意A不是一个弱实体集合！它的关系表中只有a,d

发表于 更新于

图

定义：“路径”，“简单”，“连通”，“圈(k>2)”，“树(连通且无圈)”

图的连通性与图的遍历

广度优先(Breadth-First Search) —队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BFS(s): 
置Discovered[s]=true, 其他v, 置Discovered[v]=false 
初始化L[0], 单个元素s构成 
置层计数器i=0 
置BFS树T=空集
While L[i]非空
	初始化一个空表L[i+1]
	For 每个结点L[i]中结点u 
	考虑每条关联到u的边(u,v) 
    If Discovered[v]=false then 
    	置Discoverd[v]=true 
        把边(u,v)加到树T上 
        把v加到表L[i+1]
    Endif 
  Endfor 
 层计数器加1 
Endwhile

如果图是邻接表给出，BFS将以O(m+n)时间运行

DFS—栈

1
2
3
4
5
6
7
8
9
10
11
DFS(s) 
初始化S为具有一个元素s的栈 
While S 非空
	从S中取出一个节点u 
	If Explored[u]=false then 
		置Explored[u]=true 
    	For每条与u关联的边(u,v) 
    		把v加到栈S 
    	Endfor 
    EndIf 
EndWhile

对无向图中任两个结点s与t,它 们的连通分支或者相等，或者不相交。
对有向图中的任何两个结点s与 t,它们的强连通分支或者相等，或者不相交。

强连通：图中每对结点相互可达

二分性测试

如果一个图是二部图，那么它不可能包含一个奇圈。没有边与同一层的两个结点相交。

BFS—存在 O(m + n) 的有效算法判别图G是 否强连通。

DAG(DirectedAcyclicGraphs)有向无圈图~拓扑排序

在O(m + n) 时间内找到一个拓扑排序—考虑边逐次递减的代价O(m); 追踪被删除 的结点代价O(n).（邻接表+零入度节点的栈）

贪心算法

证明贪心算法对一个问题能够提供一个优解：贪心算法领先、交换论证

区间调度

失败的尝试：开始时间、区间的宽度、最少“冲突”。

贪心算法：把任务(需求)按照结束时间递增排序。依次选取与前面已选定任务相容的新任务。O(nlogn)

用贪心算法领先的思路，说明以“最小结束时间”为贪心策略的最优性（归纳法）。

推广：在线算法、加权的区间调度

区间划分

在任何区间划分的实例中，资源数必须至少是区间集合的深度。一个区间集合的深度是通过时间线上任何一点的最大区间数。

贪心算法：需求按照开始时间排序，把需求安排到不冲突的资源中。对于每一个教室k, 记录下后一个需求的结束时间；把教室放在一个优先队列中(按照结束时间 先后)。 O(nlogn)

最小延迟调度

失败的尝试：任务长度、松弛时间（最晚开始时间）

贪心算法：按照结束时间增长的次序排序(最早截止时间优先)，用交换论证的方法证明最优性。

推广：增加释放时间（最早开始时间）

最优超高速缓存

“最远将来规则”（Farthest-in-future） When di需要被放入超高速缓存，收回在最远的将来被需要的那个项。

推广：最近最少使用原则（LRU)。把时间方向倒过来：过去的久而不是将来的远，恰好是Belady算法，因为实际必须在不知道将来需求的情况下匆忙做出收回的决定。

图的最短路径

Dijkstra算法

1
2
3
4
5
6
7
8
9
Dijkstra算法(G,l) 
设S是被探查的结点集合 
	对每个S中的u,存储一个d(u); 
初始S={s}且d(s)=0 
While S!=V 
	选择一个结点不在S中的结点v,使得从S到v至少有一条边连接并且	      		
	d'(v)=min_{e=(u,v), u in S}d(u)+le 最小 
    将v加入S并且定义d(v)=d'(v) 
Endwhile

使用优先队列与邻接链表使整个时间复杂度优化到 O( (M+N)logN )

  • d[]是最小堆，所以每次取出最小值只需$O(1)$的时间，并花费$O(logn)$的时间重新调整成最小堆；
  • 需要n-1次操作才可以找出剩下的n-1个点，在这期间，需要访问m次边，每次访问都可能造成d[]的改变。

最小生成树

Kruskal算法

将边按照费用递增次序排列，只要不构成圈，把边e插入树中。采用union-find数据结构，生成一个小生成树T，保持每一个连通分支的集合。算法代价：O(mlog n).

1
2
3
4
5
6
7
8
9
10
//在一个具有n 个顶点的网络中找到一棵最小生成树
令T为所选边的集合，初始化T=Φ
令E为网络中边的集合
while (E≠Φ) && (|T|≠n-1) {
令(u,v)为E中代价最小的边
E=E-{ (u,v) } / /从E中删除边
if ((u,v)加入T中不会产生环路) 将(u,v)加入T
}
i f (|T| == n-1) T是最小耗费生成树
else 网络不是连通的，不能找到生成树

反向删除算法

依照费用递减的次序开始删除边，只要不破坏当前图的连通性。

Prim算法

初始S={s}，然后贪心增长树T. 每步选择一端在T中， 费用小的边与T连接。复杂度估计：用矩阵，O(n^2)； 采用优先队列 （堆），O(mlogn)

1
2
3
4
5
6
7
8
9
10
11
12
//假设网络中至少具有一个顶点
设T为所选择的边的集合，初始化T=Φ
设TV为已在树中的顶点的集合，置TV={1}
令E为网络中边的集合
while (E<>Φ) && (|T|<>n-1) {
	令(u,v)为最小代价边，其中u∈TV,v∈TV
	if (没有这种边) break
	E=E-{(u,v)}//从E中删除此边
	在T中加入边(u,v)
}
if (|T|==n-1) T是一棵最小生成树
else 网络是不连通的，没有最小生成树

一个圈和一个割有偶数条相交边。

推广

存在相同费用的边、关心点到点的距离 、每条边运输不超过确定的交通量、删除一条边后仍保持畅通

聚类

运行Kruskal算法，但是就在它加最后的k-1条边之前停止。等价于取整棵最小生成树T,然后删除k-1 条最贵的边。

Huffman码与数据压缩

证明：归纳步骤中用反证法。假设贪心算法产生的树T不是最优的，存在树Z, 使得ABL(Z)<ABL(T),根据前面的命题，存在这样一棵树Z,其中y*与z*(频率最低的两个字母)是兄弟。类似的，我们可以得到Z’, 满足：ABL(Z’)=ABL(Z) - fw. 于是就得到：ABL(Z’)<ABL(T’)，与作为S’前缀码的T’最优性相矛盾。

基本是到此结束的，但是上机考试的经历实在不忍回首，真是对不起葡萄。要在这里好好学下huffman的代码了。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// huffman.h
#pragma once
#include<iostream>
#include<list>
#include <algorithm>
#include<string>
using namespace std;
int T = 0;
class binaryTree
{
public:
	binaryTree* right;
	binaryTree* left;
	int weight;//权重
	char key;//字母
	binaryTree(int theWeight=0,char theKey=0,binaryTree* theLeft=NULL, binaryTree* theRight = NULL)
	{ weight = theWeight; right = theRight; left = theLeft; key = theKey; }
	void makeTree(binaryTree, binaryTree);
};
void binaryTree::makeTree(binaryTree theLeft, binaryTree theRight)
{
	binaryTree* ltree = new binaryTree(theLeft.weight, theLeft.key, theLeft.right, theLeft.left);
	binaryTree* rtree = new binaryTree(theRight.weight, theRight.key, theRight.right, theRight.left);
	left = ltree;
	right = rtree;
}
struct hpair
{//权重-字母-编码
	int weight;
	char key;
	string huffString = "";
};
hpair* p = NULL;//申明自定义的类的对象时，要写在类定义之后！！
bool compare(binaryTree* a,binaryTree* b)
{
	return a->weight<b->weight; //升序排列
}

binaryTree* myTree = NULL;
void huffmanTree(hpair* code, int n)
{
	list<binaryTree*> tlist;
	binaryTree *hNode = new binaryTree[n];
	//创建n个叶节点
	for (int i = 0; i < n; i++)
	{
		hNode[i] = binaryTree(code[i].weight, code[i].key, NULL, NULL);
		hNode[i].key = code[i].key;
		tlist.push_back(&hNode[i]);
	}
	//每次取权最小的两个节点，构成新的节点
	while (tlist.size()>1)
	{
		tlist.sort(compare);
		binaryTree *theR,*theL;
		theR = tlist.front();
		tlist.pop_front();
		theL = tlist.front();
		tlist.pop_front();
		binaryTree* tree =new binaryTree(theR->weight + theL->weight, ' ', theL, theR);
		tlist.push_back(tree);
	}
	binaryTree* tmp = tlist.front();
	myTree = new binaryTree(tmp->weight, tmp->key, tmp->left, tmp->right);
}
void huffCode(binaryTree* tree, string s)
{
	if ((tree->left) == NULL || (tree->right) == NULL)
	{//递归得到叶节点
		cout << tree->key << "-----" << s << endl;
		for (int i = 0; i < T; i++)
		{
			if (p[i].key == tree->key)
				p[i].huffString = s;
		}
	}
	else
	{//向左附加0，向右附加1，递归
		huffCode(tree->left, s + "0");
		huffCode(tree->right, s + "1");
	}
}
hpair* createPair(string s)
{//根据传入的字符串确定出现的符号和频率
	int num[26];
	for (int i = 0; i < 26; i++)
		num[i] = 0;
	int len = s.length();
	for (int i = 0;i < len; i++)	
		num[s[i] - 'a']++;//出现次数
	int total = 0;//字母种数
	for(int i=0;i<26;i++)
		if (num[i])
		{
			total++;
		}
	T = total;
	int j = 0;
	p = new hpair[total];
	for (int i = 0; i < 26; i++)
	{
		if (num[i])
		{
			p[j].key = 'a' + i;
			p[j++].weight = num[i];
		}
	}
	return p;
}
string encode(string a)
{//用已有的哈夫曼树得出的字母编码，将字符串转为01串
	string ret = "";
	int len = a.length();
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < T; j++)
		{
			if (p[j].key == a[i])
				ret += p[j].huffString;
		}
	}
	return ret;
}

string trans(string num)
{//将01串转为原文
	string tr = "";
	char temp;
	binaryTree* tt;
	int len = num.length();
	for (int i = 0; i < len; )
	{
		tt = myTree;
		while (tt->left != NULL)
		{//读到0向左读到1向右
			temp = num[i++];
			if (temp == '0')
				tt = tt->left;
			else
				tt = tt->right;
		}
		//到达叶节点，附加字母
		tr += tt->key;
	}
	return tr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// main.cpp
#include"huffman.h"
#include<vector>
#include<string>
#include<iostream>
using namespace std;
void main()
{
	string s = "iisssksssskkttteonoks";
	cout << s << endl;
	hpair* hp = NULL;
	hp= createPair(s);
	huffmanTree(hp, T);
	huffCode(myTree, "");
	cout << '\n' << "--------------After encode--------------" << endl;
	string ret=encode(s);
	cout << ret << endl;
	cout << '\n' << "--------------Translation--------------" << endl;
	string tr = trans(ret);
	cout << tr << endl;
	system("pause");
}

发表于

稳定匹配（邀请-拒绝算法 [Gale-Shapley 1962] ）

一个匹配S是稳定的，如果匹配S是完美的且不存在相对于S的不稳定因素。

算法

初始，每个人都是自由的。一个自由的男人m选择他的优先表上排名高的女人w,发起邀请，那么(m,w)进入中间状态： 约会 。

如果又有另一个男人m’发起邀请，那么女人w决定,选择m,还是m’. 如果m优先， 那么约会状态不变。否则(m’,w)变成约会状态，m变成自由状态。

循环往复；当没有人处于自由状态，那么所有的约会被定为后的结果， 返回终的完美匹配

1
2
3
4
5
6
7
8
9
Initialize each person to be free. 
while(some man is free and hasn't proposed to every woman) { 		Choose such a man m 
    w = 1st woman on m's list to whom m has not yet proposed 
    if (w is free) 
          assign m and w to be engaged 
    else if (w prefers m to m') 
             assign m and w to be engaged, and m' to be free 		else 
             w rejects m 
}

至多n^2次While循环的迭代后终止。G-S算法的每次执行都得到男士对应的最佳有效伴侣集合。每个女士与她最差的有效伴侣配对。

trick：女士对自己的优先表做反向变换； 
1
2
for i = 1 to n 
	inverse[pref[i]] = i

五类典型问题

Interval scheduling: n log n greedy algorithm.

Weighted interval scheduling: n log n dynamic programming algorithm.

Bipartite matching: nkmax-flow based algorithm.

Independent set: NP-complete.

Competitive facility location: PSPACEcomplete.

算法分析

亚线性时间(O(logn))-线性时间O(n)-O(nlogn)阶时间-平方时间-立方时间-O(n^k)时间-指数时间(Exponential time)-n!时间

我对不起葡萄

发表于 更新于

太湖是中国东部的一个淡水湖,占地面积2250平方公里,是中国第三大淡水湖,仅次于鄱阳和洞庭。太湖约有90个岛屿,大小从几平方米到几平方公里不等。太湖以其独特的“太湖石”而闻名,太湖石常用于装饰中国传统园林。太湖也以高产的捕鱼业闻名。自上世纪70年代后期以来,捕捞鱼蟹对沿湖的居民来说极为重要,并对周边地区的经济作出了重大贡献。太湖地区是中国陶瓷( ceramics)业基地之一,其中宜兴的陶瓷厂家生产举世闻名的宜兴紫砂壶( clay teapot)。

Taihu Lake, a freshwater lake in eastern China, with an area of 2250 square kilometers, is the third largest freshwater lake in China, second to Poyang and Dongting Lake. Taihu Lake encompasses about 90 islands, ranging in size from several square meters to several square kilometers. Taihu Lake is famous for its unique “Taihu Stone”, which is often used to decorate traditional Chinese gardens. Taihu Lake is also well-known for its high-yield fishing industry. Fishing for fish and crabs since the late 1970s has been of great importance to inhabitants there and made great contribution to the economy of the surrounding areas. Taihu Lake region is also a base for China’s ceramic industry, where manufacturers in Yixing produce the world-famous Yixing clay teapot.

Notes

a freshwater lake 淡水湖

encompass [ɪnˈkʌmpəs] v.包含，涉及;包围;

ranging in size from … to …

high-yield fishing industry 高产的捕鱼业

ceramic [səˈræmɪk] n. 陶瓷器 adj. 陶器的

garden 园林

inhabitant [ɪnˈhæbɪtənt] n. (某地的)居民，栖息动物

Here‘s mud in your eye! 祝你幸福！