0%

学习链接

案例:中国旅游网有道翻译

快捷键【Ctrl+U】打开源码页面

合法性:如果网站有 robots.txt 文档,要判断是否有禁止访客获取的数据。

准备工作:在 PyCharm 中安装 requests 库

基本原理:网页请求分为request和response两个环节,request分get和post两种方式,写爬虫前要先确定向谁发送请求,用什么方式发送。

开始爬虫

所有在源码中的数据请求方式都是GET

1
2
3
4
import requests        #导入requests包
url = 'http://www.cntour.cn/'
strhtml = requests.get(url) #Get方式获取网页数据
print(strhtml.text)

用 GET 方式获取数据需要调用 requests 库中的 get 方法:requests.get(url),这个方法获得一个url对象,代表整个网页,如果只需网页中的源码,使用.text

在开发者模式中,依次单击“Network”按钮和“XHR”按钮,找到翻译数据,将 Headers 中的 URL 复制出来,并赋值给 url。POST 请求数据必须构建请求头。复制From Data中的请求参数并构建一个新字典。使用 requests.post 方法请求表单数据。将字符串格式的数据转换成 JSON 格式数据,并根据数据结构,提取数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import requests        #导入requests包
import json
def get_translate_date(word=None):
url = 'http://fanyi.youdao.com/translate?smartresult=dict&smartresult=rule'
From_data={'i':word,'from':'zh-CHS','to':'en','smartresult':'dict','client':'fanyideskweb','salt':'15477056211258','sign':'b3589f32c38bc9e3876a570b8a992604','ts':'1547705621125','bv':'b33a2f3f9d09bde064c9275bcb33d94e','doctype':'json','version':'2.1','keyfrom':'fanyi.web','action':'FY_BY_REALTIME','typoResult':'false'}
#请求表单数据
response = requests.post(url,data=From_data)
#将Json格式字符串转字典
content = json.loads(response.text)
print(content)
#打印翻译后的数据
#print(content['translateResult'][0][0]['tgt'])
if __name__=='__main__':
get_translate_date('我爱中国')

POST请求有道翻译{“errorcode:50}——把URL中把_o去掉

json模块主要有四个比较重要的函数,分别是:

  • dump - 将Python对象按照JSON格式序列化到文件中
  • dumps - 将Python对象处理成JSON格式的字符串
  • load - 将文件中的JSON数据反序列化成对象
  • loads - 将字符串的内容反序列化成Python对象

Beautiful Soup 解析网页

安装 bs4 库,安装 lxml 库

1
2
3
4
5
6
7
import requests        #导入requests包
from bs4 import BeautifulSoup
url='http://www.cntour.cn/'
strhtml=requests.get(url)
soup=BeautifulSoup(strhtml.text,'lxml')
data = soup.select('#main>div>div.mtop.firstMod.clearfix>div.centerBox>ul.newsList>li>a')
print(data)

首先,HTML 文档将被转换成 Unicode 编码格式,然后 Beautiful Soup 选择最合适的解析器来解析这段文档,此处指定 lxml 解析器进行解析。解析后便将复杂的 HTML 文档转换成树形结构,并且每个节点都是 Python 对象。将解析后的文档存储到新建的变量 soup 中。用 select(选择器)定位数据,方法:开发者模式,将鼠标光标停留在对应的数据位置并右击,“Copy”➔“Copy Selector”,使用 soup.select 引用这个路径。

清洗和组织数据

1
2
3
4
5
6
for item in data:
result={
'title':item.get_text(),
'link':item.get('href')
}
print(result)

标题在<a>标签中,提取标签的正文用 get_text() 方法。链接在<a>标签的 href 属性中,提取标签中的 href 属性用 get() 方法,在括号中指定要提取的属性数据,即 get('href'),用正则表达式提取 ID (re库中)

1
2
3
4
5
6
7
8
import re
for item in data:
result={
"title":item.get_text(),
"link":item.get('href'),
'ID':re.findall('\d+',item.get('href'))
}
print(result)

\d匹配数字,+匹配前一个字符1次或多次。 re 库的 findall 方法,第一个参数表示正则表达式,第二个参数表示要提取的文本

re.compile(r’^/question’)是正则表达式 匹配 ‘/question’开头

应对反爬虫

