Why do you think CS has more job prospects than other majors?



Because anything a computer can do, it can do millions of times for almost no additional cost. No matter how good a librarian is, they can't serve 2 billion people per month like Google can.
Also, once something is controlled by software, you can improve it continuously. Tesla can extend the range of their cars over the internet. Try that with a Camaro.
Nearly all of the people entering the software industry out of college have a degree in computer science or something similar. People with a CS degree have a long term advantage in their job search over those without one.




:::info{title="中文翻译"}
为什么你认为计算机科学（CS）比其他专业拥有更多的就业前景呢？
因为无论一个计算机能做什么，它都可以以几乎零成本的方式重复执行数百万次。无论图书管理员有多么出色，他们都无法像谷歌那样每月为20亿人提供服务。
此外，一旦某个事物由软件控制，你可以持续改进它。特斯拉可以通过互联网扩展汽车的续航里程，而对于一辆雪佛兰Camaro来说是不可能的。
几乎所有从大学毕业后进入软件行业的人都拥有计算机科学或类似专业的学位。拥有计算机科学学位的人在就业搜索中具有长期优势，相比那些没有这种学位的人。

:::

- CS: 计算机科学（Computer Science）的缩写，指计算机科学领域。
- Job prospects: 就业前景，指一个专业或行业提供的就业机会和发展前景。
- Major: 专业，指在大学中所选择的主修学科或领域。
- Librarian: 图书管理员，负责管理图书馆资源和提供相关服务的专业人员。
- Serve: 提供服务，满足需求。
- Billion: 十亿，表示数字1后面跟着9个零。
- Per month: 每月，表示在一个月的时间内。
- Software: 软件，计算机程序和数据的集合，用于控制计算机的操作和实现特定功能。
- Improve: 改进，使变得更好或更有效。
- Continuously: 持续不断地，连续不断地。
- Tesla: 特斯拉，一家以电动汽车和可再生能源技术为主的美国公司。
- Range: 续航里程，指电动车或其他交通工具能够行驶的距离。
- Internet: 互联网，全球计算机网络系统，连接了全世界的计算机和信息资源。
- Advantage: 优势，相对于其他人或事物具有的有利条件或位置。
- Job search: 就业搜索，寻找合适的工作机会的过程。

英语翻译 26

