0%

加粗代表有价值的题目


2020-04-16 Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.


2020-04-17 Valid Parenthesis String

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

  1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  5. An empty string is also valid.

解决方法

  • 回溯 复杂度(3^N)
  • dp (N^3)
  • 贪心 (N)

2020-04-18 朋友圈问题 查并集

  1. 搞清楚索引数组的含义
  2. 更新的都是顶级索引

Number of Islands

1
2
3
4
5
6
7
Input:
11110
11010
11000
00000

Output: 1
  • 使用dfs
  • 使用union find


2020-04-20 Minimum Path Sum

1
2
3
4
5
6
7
8
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
  • 自己为自己做flag

2020-04-20 Search in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
  • 写二分变种的时候还是出了点问题

2020-04-21 Construct Binary Search Tree from Preorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
TreeNode* help(vector<int>& preorder, int s, int e) {
if (s == e) return nullptr;
TreeNode* node = new TreeNode(preorder[s]);
int index = s + 1;
while(index < e && preorder[index] < preorder[s]){
index++;
}
node->left = help(preorder, s + 1, index);
node->right = help(preorder, index, e);
return node;
}
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
return help(preorder, 0, preorder.size());
}
};

比四个月前写的进步了好多

2020-04-21 Product of Array Except Self

1
2
3
Input:  [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
  • 滑动窗口 O(N) 但用了除法
  • 双指针 完美解决

2020-04-22 Number Of Digit One

1
2
3
Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

ps 个位 十位 百位 分析


2020-04-23 Subarray Sum Equals K

主题 查找

和04-16如出一辙, 很好的题目!


2020-04-24 Bitwise AND of Numbers Range

1
2
3
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
Input: [5,7]
Output: 4

两个切入点

  • 高位考虑: 位数不同直接归零
  • 低位考虑: 两数不等, 低位必然是零

得到两种方法, 第一种递归, 第二中高效


2020-04-25 LRU

  • capacity
  • list
  • hashmap<key,iter>

2020-04-26 Jump Game


2020-04-27 Longest Common Subsequence

1
2
3
Input: text1 = "abcde", text2 = "ace" 
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

字符串类的dp问题一般都是两个字符串(也有可能是自己本身)逐个比较分析, 在这里

  • dp[i, j]代表text1[:i]text2[:j]的最长公共子序列长度

case1:
text1: xxxxxa
text2: xxxxxa
dp[i,j] = dp[i-1,j-1] + 1

case2:
text1: xxxxa
text2: xxxxb
dp[i,j] = max(dp[i-1, j], dp[i, j-1])


2020-04-29 Maximal Square

1
2
3
4
5
6
7
8
Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

dp 找规律

  • 结合正方形的特点设置状态
  • 找到各个dp之间的联系

2020-04-30 Binary Tree Maximum Path Sum

1
2
3
4
5
6
7
8
9
Input: [-10,9,20,null,null,15,7]

-10
/ \
9 20
/ \
15 7

Output: 42
  • 树的问题本质上都是树的遍历
  • 遍历每个点作为路径的拐点即可
  • 对于每个遍历的点, 需要求得左右两边单边的最大值, 如果是负数直接舍去

2020-05-01 Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

回溯即可


2020-05-02 278. First Bad Version

二分查找变种

  • 开区间
  • while(lo < hi)
  • 三种情况判断

2020-05-05 Number Complement

统计某个数字的位数, 怕溢出, 右移是个好选择


2020-05-06 387. First Unique Character in a String

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

easy题目, 绕了远路


2020-05-08 993. Cousins in Binary Tree

判断两个节点是否在一层并且父节点不同

关于层次

  • 使用队列层次遍历
  • 数组表示

2020-05-09 Check If It Is a Straight Line

  • 叉积!

2020-05-16 Maximum Sum Circular Subarray

分析

两种情况

  • 单区间
  • 双区间

单区间好解决, 双区间的话… 不就是sum减去中间吗(最小子序列和)

这是个好问题, 这么简单, 就是不好想


2020-05-17 Odd Even Linked List

把链表奇数位置和偶数位置的分开, 之后把偶数位置的item放到奇数的后面

链表的问题: 把链表的细节扣清楚


2020-05-18 Find All Anagrams in a String

方法一

固定长度的滑动窗口: 写起来代码比较多

方法二

不固定长度的滑动窗口: 这滑动窗口的框架真是经典


2020-05-20 Permutation in String

判断一个字符串的排列是否是另一个字符串的子串

滑动窗口

  • right移动: right没有到右端以及每个字符匹配的个数不足
  • left移动: 直到匹配的个数不满足为止

2020-5-25 最长公共子序列

dp[i][j]存储字符串str1和字符串str2的最长公共子序列, 则

  1. 如果str1[i] == str2[j] 那么dp[i][j] = dp[i-1][j-1] + 1
  2. 否则
    1. 采用str1[i], dp[i][j] = dp[i][j-1]
    2. 采用str2[j], dp[i][j] = dp[i-1][j]

And…

Max Dot Product of Two Subsequences

最大连续序列和

dp[i]代表以nums[i]结尾的最大连续序列和
dp[i] = max(nums[i], nums[i] + dp[i-1]

简化 dp[i] = nums[i] + max(0,dp[i-1])
因为只需要保存前一个变量, 所以空间值需要一个变量即可

1
2
3
4
5
6
7
8
9
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int cur = ans;
for(int i = 1; i < nums.size(); i++) {
cur = nums[i] + max(0, cur);
ans = max(ans, cur);
}
return ans;
}

最大子矩阵和

将上述问题扩展成二维问题 eg

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

求从i行到j行的最大子矩阵和(行数已知, 列未知), 只需要将矩阵压缩成一行数据后求最大连续序列和即可

求矩阵和, 就要遍历所有这样的行, 即 C(_n)(^2)种可能, 每种可能O(N)计算, 因此复杂度是O(N^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
// 1D连续最长子序列
int maxSeq(vector<int>& nums) {
int ans = 0, cur = 0, n = nums.size();
for(int i = 0; i < n; i++) {
cur = nums[i] + max(0, cur);
ans = max(ans, cur);
}
return ans;
}


int maxSubMatrix(vector<vector<int>>& nums) {
int n = nums.size(), m = nums[0].size(), maxsubrec = 0;
vector<int> dp(m, 0);
for(int i = 0; i < n; i++) {
std::fill(dp.begin(), dp.end(), 0);
for(int j = i; j < n; j++) {
for(int k = 0; k < m; k++) {
dp[k] += nums[j][k];

}
int curMax = maxSeq(dp);
maxsubrec = max(maxsubrec, curMax);
}
}
return maxsubrec;
}

自己实现shared_ptr

1. 数据成员

两个指针, 一个指向真正的内存, 另一个指向引用数量

1
2
3
private:
T* _ptr;
size_t* _count;

2. 生命周期

默认构造函数

1
2
3
4
5
6
7
SmartPointer(T* ptr = nullptr) : _ptr(ptr) {
if (_ptr) {
_count = new size_t(1);
} else {
_count = new size_t(0);
}
}

拷贝构造函数

1
2
3
4
5
6
7
SmartPointer(const SmartPointer& ptr) {
if (this != &ptr) {
this->_ptr = ptr._ptr;
this->_count = ptr._count;
(*this->_count)++;
}
}

拷贝赋值函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
SmartPointer& operator=(const SmartPointer& ptr) {
if (this->_ptr == ptr._ptr) {
return *this;
}
// 当前内存引用减一
if (this->_ptr) {
(*this->_count)--;
if (this->_count == 0) {
delete this->_ptr;
delete this->_count;
}
}
// 更改之后是引用加一
this->_ptr = ptr._ptr;
this->_count = ptr._count;
(*this->_count)++;
return *this;
}

析构

1
2
3
4
5
6
7
~SmartPointer() {
(*this->_count)--; // 引用数--
if (*this->_count == 0) { // 如果为0 删除
delete this->_ptr;
delete this->_count;
}
}

3. 函数成员

指针语义

1
2
3
4
5
6
7
8
9
T& operator*() {
assert(this->_ptr == nullptr);
return *(this->_ptr);
}

T* operator->() {
assert(this->_ptr == nullptr);
return this->_ptr;
}

引用数

1
2
3
size_t use_count(){
return *this->_count;
}

ps

实际上C++11中的智能指针引用数的更改是原子性的, 而且可以自定义删除函数.

问题

有64个鸡蛋, 有一个仪器可以同时测得8个鸡蛋重量的相对大小;
如果想要从64个鸡蛋中得到最重的4个, 最少称重多少次?

解答

将64个鸡蛋分成8组,每组8个鸡蛋, 组的编号为ABCDEFGH, A8代表A组的第8个鸡蛋
每组测试一次, 测试了8次
得到每组最重的鸡蛋, 假设是A1…H1, 将这8个在测一次, 测试了9次
假设从重到轻依次是A-H, 当前可以排除的鸡蛋是

  1. EFGH以及所在的组的全部鸡蛋, 因为要取最重的4个, EFGH组排不上号
  2. 对于D组, 因为A>B>C>D, 所以D组的其他鸡蛋也就排除
  3. 对于C组, 因为A>B>C, 至少有两个比C大, C组除了C1和C2都可以排除
  4. 同理, ABCD四个组分别留下 4 3 2 1个鸡蛋

经过9次测试, 现在只有10个鸡蛋, 并且知道其中最重的鸡蛋, 所以问题变成了从9个鸡蛋选最重的3个鸡蛋
此时
A2 > A3 > A4
B1 > B2 > B3
C1 > C2
D1
B1 > C1 > D1
因为无法确定最轻的鸡蛋, 所以必须测两次: 第一次任意8个, 将最轻的换下, 得到3个最重的鸡蛋

题目

每个飞机只有一个油箱,飞机之间可以相互加油(注意是相互,没有加油机)一箱油可供一架飞机绕地球飞半圈。为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?(所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场

解答

5架
(1)3 架飞机同时从机场出发,飞行八分之一周(A点),各耗油四分之一。此时某架飞机给其余两架补满油,自己返回基地;
(2)另一架飞机和目标机结伴,飞至四分之一周(B点),给目标机补满油,自己返回;
(3)目标机独自飞行半周(C点);
(4)与从基地反向出发的一架飞机相遇,2 机将油平分,飞至最后八分之一处(D点);
(5)与从基地反向出发的另一机相遇,各分四分之一油,返回。

如果想要为PyTorch贡献代码,回报开源社区,但是codebase却让你望而生畏,文章的目的就是分两部分给出一些指导

  1. 梳理“可以自动微分的Tensor库”的基本概念
  2. 介绍查看复杂的codebase的工具和技巧

共1070字,读完预计3分钟

前提

  • 写过PyTorch代码
  • 想要了解PyTorch的原理或者想要自定制PyTorch

第一部分:基本概念

首先介绍Tensor普遍的概念。从你熟悉的Tensor数据结构谈起,介绍一些tensor数据类型更加详细的讨论,帮助我们更好的理解Tensor是怎样实现的(如果你相当熟悉PyTorch,建议跳过);接着谈Tensor的三个拓展点:layoutdevicedtype

Tensor

Tensor是PyTorch中心数据结构,包含标量的n维数据和一些描述Tensor的元数据结构(Tensor的size,Tensor元素的dtype,Tensor的device)

对于二维Tensor Strides如何计算得到??

stride

stride是PyTorch与其他框架显著不同的特征

Tensor是一个数学概念,必须设计在计算机中如何表示Tensor,最常见的就是连续存储,如上图所示,Tensor存储32bits(4 Bytes)的整数,逐行连续存储,每两个之间的地址都相差4字节,Stride是如何将Tensor中的数字映射到连续的物理地址呢?

假设想要访问tensor[1,0]元素,那么通过计算对应维度与strides相乘得到偏置offset加tensor基地址就可以了,如图
$$
offset = 1 * 2 + 0 * 1 = 2\

addr = 0x10 + 2 * 4 = 0x18
$$
Strides是向用户提供Tensor不同视图的基础,举例来说,想要取Tensor的第二行
$$
offset = 1\cdot strides[1] = 2
$$

首先tensor[1,:]表示的是tensor的第二行的全部数字,在操作中,我们并没有创建新的Tensor,而是返回了原来Tensor的一个视图,不难发现3和4在连续的存储空间,我们所需要做的就是记录偏置(每个Tensor都有偏置,默认为0),如图所示,新的Tensor即为偏置为2,sizes为[2],strides为[1]的Tensor


$$
offset = 0 \cdot strides[0] = 0
$$
对于只取列的情况地址并不连续,这就是Stride的用武之地了。

如果Stride不为1,如图中所示为2,代表着两个元素之间要跳步,这也就是Stride的名字的由来,如图所示,新的Tensor就是偏置为0,size为[2],步长strides为[2]的Tensor

关于Tensor的实现

如上图,Tensor的实现主体在两个文件中,一个是c10/TensorImpl,另一个是c10/StorageImpl,Storage 定义了tensor的元素类型和物理大小,tensor定义了物理内存的逻辑解释:tensor的sizes、strides、offset

即使是最简单的Tensor创建torch.zeros(2,2),都会有

Tensor基本操作的实现细节

当你在做抽象层调用矩阵乘法torch.mm,会发生两种种类的动态分发

第一种是根据Tensor的设备类型和数据布局。不管是CPU的Tensor还是GPU的Tensor,不管是strided的layout还是sparse的layout,同样是矩阵乘法,但是实现细节是不一样的,所以如果没有对应的库,你没有别的选择,只能动态分布加载

第二种是Tensor元素的数据类型。实现中就是对不同dtype的简单的switch语句

Tensor 拓展

各种各样的Tensor

首先由三个参数确定Tensor的类型

  • device设备 描述Tensor存储在什么设备上 eg CPU、NVIDIA GPU(cuda)、AMD GPU(hip) 或者 TPU(xla)
  • layout数据布局 描述逻辑上如何解释物理内存 最常见的是strided tensor 其他的有 sparse tensor
  • dtype数据类型 描述Tensor元素的类型 eg integers float

一般安装Ubuntu系统后,连接网络缺少Wifi选项,也就是缺少无限网卡驱动。

我记得两三年前刚接触Linux遇到过这个问题,在安装盘中就有驱动的文件,两个命令安装就可以了,但是现在网上一搜一大把没有前因后果的垃圾……导致浪费了很多时间!!

两个驱动文件

  • dkms_2.2.0.3-2ubuntu11.1_all.deb
  • bcmwl-kernel-source_6.30.223.248+bdcom-0ubuntu8_amd64.deb

在文件ubuntu-16.04.1-desktop-amd64.iso的目录路径如下:

  • pool/main/d/dkms
  • pool/restricted/b/

分别安装即可

1
2
$ sudo dpkg -i dkms_2.2.0.3-2ubuntu11.1_all.deb
$ sudo dpkg -i bcmwl-kernel-source_6.30.223.248+bdcom-0ubuntu8_amd64.deb

Locks

当多核处理器共享内存(并发)的同时, 也带来了数据正确性的问题. 锁可以提供互斥机制, 确保在某个代码段只有一个CPU持有锁

竞争条件

假设几个处理器同时维护一个链表, 如果没有并发要求, 有如下实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct list {
int data;
struct list *next;
};

struct list *list = 0;

void
insert(int data)
{
struct list *l;

l = malloc(sizeof( *l));
l->data = data;
l->next = list; // 15
list = l;
}

单处理器执行是没有问题的, 如果多个处理器执行问题就会出现.

假设有两个CPU并发执行, A处理器执行完第15行, B处理器也可能执行到第14行, 此时两个新插入的数据同时指向链表中的第一个数据, 当两个处理器执行完代码, 必然有一个数据会丢弃.

这就是一个竞争条件的例子. 竞争条件是内存中的一个位置被并发访问, 至少一个在写数据. 如果读数据的进程读到一个不完整的数据, 就产生了bug.

避免竞争的常用方法是用锁Lock, 锁提供互斥, 确保在执行insert的时候只有一个CPU在执行, 添加几行实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct list *list = 0;
struct lock listlock;

void
insert(int data)
{
struct list *l;

acquire(&listlock);
l = malloc(sizeof( *l));
l->data = data;
l->next = list; // 15
list = l;
release(&listlock);
}

位于acquire和release之间的代码通知叫做关键段 critical section.

锁保护数据, 实际上是指保护应用到数据上的不变量. 不变量是指数据结构被操作时的属性.

在上例中, 不变量就是list指向第一个节点以及每个节点都指向下一个节点. 当执行到15行时, 不变量暂时被破坏. 锁的功能就是维护数据结构的不变量.

锁的实现

给出一个锁的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
struct spinlock{
uint locked;
}
void
acquire(struct spinlock *lk)
{
for(;;) {
if(!lk->lock) { // 8
lk->locked = 1;
break;
}
}
}

如果一个CPU获得了锁, 就跳出循环继续执行代码, 如果不能获得锁, 就一直空循环, 一次次的查看锁是否释放.

但是上述实现实际上是有问题的. 当两个CPU同时执行到第8行, 一个CPU获得了锁, 跳出循环, 另一个CPU同样可以执行, 锁没有起到应有的作用.

一行代码, 甚至是变量++, 都不是原子的, 真正原子的是一条汇编指令.

如果将8行和9行变为原子操作, 那么锁就起作用了. 处理器正是提供了一个专用的指令完成了这样一个操作xchg

在一个原子操作中, 该指令可以将内存中的一个字和寄存器交换, 以下每次迭代读lk->locked然后置1, 如果已经有锁, lk->locked已经是1, 返回0 , 否则返回1.

1
2
3
// The xchg is atomic.
while(xchg(&lk−>locked, 1) != 0)
;

内置类型、自定义类型的机制

第二章 变量和基本类型

Types are fundamental to any program: They tell us what our data mean and what operations we can perform on those data.

2.1 原始的内置类型

2.1.1 算数类型

算数类型包括整型和浮点型,cpp标准规定了各个类型占用的最小位数

signed unsigned

哪些类型区分有无符号?整型除了bool和扩展char类型外,都区分有/无符号

char是signed还是unsigned取决于编译器

选择类型Tips

  • 选double:float和double花销忽略不计,float往往精度不够 long double没必要
  • 用int:short太短,long又往往和int一样,如果不够用long long

问题

@CSAPP
int short long 区别
double float只是位数不同吗

2.1.2 类型转换

赋值时

1
2
3
4
unsigned char c1 = -1; // 255
signed char c2 = 256; // 0
// sizeof(1) = 4字节
// 这种赋值时候的做法像是直接截断

判断时

if 条件判断自动转换 非bool <=> bool

unsigned类型永远都会大于等于零

计算时

一般来讲是向上转换,尽量不丢失信息
当一个有符号一个无符号,有符号转为无符号型

1
2
3
4
unsigned u = 10;
int i = -42;
cout << u + i << endl;
// i 先转换为无符号型,之后在相加

2.1.3 常量

常量的类型都是什么?

常量的类型由前后缀显式决定
注意到:对于浮点数 L是long double 默认double f是float

其他

true false nullptr

2.2 变量

A variable provides us with named storage that our programs can manipulate.

2.2.1 变量定义

初始化和赋值

初始化是在创建对象时给该对象value,赋值是要覆盖原来的value,在C++中真的有很大的区别吗?

list 初始化

@

默认初始化 =》 没有显式初始化

默认值取决于变量的类型和定义的位置

当变量定义在函数外时,会被初始化为0,在函数内时,随机数,正常访问
(书上说是未初始化类型,访问会Error……)

2.2.2 变量的声明和定义

为了分离编译,C++区分变量的声明和定义,声明是告诉程序别处有这个变量,定义是让程序弄出个实体来

1
2
3
extern int j; // 声明
int i; // 定义
extern double pi = 3.14; // 定义 覆盖外部的变量

scope

相同变量名在不同的scope可以有多个定义,内嵌的变量会屏蔽外层的变量,除非有特定的目的,不然不建议这样使用

2.3 复合类型

A compound type is a type that is defined in terms of another type.引用和指针就是两种复合类型

2.3.1 引用

1
2
3
int refVal = 2;
int &refVal3 = refVal; // reference
int &refVal2 = refVal3; // 2rd alias

2.3.2 指针

空指针

  • nullptr
  • 0
  • NULL #include

指针的引用

1
2
3
4
5
int i = 42;
int *p;
int *&r = p;
r = &i;
*r = 0;

第三行从右往左读,&r代表是一个引用,int *代表一个整型指针的引用,所以最后r就是p的引用,就是p的第二个名字,就有了后面两行

问题

  1. 还有哪些复合类型
  2. 引用和指针到底有什么不同
    1. 指针本身是一个object,引用不是
    2. 指针可以被赋值被复制,引用是一次性绑定
    3. 指针不用初始化定义,引用一定要初始化

2.4 const 限定符

const 修饰的变量必须定义时初始化,如果不初始化,也行,extern

1
extern const int bufSize;

2.4.1 const类型的引用

定义

1
2
3
4
const int ci = 1024;
const int &ref = ci;
r1 = 43; // Error
int &r2 = ci; // Error

存在绑定引用类型不匹配情况:可以绑定一个const引用到一个非const对象,常量 或者表达式

1
2
3
4
double dval = 3.14;
const int &ri = dval; // pass
// ri => 3
int &ri = dval; // error

为什么一定要是const呢?

1
2
const int temp = dval;
const int &ri = temp;

如果没有const,ri可以修改,那么ri修改的实际是是temp,dval没有变,这显然违背了引用的原意,是不合适的

用const修饰的引用,去引用一个没用const的变量有什么用呢

1
2
3
4
5
int i = 43;
int &r1 = i;
const int &r2 = i;
r1 = 0;
r2 = 0; //error

该引用对object只读,但是object可以通过别的引用写

2.4.2 指针和引用

1
2
3
4
5
6
7
8
const double pi = 3.14;   //pi is const; its value may not be changed
double *ptr = &pi; //error: ptr is a plain pointer
const double *cptr = &pi; //ok: cptr may point to a double that is const
*cptr = 42; //error: cannot assign to *cptr
int errNumb = 0;
int *const curErr = &errNumb; // curErr will always point to errNumb
const double pi = 3.14159;
const double *const pip = &pi; // pip is a const pointer to a const object

注意

1
2
3
4
5
6
const int &r = 0; // pass
int &r = 0; // error
double dval = 3.14;
const int &ri = dval;
// ri => 3
int &ri = dval; //error

2.4.3 Top-Level const

1
2
3
4
5
6
7
8
int i = 0;
int *const p1 = &i; // we can't change the value of p1; const is top-level

const int ci = 42; // we cannot change ci; const is top-level
const int *p2 = &ci; // we can change p2; const is low-level

const int *const p3 = p2; // right-most const is top-level, left-most is not
const int &r = ci; // const in reference types is always low-level

const关键字限定自己不能改变的就是top-level,否则就是low-level,当复制一个对象的时候,top-level忽略,low-level不能忽略

low-level 不同,类型不同,如果不能通过convert,就会Error

2.4.4 常量表达式

  • 初始化定义常量
  • 编译时确定

constexpr 变量

Variables declared as constexpr are implicitly const and must be initialized by constant
expressions

1
2
const int *p = nullptr;     // p is a pointer to a const int p是指向int常量的指针
constexpr int *q = nullptr; // q is a const pointer to int q是指向int的常量指针

区别非常大,constexpr在对象上组成了一个top-level const,所以p可以指向另一个const int类型的变量,但是q是top-level,不能改,只能初始化定义死了。

2.5 Dealing with Types

2.5.1 类型别名

传统方法

1
2
typedef double wages; // wages => double
typedef wages base, *p; // base => double p=>double *

新方法

1
2
// cpp 11
using sufu = wages;

2.5.2 auto

cpp11 auto ordinarily ignores top-level consts.

1
2
3
4
5
6
7
8
9
10
11
12
13
int i = 0, &r = i;
const int ci = i, &cr = ci;
auto b = ci; // b is an int (top-level const in ci is dropped)
auto c = cr; // c is an int (cr is an alias for ci whose const is top-level)
auto d = &i; // d is an int*(& of an int object is int*)
auto e = &ci; // e is const int*(& of a const object is low-level const)

const auto f = ci; // deduced type of ci is int; f has type const int

auto k = ci, &l = i; // k is int; l is int&
auto &m = ci, *p = &ci; // m is a const int&;p is a pointer to const int
// error: type deduced from i is int; type deduced from &ci is const int
auto &n = i, *p2 = &ci;

2.5.3 decltype

和auto类似,让编辑器猜类型的

1
2
3
4
const int ci = 0, &cj = ci;
decltype(ci) x = 0; // x has type const int
decltype(cj) y = x; // y has type const int& and is bound to x
decltype(cj) z; // error: z is a reference and must be initialized

2.6 写自己的类型

2.6.2 写自己的Header文件

Header包含entities

  • class定义
  • const类型
  • constexpr类型

假设有两个进程, 进程A向进程B发送信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct q { 
void *ptr;
}

void send(struct q *position, void *data) {
while(position->ptr != 0) ; // 当前的数据还没有被读完
position->ptr = data; // 设置数据
}

void *recv(struct q *position){
void *getData;
while((getData = position->ptr)==0) ; // 没有数据可读
position->ptr = 0; // 读完毕
return getData; // 返回读到的data
}

上面的实现开销很大, 如果发送方很少发, 那么接受方就要一直空转. 避免接收方空转的一种方法是接收方让出CPU直到发送方传递数据才恢复.

假设有一对调用, wait和notify, 按照一下方式工作, wait(chan)在通道chan上等待, notify(chan)将在通道chan上等待的进程唤醒, 如果没有在通道chan上的进程, notify就什么都不做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct q { 
void *ptr;
}

void send(struct q *position, void *data) {
while(position->ptr != 0) ; // 当前的数据还没有被读完
position->ptr = data; // 设置数据
notify(position);
}

void *recv(struct q *position){
void *getData;
while((getData = position->ptr) == 0) // 1.
wait(position); // 没有数据可读
position->ptr = 0; // 读完毕
return getData; // 返回读到的data
}

然而事实没有那么简单, 假设recv在执行完1处并且将要执行下一行(wait)的时候, send开始执行(访问内存), 一下执行到notify, 发现并没有可以唤醒的进程, 此时recv继续执行, wait, 造成了死锁

问题的根源在于违反了recv只有在position->ptr为0时候才会wait的不变性

引入系统提供的自旋锁(参考), 更换函数接口, wait(chan, &lock). 在通道chan等待挂起并且释放lock锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct q { 
struct spinlock lock;
void *ptr;
}

void send(struct q *position, void *data) {
acquire(&position->lock);
while(position->ptr != 0) ; // 当前的数据还没有被读完
position->ptr = data; // 设置数据
notify(position);
release(&position->lock);
}

void *recv(struct q *position){
void *getData;

acquire(&position->lock);
while((getData = position->ptr)==0)
wait(position, &position->lock); // 没有数据可读
position->ptr = 0; // 读完毕
release(&position->lock);
return getData; // 返回读到的data
}

如果send函数很少发信息, 那么大多数情况, recv是状态一直在进程表中是睡眠, 并不会占用CPU资源, 而且此时关于此代码系统中是没有锁的. 如果send函数调用, 重新获取锁, 将recv进程状态唤醒, 程序继续执行.

总之将之前的空转的状态代替成了睡眠, 但是正确性没有变, 减少了开销, 值得注意的是, 最底层的实现仍是自旋锁.

wait函数内部逻辑(唤醒后重新获取锁)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void wait(void *chan, struct spinlock *lk)
{
struct proc *p = myproc();

...
// Go to sleep.
p->chan = chan; // 设置当前进程等的通道chan
p->state = SLEEPING; // 让出执行权 设置当前进程是睡眠

sched(); // 调度其他进程
...
p->chan = 0;
acquire(lk);// 重新获取锁
}

notify函数内部逻辑

1
2
3
4
5
6
7
8
void notify(void *chan)
{
struct proc *p;
// 所有睡眠进程中通道是chan的进程设置成RUANNABLE
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
if(p->state == SLEEPING && p->chan == chan)
p->state = RUNNABLE;
}