在 Request headers 中构造浏览器的请求头,封装自己。服务器识别浏览器访问的方法就是判断 keyword 是否为 Request headers 下的 User-Agent

………………


关于json编码:

1
2
3
4
5
import json
obj = {"name": "测试"}
json.dumps(obj)
print(json.dumps(obj))
print(json.dumps(obj, ensure_ascii=False))

输出结果:

1
2
{"name": "\u6d4b\u8bd5"}
{"name": "测试"}

背景

logistic回归的问题:1、过拟合或欠拟合;2、消耗大量资源

神经重接实验——存在学习算法可以同时处理视觉、听觉和触觉,而不需要运行上千个不同的程序或算法

结构

输入层、输出层、隐藏层,偏置单元 值为1

由输入层计算出输出:向前传播,有效解决非线性假设函数

神经网络就相当于通过初始特征学习到新的特征, 再通过新的特征进行logistic回归得到输出结果

逻辑运算

通过改变参数进行逻辑与、或、非运算,将这三个神经单元组成一个神经网络可得到同或运算

代价函数

反向传播算法

求出”梯度”即偏导项

展开参数

问题描述

Example 1:

1
2
Input: "42"
Output: 42

Example 2:

1
2
3
4
Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.

Example 3:

1
2
3
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

1
2
3
4
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

1
2
3
4
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.

解决方案

主要就是要考虑的细节比较多,特殊的情况及其处理在注释中给出

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
int myAtoi(string str)
{
int len = str.length();
int s = 0;
long long res = 0;
int numLen = 0;
bool minus = false;
bool hasNum = false;
while (s < len && ((str[s] == ' ' && !hasNum) || str[s] == '0'))
{
//第二个条件针对"0 123"
if (str[s] == '0')hasNum = true;
++s;
}
if (!hasNum)
{//hasNum的判断针对"0-1"
//if-else语句针对"-+1","-+1","+1"
if (str[s] == '-') { ++s; minus = true; }
else if (str[s] == '+') { ++s; }
}
while (s < len && (str[s] == '0'))++s;//针对" +0 123","-000000000000001"," 0000000000012345678"
if (str[s]<'0' || str[s]>'9')return 0;
while (s < len&&str[s] >= '0' && str[s] <= '9'&&numLen<11)
{//INT_MAX是10位数,numLen针对"20000000000000000000"
res *= 10;
res += (str[s] - '0');
++s; ++numLen;
}
if (minus)res *= (-1);
if (res > INT_MAX)return INT_MAX;
if (res < INT_MIN) return INT_MIN;
return res;
}

另外看到一个解决方法,在处理数字串前面的空白、0、正负号时更简洁:

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
class Solution {
public:
int myAtoi(string str) {
bool neg = false, caled = false;
int res = 0;
int tmp;
for(string::iterator it=str.begin(); it!=str.end(); ++it) {
if ( *it == ' ' && !caled) continue;
if ( *it == '-' && !caled) { neg = true; caled = true; continue; }
if ( *it == '+' && !caled) { neg = false; caled = true; continue; }
if ( *it >= '0' && *it <= '9') {
tmp = *it - '0';
caled = true;
if ( res > 0 && !neg &&
(( res > INT_MAX / 10) || ((INT_MAX - res*10) < tmp)) ) {
res = INT_MAX;
return res;}
if (res > 0 && neg &&
(( -1 * res < INT_MIN / 10) || (res*-10 <= INT_MIN + tmp)) ) {
res = INT_MIN;
return res;}
res = res*10 + tmp;
continue;
}
break;
}
if (caled) res = neg ? -1 * res : res;
return res;
}
};

题目描述

Given a 32-bit signed integer, reverse digits of an integer. Returns 0 when the reversed integer overflows.

Example 1:

1
2
Input: 123
Output: 321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21

解决方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int reverse(int a)
{
long long b = 0;
long long tmp = a;
if (a<0)
tmp *= (-1);
int mod = 10;
int k = 0;
while (tmp > 0)
{
k = tmp % (mod);
tmp /= mod;
b *= 10;
b += k;
}
b=(a > 0) ? b : (-1)*b;
if (b > INT_MAX || b < INT_MIN)
return 0;
return b;
}