[爬楼梯](https://leetcode.cn/problems/climbing-stairs/description/)

```cpp
class Solution {
public:
    int climbStairs(int n) {
        if(n<=1) return n;
        vector<int>dp(n+1);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }

        return dp[n];



    }
};

```
[最小花费爬楼梯](https://leetcode.cn/problems/GzCJIP/description/)

```cpp
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1);

        dp[0]=0;
        dp[1]=0;

        for(int i=2;i<=cost.size();i++) {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }

        return dp[cost.size()];

    }
};
```
[过河卒](https://www.luogu.com.cn/problem/P1002)


```cpp
#include <bits/stdc++.h>
using namespace std;
long long dp[25][25];
int x,y,n,m;
bool s[30][30];
int main()
{
   cin>>n>>m>>x>>y;
   n+=2,m+=2,y+=2,x+=2;
   dp[2][1]=1;
   s[x][y]=1;
    s[x-2][y-1]=1;
	s[x-2][y+1]=1;
	s[x+2][y-1]=1;
	s[x+2][y+1]=1;
	s[x-1][y+2]=1;
	s[x-1][y-2]=1;
	s[x+1][y+2]=1;
	s[x+1][y-2]=1;
   for(int i=2;i<=n;i++)
   {
       for(int j=2;j<=m;j++)
       {
           if(s[i][j])continue;
           dp[i][j]=dp[i][j-1]+dp[i-1][j];
       }
   }
    cout<<dp[n][m];
    return 0;
}


// 大佬题解


```

[数字三角形](https://www.luogu.com.cn/problem/P1216)


```cpp
include<iostream> 
include<cstdio> 
include<cmath> 
using namespace std;  
int n;  
int a[1000][1000];  
int main()  
{       
	scanf("%d",&n);  
	for(int i=0;i<n;i++)  
	for(int j=0;j<=i;j++)  
	scanf("%d",&a[i][j]);//以上输入  
	for(int i=n-2;i>=0;i--)   
	{  
 		for(int j=0;j<=i;j++)//for循环按顺序扫描除最后一排前的所有数  
		a[i][j]+=max(a[i+1][j],a[i+1][j+1]); 
        //从左下，右下中选取大的加到现在的位置上 
    } 
    cout<<a[0][0]<<endl; 
    return 0; 
 }
 
 
 
 #include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
#define rint register int
inline void read(int &x)//读入优化 
{
    x=0;int w=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}
const int maxn=1000+10;
int n,a[maxn][maxn],ans; 
int main()
{
    read(n);
    for(rint i=1;i<=n;i++)
    {
        for(rint j=1;j<=i;j++)
        {
            read(a[i][j]);
            a[i][j]+=max(a[i-1][j-1],a[i-1][j]);//本题最重要的步骤 
            //a[i][j]代表从上往下到达i行j列这个点所能达到的和的最大值 
            ans=max(ans,a[i][j]);//在所有答案中找最大的（与在最底下一层找最大值是一样的）
        }
    }//边读入边计算，随手优化一下常数（其实只是懒得打for循环） 
    cout<<ans<<endl;
    return 0; 
} 


#include<stdio.h>
#include<iostream>
using namespace std;
int main(int argc, char** args) {
	int r = 0, map[1005][1005]; //r是层数, map用来存放对应的数字
	scanf("%d", &r);
	for(int i = 1;i <= r;i++) {
		for(int j = 1;j <= i;j++) {
			scanf("%d", &map[i][j]);
		}
	}
	int dp[1005][1005] = {0}, ans = 0; //dp用来存放状态, ans用来存放答案
	for(int i = 1;i <= r;i++) {
		for(int j = 1;j <= i;j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + map[i][j];
			if(dp[i][j] > ans) { //假如取到的数字和大于原先取到的
				ans = dp[i][j];
			}
		}
	}
	printf("%d", ans);
}
 
 
 
 
```

[线段](https://www.luogu.com.cn/problem/P3842)


```cpp
#include <iostream>
#include <cstdio>
#define rep(i,m,n) for(int i=m;i<=n;++i)
using namespace std;
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
const int MAXN = 20010;
int n;
int l[MAXN], r[MAXN], f[MAXN][2];
int main(){
    n = read();
    rep(i, 1, n) l[i] = read(), r[i] = read();
    f[1][0] = r[1] + r[1] - l[1] - 1;
    f[1][1] = r[1] - 1;
    rep(i, 2, n)
       f[i][0] = min(f[i-1][0] + abs(l[i-1] - r[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - r[i]) + r[i] - l[i] + 1),
       f[i][1] = min(f[i-1][0] + abs(l[i-1] - l[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - l[i]) + r[i] - l[i] + 1);
    printf("%d\n", min(f[n][0] + n - l[n], f[n][1] + n - r[n]));
    //rep(i, 1, n){ rep(j, 0, 1) printf("f[%d][%d] = %d, ", i, j, f[i][j]); puts(""); }
    return 0;
}
```

[整数划分](https://www.acwing.com/problem/content/902/)
```cpp

// 背包问题
using namespace std;

const int N = 1e3 + 7, mod = 1e9 + 7;

int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i <= n; i ++) {
        f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= n; j ++) {
            f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1
            if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
        }
    }

    cout << f[n][n] << endl

}
```

计数DP

按照官方文档的介绍，Redis所实现的是一种近似的LRU算法，每次随机选取一批数据进行LRU淘汰，而不是针对所有的数据，通过牺牲部分准确率来提高LRU算法的执行效率。



Redis内部只使用Hash表缓存了数据，并没有创建一个专门针对LRU算法的双向链表，之所以这样处理也是因为以下几个原因：

筛选规则，Redis是随机抽取一批数据去按照淘汰策略排序，不再需要对所有数据排序；



性能问题，每次数据访问都可能涉及数据移位，性能会有少许损失；

内存问题，Redis对内存的使用一向很“抠门”，数据结构都很精简，尽量不使用复杂的数据结构管理数据；

策略配置，如果线上Redis实例动态修改淘汰策略会触发全部数据的结构性改变，这个Redis系统无法承受的。



redisObject是Redis核心的底层数据结构，成员变量lru字段用于记录了此key最近一次被访问的LRU时钟(server.lruclock)，每次Key被访问或修改都会引起lru字段的更新。


```c
struct redisObject {
    unsigned type:4;      // 对象类型，占用4位，用于标识不同类型的对象
    unsigned encoding:4;  // 对象编码方式，占用4位，用于表示对象数据的存储方式
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;         // 引用计数，用于记录对象的被引用次数
    void *ptr;            // 指向实际存储对象数据的指针
};



unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        atomicGet(server.lruclock,lruclock);
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}
```
原文链接https://mp.weixin.qq.com/s/LsxzvpegWk6XVqhuqHKS4g

redis  LRU

什么是预读？

磁盘读写，并不是按需读取，而是按页读取，一次至少读一页数据（一般是4K），如果未来要读取的数据就在页中，就能够省去后续的磁盘IO，提高效率。

 



预读为什么有效？

数据访问，通常都遵循“集中读写”的原则，使用一些数据，大概率会使用附近的数据，这就是所谓的“局部性原理”，它表明提前加载是有效的，确实能够减少磁盘IO。

 

按页(4K)读取，和InnoDB的缓冲池设计有啥关系？

（1）磁盘访问按页读取能够提高性能，所以缓冲池一般也是按页缓存数据；

（2）预读机制启示了我们，能把一些“可能要访问”的页提前加入缓冲池，避免未来的磁盘IO操作；



传统的LRU缓冲池算法十分直观，OS，memcache等很多软件都在用，MySQL为啥这么矫情，不能直接用呢？

这里有两个问题：

（1）预读失效；

（2）缓冲池污染；

 

什么是预读失效？

由于预读(Read-Ahead)，提前把页放入了缓冲池，但最终MySQL并没有从页中读取数据，称为预读失效。

 

如何对预读失效进行优化？

要优化预读失效，思路是：

（1）让预读失败的页，停留在缓冲池LRU里的时间尽可能短；

（2）让真正被读取的页，才挪到缓冲池LRU的头部；

以保证，真正被读取的热数据留在缓冲池里的时间尽可能长。



改进版缓冲池LRU能够很好的解决“预读失败”的问题。

画外音：但也不要因噎废食，因为害怕预读失败而取消预读策略，大部分情况下，局部性原理是成立的，预读是有效的。

 

新老生代改进版LRU仍然解决不了缓冲池污染的问题。

 

什么是MySQL缓冲池污染？

当某一个SQL语句，要批量扫描大量数据时，可能导致把缓冲池的所有页都替换出去，导致大量热数据被换出，MySQL性能急剧下降，这种情况叫缓冲池污染。

 

例如，有一个数据量较大的用户表，当执行：

select * from user where name like "%shenjian%";

虽然结果集可能只有少量数据，但这类like不能命中索引，必须全表扫描，就需要访问大量的页：

（1）把页加到缓冲池（插入老生代头部）；

（2）从页里读出相关的row（插入新生代头部）；

（3）row里的name字段和字符串shenjian进行比较，如果符合条件，加入到结果集中；

（4）…直到扫描完所有页中的所有row…

 

如此一来，所有的数据页都会被加载到新生代的头部，但只会访问一次，真正的热数据被大量换出。

 

怎么这类扫码大量数据导致的缓冲池污染问题呢？

MySQL缓冲池加入了一个“老生代停留时间窗口”的机制：

（1）假设T=老生代停留时间窗口；

（2）插入老生代头部的页，即使立刻被访问，并不会立刻放入新生代头部；

（3）只有满足“被访问”并且“在老生代停留时间”大于T，才会被放入新生代头部；

原文链接https://mp.weixin.qq.com/s/zMgfT_WmyYmmUuZUUr6xOA


https://mp.weixin.qq.com/s/m662-Sa5dVnsWJH4NJObyA

mysql buffer pool

下面来讲解一下文件锁有关的API，它是进程级别的锁。
1. **`fcntl()`**：控制文件描述符的属性。



   ```c
   #include <fcntl.h>

   int fcntl(int fd, int cmd, ... /* arg */ );
   ```

   - `fd`：文件描述符。
   - `cmd`：控制命令，可以是以下之一：
     - `F_SETLK`：设置锁（非阻塞）
     - `F_SETLKW`：设置锁（阻塞）
     - `F_GETLK`：获取锁信息
   - `arg`：命令的附加参数，可以是一个 `struct flock` 结构。

   返回值：
   - 成功时返回执行命令的结果（根据命令不同）。
   - 失败时返回 -1，并设置 `errno`。

2. **`struct flock`**：文件锁信息结构。

   ```c
   struct flock {
       short l_type;    // 锁的类型：F_RDLCK、F_WRLCK、F_UNLCK
       short l_whence;  // 偏移量起点：SEEK_SET、SEEK_CUR、SEEK_END
       off_t l_start;   // 锁的起始偏移量
       off_t l_len;     // 锁的长度，0 表示锁住整个文件
       pid_t l_pid;     // 持有锁的进程ID（F_GETLK 命令返回）
   };
   ```

   - `l_type`：锁的类型，可以是 `F_RDLCK`（读锁）、`F_WRLCK`（写锁）、`F_UNLCK`（解锁）。
   - `l_whence`：偏移量起点，如 `SEEK_SET`、`SEEK_CUR`、`SEEK_END`。
   - `l_start`：锁的起始偏移量。
   - `l_len`：锁的长度，0 表示锁住整个文件。
   - `l_pid`：持有锁的进程ID，`F_GETLK` 命令返回时会填充。

3. **文件锁类型**：
   - **读锁（F_RDLCK）**：允许其他进程获取读锁，但阻止其他进程获取写锁。
   - **写锁（F_WRLCK）**：阻止其他进程获取读锁和写锁。
   - **解锁（F_UNLCK）**：释放文件上的锁。

以下是演示：

进程1 - 写入数据：

```c
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
    int fd = open("file_lock_example.txt", O_WRONLY | O_CREAT, S_IRUSR | S_IWUSR);
    if (fd == -1) {
        perror("打开文件失败");
        exit(1);
    }

    struct flock lock;
    lock.l_type = F_WRLCK;  // 写锁
    lock.l_whence = SEEK_SET;
    lock.l_start = 0;
    lock.l_len = 0;  // 锁住整个文件

    printf("进程1 尝试获取写锁...\n");
    if (fcntl(fd, F_SETLKW, &lock) == -1) {
        perror("获取写锁失败");
        exit(1);
    }

    printf("进程1 获取写锁成功，写入数据...\n");
    sleep(30);  // 模拟写入数据的耗时操作

    lock.l_type = F_UNLCK;  // 解锁
    if (fcntl(fd, F_SETLKW, &lock) == -1) {
        perror("解锁失败");
        exit(1);
    }

    close(fd);

    return 0;
}
```

进程2 - 读取数据：

```c
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
    int fd = open("file_lock_example.txt", O_RDONLY);
    if (fd == -1) {
        perror("打开文件失败");
        exit(1);
    }

    struct flock lock;
    lock.l_type = F_RDLCK;  // 读锁
    lock.l_whence = SEEK_SET;
    lock.l_start = 0;
    lock.l_len = 0;  // 锁住整个文件

    printf("进程2 尝试获取读锁...\n");
    if (fcntl(fd, F_SETLKW, &lock) == -1) {
        perror("获取读锁失败");
        exit(1);
    }

    printf("进程2 获取读锁成功，读取数据...\n");
    sleep(2);  // 模拟读取数据的耗时操作

    lock.l_type = F_UNLCK;  // 解锁
    if (fcntl(fd, F_SETLKW, &lock) == -1) {
        perror("解锁失败");
        exit(1);
    }

    close(fd);

    return 0;
}
```

当某个进程获取一个文件的写锁，这个文件就会被锁死，其他进程无法获取他的锁，包括写锁读锁，所以上面进程2会阻塞

![image.png](/static/img/82a0dd03c0404fbadfea23aa32c448bb.image.webp)

你也可以用信号量来进行模拟文件锁操作，还有共享内存等，锁就是一个与各自状态无关联且双方都能够访问的变量。