主要需要注意的地方是int和long long数据类型的区别。使用INT_MAX和INT_MIN可以表示int类型的最值。

unsigned int 0~4294967295
int -2147483648~2147483647 [$−2^{31}, 2^{31} − 1​$]
unsigned long 0~4294967295
long -2147483648~2147483647
long long的最大值:9223372036854775807
long long的最小值:-9223372036854775808
unsigned long long的最大值:1844674407370955161

题目描述

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3
P   A   H   N
A P L S I I G
Y I R

And then read line by line: "PAHNAPLSIIGYIR"

解决方案

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
#include<bits/stdc++.h>
using namespace std;
/*
思路:找出每一行的字母位置的规律,具体做法是将所有的字母分组,每一组是一个'v'字形,
每一组中,除了最上面一行和最下面一行,都会有两个间隔规律的字母处于同一行中
*/
string zigzag(string s, int numRows)
{
if (numRows == 1)
return s;
string* r=new string[numRows];
for (int i = 0; i < numRows; ++i)
{
r[i] = "";
}
int groupSize = 2 * numRows - 2;//组的大小
int size = s.length();
for (int i = 0; i < numRows; ++i)
{
int j = i;
while (j < size)
{
//若没有在最开始讨论“只有一行”的情况,这里会进入死循环
r[i] += s[j];
int k = 2 * (numRows - i - 1) ;//每一组中处于同一行的字母的间隔
if (k > 0 &&(i)&& ((j + k) < size))
//不是最上面一行和最下面一行,并且小于总字符串长度
r[i] += s[j + k];
j += groupSize;//查找每个组
}
}
string res = "";
for (int i = 0; i < numRows; ++i)
{
res += r[i];
}
return res;
}
int main()
{
string s1 = "PAYPALISHIRING";
int num1 = 3;
cout << zigzag("AB", 2) << "\n";
system("pause");
return 0;
}

学习一个更精简的解决方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
string convert(string s, int numRows) {

if (numRows == 1) return s;

vector<string> rows(min(numRows, int(s.size())));
int curRow = 0;
bool goingDown = false;

for (char c : s) {
rows[curRow] += c;
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}

string ret;
for (string row : rows) ret += row;
return ret;
}
};

复杂度比最上面的做法低,依次遍历总的字符串,比较巧的地方是改变子字符串的行号,用goingDown表示此时向上(+1)还是向下(-1)走,若是此时curRow是最上面一行或最下面一行,则变换方向,即goingDown取反。

淘聘网

王炜

课程目标:一个数据平台

  1. python编程 爬取数据
  2. 模拟Oracle BI 软件,系统原型搭建,建模

课程考核:

提供数据或自己收集,做分析。

数据分析:

  1. BIEE——oracle企业版
  2. 最基本的方式:Excel
  3. Python

IOE(IBM的小型机、Oracle数据库、EMC存储设备)

BATJ(百度、阿里巴巴、腾讯、京东)

FLAG(Facebook,LinkedIn,Amazon,Google)

建模:物理,逻辑,应用

实训报告:实训目的、实训内容、调试程序的步骤、实验过程总结、总结


练习unix和linux环境

IAAS,PAAS(platform),SAAS

信息系统架构的演变:数据服务器,应用服务器,Web服务器,客户端

BI系统,ERP系统,CRM管理系统

数据化:OLTP(处理)与OLAP(分析)

大数据4v:数据量,速度,多样性,价值

中间件 商务智能应用

看文档和教程Tutorial 建模:11g Admininstraion 第一行

数据展现分析和仪表盘(new)第二条

数据孤岛 oracle主页

产品-业务分析

305 PDF


通常服务器使用 LAMP(Linux + Apache + MySQL + PHP)或 LNMP(Linux + Nginx+ MySQL + PHP)组合

冯诺依曼计算机工作方式的基本特点:按地址访问并顺序执行指令

指令寄存器(Instruction Register,IR)用来保存当前正在执行的一条指令。程序计数器(Program Counter,PC)用来指出下一条指令在主存储器中的地址。

[例题]一个四路组相联的cache共有64块,主存共有8192块,每块32字,则主存地址中字块标记,组地址,块内地址的位数分别是:9,4,5

从题中可看出:
每块32字所以块内地址为5位,2的5次方等于32,.
64/4=16组,2的4次方等于16,所以组地址为4位,(如果是直接相连的话,那么就是2的6次方等于64,块地址就为6位了,但是这里是4路组相连,所以是组地址,而不是块地址)
然后主存一共有8192*32个字,取LOG,也就是18位,
所以字块标记为18-5-4=9位.
主存字块标记 组地址 块内地址
9位 4位 5位 不要总认为地址就是32位呀!!!

浮点乘法判溢出的时刻是:阶码求和之后尾数相乘并规格化之后

RISC有乘除指令和浮点运算指令。RISC的主要目的是减少指令数。

在微程序处理器中,N种微操作,控制字段要设置的位数是$log_2N向上取整+1$ 考虑N=1的情况

在规格化数表示中,保持其他方面不变,将阶码部分的移码改为补码表示,则数的表示范围不变。

认真读题——“每次取一个字节PC自动加1”,“两个字节”

寄存器间接寻址方式:寄存器内存放的是操作数的地址,而不是操作数本身,即操作数是通过寄存器间接得到的。操作数处于内存单元中。

寄存器相对寻址方式:操作数在存储器中,其有效地址是一个基址寄存器(BX、BP)或变址寄存器(SI、DI)的内容和指令中的8位/16位偏移量之和。

为提高存储器存取效率,通常将同一文件存放在不同面的同一磁道上。

正数的反码等于其原,而负数的反码则可以通过保留其符号位,将原的数值得到。

硬件向量法, 就是通过向量地址来寻找设备的中断服务程序入口地址,而且向量地址是由硬件电路产生的。

题目3.47 下面C代码实现了一个4阶FIR滤波器,输入为数组 sig_in 。设所有数组元素为16位定点数。假设你要面向 一个具有SIMD指令集且有128位寄存器的处理器,用汇编语言优化该代码。在不知指令细节的情况下,简要介绍一 下如何实现该代码,最大限度用字并行操作,并使寄存器和存储器间数据传送量最少。

1
for (i=3;i<128;i++)    sig_out[i] = sig_in[i-3]*f[0]+sig_in[i-2]*f[1]+sig_in[i-1]*f[2]+sig_in[i]*f[3]

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
F=[f[3],f[2],f[1],f[0],f[3],f[2],f[1],f[0]]
B=[sig_in[7],sig_in[6],...,sig_in[0]]
for(i=0;i<16;i++)
A=[sig_in[i*8+7],...,sig_in[i*8+0]]
if i>0
// 为了保证i=0时不会数组下界溢出
B=[sig_in(i-1)*8+7,...,sig_in[(i-1)*8+0]]
for(j=0;j<4;j++)
C=A*F
sig_out[i*8+j+4],sig_out[i*8+j]=C[127:64],C[63:0]
A=A<<16*1bit
E=B>>16*7bit
A=A OR E
B=B<<16*1bit// 为A提供持续最右侧sig_in[]

==作业5.7.1==:j的初始值应为3,条件是≥0,–j;另外在i=0时要将B设为全0

吞吐率:单位时间内流水线所完成的任务数量或输出结果的数量

效率

加速比

Cache的字块内地址 VS Cache的字块地址

正数的补码反码和原码是一样的。原码和补码之间的互换方式都是除符号位之外,按位取反,末位加1

28

推断 跳转指令的转移地址 (PC+4)+(OFFSET)*4

条件转移指令的相对位移量(16位,用补码表示)的范围为:$-2^{15}至 +(2^{15}-1)$(是相对于转移指令的下调指令而言)。及最多往前调到第32768条指令(131072个单元),最多往后跳到第32767条指令(131068个单元)。

无条件转移指令的目标地址范围为:0~$2^{26}-1$(相对于下条指令),即,最近就跳到下条指令,最远跳到后面的$2^{26}-1$条指令

注意计算时int+short时的符号扩展

对阶操作不会引起阶码的溢出,因为是小阶向大阶对齐;右规可能造成阶码上溢;左规可能造成阶码下溢;尾数舍入过程,阶码加 1 而可能上溢;尾数溢出时结果不一定溢出。

某计算机的Cache共有32块,采用8路组相联映射方式。每个主存块大小为16字节,按字节编址。主存133号单元所在主存块应装入到的Cache组号是 0

汇编指令与流水线结合,如何修改给定的汇编代码,使得总指令周期最短?涉及到冒险的知识? Cache和虚存,已知Cache和内存表,给出访问要求,列出命中情况

29

(3)

在1000条指令过程中共访问存储器1500次,其中1410次仅访问一级Cache,54次访问至二级Cache,36次访问主存储器,要求它们的平均值:

$(14101+5410+36*100)/1500=3.7$

(4)

访存这一个动作,理论上只需要一个周期,一条指令有1.5次访存,也就是1.5个周期。而实际用了3.7个周期,多出来的2.2个时钟周期即为访问存储器导致的停顿。

(5)

每条指令访存1.5次,每次访存需要3.7个周期,只考虑访问存储器的话,CPI=1.5*3.7=5.55

1560692574537


今天是很美好的一天,因为和爸爸说了“父亲节快乐!”

存储器层次

局部性原理

存储信息交换的最小单元称为块(或行)

缺失代价:将相应的块从低层存储器替换到高层存储器所需的时间,包括访问块、将数据逐层传输、将数据插入发生缺失的曾和将信息传送给请求者的时间。

DRAM

现代DRAM以bank存储块方式组织。每个bank由多个行组成,发送一条Pre(预充电)命令能够打开或关闭一个bank。bank可同时进行读或写操作,“地址交叉”的轮转访问方式。多体(bank)并行

磁盘

磁道、扇区、柱面

扇区:512~4096个字节,扇区号、一个间隙、包含该扇区纠错码的信息、一个间隙、下一个扇区的扇区号

寻道、旋转延时(平均延时通常是磁盘转动一周时间的一半)、

Cache

直接映射:(Block address) modulo (#Blocks in cache)

标记(地址的高位,即 没有用来检索cache的那些位)、有效位

21

Cache大小固定,块的大小与数量的折中

Cache缺失处理

指令Cache缺失:流水线阻塞,PC-4的值送到存储器中,主存进行读操作,数据写入Cache,并将地址的高位(ALU中得到)写入标记域,设置有效位。重新取指。

写直达

写缓冲,满了就写

策略:写分配,数据块从主存中取回,并且在该块中的恰当区域重写数据(比如循环中的++i)。或直接改(变量初始化)不写入Cache。

写回

Cache被换才写 (dirty),可使用一个写缓冲来保存数据

计算Cache性能

Given:

  1. I-cache miss rate = 2%
  2. D-cache miss rate = 4%
  3. Miss penalty = 100 cycles
  4. Base CPI (ideal cache) = 2
  5. Load & stores are 36% of instructions

Miss cycles per instruction:

  1. I-cache: 0.02 × 100 = 2
  2. D-cache: 0.36 × 0.04 × 100 = 1.44

Actual CPI = 2 + 2 + 1.44 = 5.44

Ideal CPU is 5.44/2 =2.72 times faster

Average memory access time (AMAT) AMAT = Hit time + Miss rate × Miss penalty

Cache相联

全相联

组相连

22

替换策略

组相连:LRU或随机

多级Cache

计算CPI

一、二级Cache的任务不同(命中时间、缺失率)

通过分块进行软件优化—==分块算法操作子矩阵(我不会啊)==

可信存储器层次

平均无故障时间mean time to failure (MTTF)

平均维修时间mean time to repair (MTTR)

失效间隔平均时间Mean time between failures (MTBF) =MTTF+MTTR

可用性Availability = MTTF / (MTTF + MTTR)

增加MTTF –> 故障避免技术,故障容忍技术,故障预报技术

减少MTTR –> 采用故障检测、诊断和修复的工具

汉明码

检错

汉明纠错码:

所有编号为2的整数次幂的位标记为奇偶校验位,剩余为数据位

校验码1检查1,3,5,7…(二进制最右1位均为1)

校验码2检查2,3,6,7…(二进制最右2位均为1)

校验码4检查4,5,6,7…(二进制最右3位均为1)

……

计算SEC需要的位数:$2^p≥log(p+d+1)$,p个校验位,d个数据位

虚拟机

似乎不作为考试内容

虚存

页、缺页

虚页号 — 物理页号

页偏移

23

降低缺页率:使用全相连、先进的替换算法、写回机制

页的存放和查找

页表PTE:存放在存储器中,使用一个索引存储器的表来定位页。硬件包含一个指向页表首地址的寄存器。

24

每个页表项使用1位有效位、引用位(也叫使用位,周期性清零)、脏位。页表包含了每个可能的虚拟页的映射,因此不需要标记位。索引是用来访问页表的,由整个块地址即虚页号组成。主存中的页和磁盘中的页大小相等。

快表TLB

由于页表存放在主存中,程序每次至少两次访存:获得物理地址+获得数据。

利用页表的访问局部性,特殊的地址转换—>快表(地址变换高速缓存)

TLB每次装单条,是用全相连,需要回写。每个标记项存放虚页号的一部分,每个数据项中存放物理页号。TLB有标记域!

25

TLB缺失

如果不是缺页,处理器将页表中的变换装载到TLB中并重新访问

如果是缺页,操作系统更新页表

TLB和Cache实现从虚拟地址导数据项的转换

TLB在Cache的前面,物理页号与页偏移共同形成访问Cache的索引

26

图中标记和数据RAM是分开的,用Cache索引和块偏移寻址长而窄的数据RAM,无需使用16:1的多路选择器

Cache命中只可能发生在TLB命中之后

缺失的种类

强制缺失

容量缺失:在全相连时不可能容纳所有请求的块

冲突缺失(碰撞缺失)在全相连中不存在。

Design change Effect on miss rate Negative performance effect
Increase cache size Decrease capacity misses May increase access time
Increase associativity Decrease conflict misses May increase access time
Increase block size Decrease compulsory misses Increases miss penalty. For very large block size, may increase miss rate due to pollution.

有限状态机控制Cache

27

注意区别字地址和字节地址

不应用存储器平均访问时间来评估乱序处理器的存储器层次结构。—- 模拟乱序处理器和存储器层次结构

注意多个属性的外键

已知关系模式 R(a,b)和 S(b,c):

Q1: SELECT a FROM R,S WHERE R.b=S.b;

Q2: SELECT a FROM R WHERE b IN (SELECT b FROM S);

(A)Q1和Q2产生的结果一样;

(B)Q1的结果总是包含Q2的结果;

(C) Q2的结果总是包含Q1的结果;

(D) Q1和Q2产生不同的结果;

B,因为Q1会有重复的元组

如果违反3NF,会出现插入、删除、更新异常;满足了3NF,可能还是会出现插入、删除、更新异常

对日志进行recovery之后,在日志上、追加<Ti, abort>

逻辑查询计划和物理查询计划都有多个,只是最后选最优的执行

考试的第一题 根据ER写表,按上课教的方法画出来符合3NF要求

只有读操作的话,加读锁

触发器、存储过程、更新锁都不考

没有函数依赖的表,肯定是BCNF

解析–关系代数的树–逻辑层优化–估计节点大小、多种查询–物理计划–挑最好的执行

统计的中间结果存起来

物理模式,逻辑模式,用户模式

判断集合S中是否存在有两个其和等于x的元素

将S排序,借用辅助数组$S^{‘}=x-S$,合并$S^{‘}$和S

dutch national flag problem

红色球要全部在数组的左侧,白色球全部在中间,蓝色球全部在右侧,在遍历一次所有元素的情况下完成排序。

maximum-sub-segment-sum

针对每一个元素,有两个部分需要关注:① “过去部分” pre_sum;② “当前部分”nums[i]本身。有两种选择,① 加上pre_sum,本身融入到子串当中;② 以“当前部分”为子串起始位置,完全抛弃“过去部分”。

最大子矩阵

1
2
3
4
0, -2, -7,  0, 3
9, 2, -6, 2, 5
-4, 1, -4, 1, 6
-1, 8, 0, -2, 2

借鉴或者转为最大子序列,需要加一个辅助矩阵:全部子列和(totalColSum)

有了该辅助矩阵,我们就可以轻松求出指定列的子列和:

0, -2, -7, 0, 3
9, 0, -13, 2, 8
5, 1, -17, 3, 14
4, 9, -17, 1, 16

  • 假如当前的子矩阵是{0,1}行,可直接得到子列和为9,0,-13,2,8
  • 假如当前的子矩阵是{1,2}行,可通过totalColSum的第2行减去第0行的数据而得5,3,-4,3,11