Trluper

什么是KMP算法

KMP算法一种改进的模式匹配算法，是D.E.Knuth、J.H.Morris、V.R.Pratt于1977年联合 发表。KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配，后文主串和模式串匹配， 子串和模板串匹配。先在开头约定，本文用pat表示模式串，长度为 M，txt 表示文本串，长度为N。KMP 算法是在 txt 中查找子串 pat，如果存在，返回这个子串的起始索引，否则返回 -1。

几个最基本的概念：

• 字符串的前缀：从主串下标0开始的子串称为主串的前缀
• 字符串的后缀：从主串下标大于0的位置到结尾的子串称为主串的后缀
• 目标串：也就是主串，简单说就是那条比较长的串txt
• 模式串：也就是那条短的，用来匹配的串pat
• kmp算法的目的：在\(O(m+n)\)的时间复杂度的内进行串匹配，也就是在目标串中找到模式串，并返回目标串中模式串的第一个字符下标

1. 消息队列的优缺点？

• 异步处理 - 相比于传统的串行、并行方式，消息队列使服务端能够异步处理请求，提高了系统吞吐量。
• 应用解耦 - 系统间通过消息通信，不用关心其他系统的处理。
• 流量削锋 - 可以通过消息队列长度控制请求量；可以缓解短时间内的高并发请求。
• 日志处理 - 解决大量日志传输。
• 消息通讯 - 消息队列一般都内置了高效的通信机制，因此也可以用在纯的消息通讯。比如实现点对点消息队列，或者聊天室等。

解耦、异步、削峰是什么？

• 解耦：A 系统发送数据到 BCD 三个系统，通过接口调用发送。如果 E 系统也要这个数据呢？那如果 C 系统现在不需要了呢？A 系统负责人几乎崩溃…A 系统跟其它各种乱七八糟的系统严重耦合，A 系统产生一条比较关键的数据，很多系统都需要 A 系统将这个数据发送过来。如果使用 MQ，A 系统产生一条数据，发送到 MQ 里面去，哪个系统需要数据自己去 MQ 里面消费。如果新系统需要数据，直接从 MQ 里消费即可；如果某个系统不需要这条数据了，就取消对 MQ 消息的消费即可。这样下来，A 系统压根儿不需要去考虑要给谁发送数据，不需要维护这个代码，也不需要考虑人家是否调用成功、失败超时等情况。

-** 异步：**A 系统接收一个请求，需要在自己本地写库，还需要在 BCD 三个系统写库，自己本地写库要 3ms，BCD 三个系统分别写库要 300ms、450ms、200ms。最终请求总延时是 3 + 300 + 450 + 200 = 953ms，接近 1s，用户感觉搞个什么东西，慢死了慢死了。用户通过浏览器发起请求。如果使用 MQ，那么 A 系统连续发送 3 条消息到 MQ 队列中，假如耗时 5ms，A 系统从接受一个请求到返回响应给用户，总时长是 3 + 5 = 8ms

• 削峰：将请求统统放到消息队列里去，服务器从消息队列中取任务，这样可以减少高峰时期对服务器压力。

缺点

• 系统可用性降低：加入个消息队列进去，那消息队列宕机了了，你的系统也就无法使用。因此，系统可用性会降低；
• 系统复杂度提高：加入了消息队列，要多考虑很多方面的问题，比如如何保证消息不被重复消费、如何保证消息可靠性传输等。因此，需要考虑的东西更多，复杂性增大。

2. RabbitMQ怎么保证消息的可靠性？

RabbitMQ消息的传输会经过三个阶段从生成者到Rabbit服务器的队列再到消费者，因此我们在三个阶段采取来保证消息的可靠性：

• 生产者丢失数据：在消息还未到达RabbitMQ服务器上时，未防止RabbitMQ服务器宕机导致的消息丢失，我们可以将信道设置成 confirm 模式（发送方确认模式）一旦channel进入confirm模式，所有在该信道上发布的消息都将会被指派一个唯一的ID（从1开始），一旦消息被投递到所有匹配的队列之后；rabbitMQ就会发送一个ACK给生产者（包含消息的唯一ID），这就使得生产者知道消息已经正确到达目的队列了；如果rabbitMQ没能处理该消息，则会发送一个Nack消息给你，你可以进行重试操作。 >- 另外一个方案是走事务机制，送消息前，开启事务（channel.txSelect()）,然后发送消息，如果发送过程中出现什么异常，事务就会回滚（channel.txRollback()）,如果发送成功则提交事务（channel.txCommit()）。然而，这种方式有个缺点：吞吐量下降；

• 消息队列丢数据：开启RabbitMQ的持久化策略，将消息持久化进磁盘。和confirm机制配合使用，你可以在消息持久化磁盘后，再给生产者发送一个Ack信号。这样，如果消息持久化磁盘之前，rabbitMQ阵亡了，那么生产者收不到Ack信号，生产者会自动重发。 >操作和简单：1、将queue的持久化标识durable设置为true,则代表是一个持久的队列；2、 发送消息的时候将deliveryMode=2

• 消费者丢失数据：消费者丢数据一般是因为采用了自动确认消息模式，我们将它改为手动确认即可

3. 交换机Exchange有哪些模式

• fanout交换器：它会把所有发送到该交换器的消息路由到所有与该交换器绑定的队列中；
• direct交换器：direct类型的交换器路由规则很简单，它会把消息路由到那些Routing_Key完全匹配的队列中；
• topic交换器：匹配规则比direct更灵活。
• headers交换器：根据发送消息内容的headers属性进⾏匹配（由于性能很差，不实⽤）

3. 消息基于什么传输？

由于TCP连接的创建和销毁开销较大，且并发数受系统资源限制，会造成性能瓶颈。 RabbitMQ使⽤信道的方式来传输数据。信道是建⽴在真实的TCP连接内的虚拟连接，且每条 TCP连接上的信道数量没有限制。

• RabbitMQ采用类似非阻塞IO（Non-blocking I/O）做法，选择TCP连接复⽤，不仅可以减少性能开销，同时也便于管理。
• 每个线程把持一个信道，所以信道复用了Connection的TCP连接。同时RabbitMQ可以确保每个线程的私密性，就像拥有独立的连接一样。

4. 如何避免消息重复投递或重复消费？

消费端处理消息的业务逻辑保持幂等性。只要保持幂等性，不管来多少条重复消息，最后处理的结果都一样。如保证每条消息都有唯一编号且保证消息处理成功与去重表的日志同时出现。利用一张日志表来记录已经处理成功的消息的 ID，如果新到的消息 ID 已经在日志表中，那么就不再处理这条消息。

5. 如何保证消息的顺序

• （1）保证生产者 - MQServer - 消费者是一对一对一的关系。 缺陷：
  • 并行度就会成为消息系统的瓶颈（吞吐量不够）
  • 更多的异常处理，比如：只要消费端出现问题，就会导致整个处理流程阻塞，我们不得不花费更多的精力来解决阻塞的问题。
• （2）通过合理的设计或者将问题分解来规避。
  • 不关注乱序的应用实际大量存在
  • 队列无序并不意味着消息无序 所以从业务层面来保证消息的顺序而不仅仅是依赖于消息系统，是一种更合理的方式。

6. 如果有一个消息一直得不到消费，比如客户端宕机且设置手动确认，然后一直未手动确认，此时怎么办？

在RabbitMQ中，当消费者未正常消费消息，由于未收到来自消费者的确认，就会进行重试策略，但重试策略必须有一个次数，不然一直有这样的消息得不到消费，一直占用队列资源就造成吞吐量的低下。

因此当一个消息在队列中达到一定的重试次数后仍然无法被成功处理，或者因为某些原因（如TTL过期、队列达到最大长度等）被队列拒绝返回nack时，RabbitMQ可以将这些消息发送到另一个交换机（Dead Letter Exchange），进而路由到一个专门的队列（Dead Letter Queue, DLQ），即死信队列。

DLQ中的消息代表了那些经过多次尝试仍无法被成功处理的消息。你可以有一个专门的消费者来监听DLQ，并对这些消息进行进一步的处理，例如记录日志、发送告警或者进行人工干预。

7. RabbitMQ基本概念

• Broker： 简单来说就是消息队列服务器实体
• Exchange： 消息交换机，它指定消息按什么规则，路由到哪个队列
• Queue： 消息队列载体，每个消息都会被投入到一个或多个队列
• Binding： 绑定，它的作用就是把exchange和queue按照路由规则绑定起来
• Routing Key： 路由关键字，exchange根据这个关键字进行消息投递
• VHost： vhost 可以理解为虚拟 broker ，即 mini-RabbitMQ server。其内部均含有独立的 queue、exchange 和 binding 等，但最最重要的是，其拥有独立的权限系统，可以做到 vhost 范围的用户控制。当然，从 RabbitMQ 的全局角度，vhost 可以作为不同权限隔离的手段（一个典型的例子就是不同的应用可以跑在不同的 vhost 中）。
• Producer： 消息生产者，就是投递消息的程序
• Consumer： 消息消费者，就是接受消息的程序
• Channel： 消息通道，在客户端的每个连接里，可建立多个channel，每个channel代表一个会话任务

8. 什么原因会导致 MQ 消息积压?

MQ消息积压是指生产者发送的消息在Broker端大量堆积，无法被消费者及时消费，导致业务功能无法正常使用。以下是一些导致MQ消息积压的常见原因：

-** 流量变大而服务器配置偏低：当消息的产生速度大于消费速度时，如果RabbitMQ服务器配置较低，就可能导致消息积压。 - 消费者故障：如果消费者出现宕机或网络问题，导致无法及时消费消息，消息会持续堆积。 - 程序逻辑设计问题：如果生产者持续生产消息，但消费者由于某种原因（如处理逻辑耗时过长）消费能力不足，也会造成消息积压。 - 新上线的消费者功能存在BUG：新上线的消费者功能如果有缺陷，可能导致消息无法被正常消费，从而引发消息堆积。 - 配置不合理：消息队列的容量设置过小或消费者的线程数设置过少，都可能导致消息积压。 - 生产者推送大量消息**：在特定场景下，如大促活动，生产者可能短时间内推送大量消息至Broker，如果消费者的消费能力不足以应对这种突发流量，也会导致消息堆积。

了解决MQ消息积压问题，可以采取以下策略：

• 扩容：纵向扩容，增加服务器资源，如内存和CPU；横向扩容，将单机改为集群模式，增加集群节点，并增加消费者数量。
• 优化程序逻辑：确保生产者和消费者的逻辑设计合理，避免生产者过快生产消息或消费者处理消息过慢。
• 监控和报警：建立有效的监控和报警机制，及时发现并解决消息积压问题。

8. 有几百万消息持续积压几小时，怎么办？

消息积压处理办法：临时紧急扩容

• 1.先修复 consumer 的问题，确保其恢复消费速度，然后将现有 cnosumer 都停掉。
• 2.新建一个topic,临时建立好原先 10 倍的 queue 数量。
• 3.然后写一个临时的分发数据的 consumer 程序，这个程序部署上去消费积压的数据，消费之后不做耗时的处理，直接均匀轮询写入临时建立好的 10 倍数量的 queue。
• 4.接着临时征用 10 倍的机器来部署 consumer，每一批 consumer 消费一个临时 queue 的数据。这种做法相当于是临时将 queue 资源和 consumer 资源扩大 10 倍，以正常的 10 倍速度来消费数据
• 5.等快速消费完积压数据之后，得恢复原先部署的架构，重新用原先的 consumer 机器来消费消息。

9 与其他消息队列的区别比较？

ctiveMQ：的社区算是比较成熟，但是较目前来说，ActiveMQ 的性能比较差，而且版本迭代很慢，不推荐使用。

RabbitMQ：在吞吐量方面虽然稍逊于 Kafka 和 RocketMQ ，但是由于它基于 erlang 开发，所以并发能力很强，性能极其好，延时很低，达到微秒级。但是也因为 RabbitMQ 基于 erlang 开发，所以国内很少有公司有实力做erlang源码级别的研究和定制。如果业务场景对并发量要求不是太高（十万级、百万级），那这四种消息队列中，RabbitMQ 一定是你的首选。如果是大数据领域的实时计算、日志采集等场景，用 Kafka 是业内标准的，绝对没问题，社区活跃度很高，绝对不会黄，何况几乎是全世界这个领域的事实性规范。

RocketMQ：阿里出品，Java 系开源项目，源代码我们可以直接阅读，然后可以定制自己公司的 MQ，并且 RocketMQ 有阿里巴巴的实际业务场景的实战考验。RocketMQ 社区活跃度相对较为一般，不过也还可以，文档相对来说简单一些，然后接口这块不是按照标准 JMS 规范走的有些系统要迁移需要修改大量代码。还有就是阿里出台的技术，你得做好这个技术万一被抛弃，社区黄掉的风险，那如果你们公司有技术实力我觉得用RocketMQ 挺好的。

kafka：特点其实很明显，就是仅仅提供较少的核心功能，但是提供超高的吞吐量，ms 级的延迟，极高的可用性以及可靠性，而且分布式可以任意扩展。同时 kafka 最好是支撑较少的 topic 数量即可，保证其超高吞吐量。kafka 唯一的一点劣势是有可能消息重复消费，那么对数据准确性会造成极其轻微的影响，在大数据领域中以及日志采集中，这点轻微影响可以忽略这个特性天然适合大数据实时计算以及日志收集。

10 RabbitMQ 上的⼀个 queue 中存放的 message 是否有数量限制？

可以认为是没有限制，因为限制取决于机器的内存，但是消息过多会导致处理效率的下降。

0概述一下你认识的Redis？

Redis本质上是一个Key-Value类型的内存数据库，很像memcached，整个数据库统统加载 在内存当中进行操作，定期通过异步操作把数据库数据flush到硬盘上进行保存。 因为是纯内存操作，Redis的性能非常出色，每秒可以处理超过 10万次读写操作，是已知性能 最快的Key-Value DB。 Redis的出色之处不仅仅是性能，Redis最大的魅力是支持保存多种数据结构，此外单个value 的最大限制是1GB，不像 memcached只能保存1MB的数据，因此Redis可以用来实现很多有用的功能。比方说用他的List来做FIFO双向链表，实现一个轻量级的高性 能消息队列服务，用他的Set可 以做高性能的tag系统等等。 另外Redis也可以对存入的Key-Value设置expire时间，因此也可以被当作一 个功能加强版的 memcached来用。 Redis的主要缺点是数据库容量受到物理内存的限制，不能用作海量数据 的高性能读写，因此Redis适合的场景主要局限在较小数据量的高性能操作和运算上。

0.1 Redis 与其他 key - value 缓存产品有以下三个特点

• Redis支持数据的持久化，可以将内存中的数据保存在磁盘中，重启的时候可以再次加载进行使用。
• Redis不仅仅支持简单的key-value类型的数据，同时还提供list，set，zset，hash等数据结构的存储。
• Redis支持数据的备份，即master-slave模式的数据备份。

0.2 Redis 优势

• 性能极高 。Redis能读的速度是110000次/s,写的速度是81000次/s 。
• 丰富的数据类型。 Redis支持二进制案例的 Strings, Lists, Hashes, Sets 及 Ordered Sets数据类型操作。
• 操作的原子性。 Redis的所有操作都是原子性的，意思就是要么成功执行要么失败完全不执行。单个操作是原子性的。多个操作也支持事务，即原子性，通过MULTI和EXEC指令包起来。
• 丰富的特性。Redis还支持 publish/subscribe, 通知, key 过期等等特性

1. Redis数据类型

Redis提供了String,Hash,List,Set,Zset五种数据类型。

1.1 String

String数据结构是最简单的key-value类型，value不仅可以是String,也可以是数字，包括整数，浮点数和二进制数。

string 数据结构是简单的 key-value 类型。虽然 Redis 是用 C 语言写的，但是 Redis 并没有使用 C 的字符串表示，而是自己构建了一种 简单动态字符串（simple dynamic string，SDS）。相比于 C 的原生字符串：

• Redis 的 SDS 不光可以保存文本数据还可以保存二进制数据
• 并且获取字符串长度复杂度为 O(1)（C 字符串为 O(N)）
• 除此之外，Redis 的 SDS API 是安全的，不会造成缓冲区溢出。因为 SDS 在拼接字符串之前会检查 SDS 空间是否满足要求，如果空间不够会自动扩容，所以不会导致缓冲区溢出的问题

主要的应用有：缓存，计数（比如用户的访问次数、热点文章的点赞转发数量等等），共享session和限速。

准备工作

安装Redis

1. 在ubuntu安装Redis

   1	sudo apt-get install redis-server

2. Redis服务器连接默认没有密码，可通过更改/etc/redis/redis.conf内的# requirepass foobared来指定登录密码,比如去掉注释后更改密码为requirepass 123456，指定了密码为123456

   1 2 3

   sudo vim /etc/redis/redis.conf #修改密码 requirepass 123456

3. 运行远程连接redis，redis默认只允许本地连接，你可以通过注释掉bind 127.0.0.1::1来支持远程登录。

1 介绍

此次project0项目是实现一个键值对存储，数据结构由写时复制的字典树构成。实现的键-值存储可以存储映射到任何类型值的字符串键。键的值存储在表示该键的最后一个字符的节点中(又称终端节点)。例如，考虑在trie中插入kv对("ab"， 1)和("ac"， "val")。

2 Task1:Copy-On-Write trie

• 在本任务中，只需要修改trie .h和trie .cpp来实现写时复制(copy-on-write) tree。在写即复制tree中，操作不会直接修改原始tree中的节点。相反，将为修改后的数据创建新节点，并为新修改的trie返回一个新根。写时复制(Copy-on-write)使我们能够在每次操作之后随时以最小的开销访问该树。考虑在上面的例子中插入("ad"， 2)。我们通过重用原始树中的两个子节点来创建一个新的Node2，并创建一个新的值节点2。(见下图)

• 插入("b"， 3)，我们将创建一个新的根，一个新的节点，并重用以前的节点。通过这种方式，我们可以在每次插入操作之前和之后获得树的内容。只要我们有根对象(Trie类)，我们就可以访问当时Trie中的数据。(见下图)

• 插入(“a”，“abc”)并删除(“ab”，1)，我们可以得到下面的trie。注意，父节点可以有值，并且在删除后需要清除所有不必要的节点。

因此，在这里你需要实现三个函数：

• Get(key):获取键对应的值。

• Put(key, value):设置键对应的值。如果键已经存在，则覆盖现有值。注意，值的类型可能是不可复制的(即std::unique_ptr<int>)。这个方法返回一个新的树。

• Delete(key):删除键的值。这个方法返回一个新的树。

这些操作都不应该直接在trie本身上执行。您应该创建新的树节点，并尽可能重用现有的树节点。 要创建一个新节点，您应该使用TrieNode类上的Clone函数。要重用新树中的现有节点，可以复制std::shared_pt<TrieNode>复制共享指针不会复制底层数据。您不应该在此项目中通过使用new和delete手动分配内存。当没有人有对底层对象的引用时，std::shared_ptr将释放对象。

分析：

• 节点类TrieNode使用map<char, std::shared_ptr<const TrieNode>>来存储这种键值结构，，在这里另一个重要的函数是Clone函数（使用了C++类的构造函数的隐式转换)，Clone函数实现新建树中现有节点
• 叶子类TrieNodeWithValue，继承于TrieNode，增加了叶子节点存值功能
• Trie类，内部声明了root（初始为NULL),三个上述待实现的功能

1 实验准备

作业地址

实验当中提供的数据库，其中表关系如下：

索引创建如下：

1
2
3
4
5
6
7
8

CREATE INDEX ix_people_name ON people (name);
CREATE INDEX ix_titles_type ON titles (type);
CREATE INDEX ix_titles_primary_title ON titles (primary_title);
CREATE INDEX ix_titles_original_title ON titles (original_title);
CREATE INDEX ix_akas_title_id ON akas (title_id);
CREATE INDEX ix_akas_title ON akas (title);
CREATE INDEX ix_crew_title_id ON crew (title_id);
CREATE INDEX ix_crew_person_id ON crew (person_id);

2 SQLite3的一些特性

• SQLite3与MySQL的一些不同是一些命另和函数，其数据库的使用直接采用：

  1 2 3

  $ ls imdb-cmudb2022.db placeholder $ sqlite3 imdb-cmudb2022.db

• 查看表：

  1 2	sqlite> .tables akas crew episodes people ratings titles

• 查看表结构

  1 2 3 4 5 6 7 8

  sqlite> .schema people CREATE TABLE people ( person_id VARCHAR PRIMARY KEY, name VARCHAR, born INTEGER, died INTEGER ); CREATE INDEX ix_people_name ON people (name);

• 更大命令使用.help

  1	sqlite> .help

注意，MySQL当中的一些函数，SQLite未必有，就如concat我就发现没有，SQLite使用||替代字符串拼接

3 实验问题

2022 #### 3.1 Q2 [5 points] (q2_sci_fi) Find the 10Sci-Fiworks with the longest runtimes. Details: Print the title of the work, the premiere date, and the runtime. The column listing the runtime should be suffixed with the string " (mins)", for example, if the runtime_mins value is12, you should output 12 (mins). Note a work is Sci-Fi even if it is categorized in multiple genres, as long as Sci-Fi is one of the genres. Your first row should look like this: Cicak-Man 2: Planet Hitam|2008|999 (mins)

找出10个运行时间最长的“科幻”作品。输出其primary_title、primiered、runtime_minutes，其中runtime_minutes后边要接(mins)。

1 2 3 4

SELECT PRIMARY_TITLE,PREMIERED,(RUNTIME_MINUTES||' (mins)' ) FROM TITLES WHERE GENRES LIKE '%Sci-Fi' order by RUNTIME_MINUTES DESC LIMIT 10;

3.2 q3_oldest_people

Determine the oldest people in the dataset who were born in or after 1900. You should assume that a person without a known death year is still alive. Details: Print the name and age of each person. People should be ordered by a compound value of their age and secondly their name in alphabetical order. Return the first 20 results.

Your output should have the format: NAME|AGE

找出出生于1900后（包含1900），年龄最大的20个人，按照年龄年龄和姓名的字母联合排序。注意没有死亡日期，证明还活着，你要能够处理这类数据

1 2 3 4 5 6 7

select name, case when died is null then 2022-born else died-born end as age from people where born>=1900 order by age desc,name limit 20;

2023

3.1 q2_not_the_same_title

Find the 10 Action movies with the newest premiere date whose original title is not the same as its primary title.

Details: Print the premiere year, followed by the two titles in a special format. The column listing the two titles should be in the format of primary_title (original_title) Note a work is Action even if it is categorized in multiple genres, as long as Action is one of the genres. Also note that it's possible for the premiered year to be in the future. If multiple movies premiered in the same year, order them alphabetically. Your first row should look like this:

1
2
3
4
5

SELECT PREMIERED,(PRIMARY_TITLE||' ('||ORIGINAL_TITLE||')') AS T 
FROM TITLES 
WHERE PRIMARY_TITLE!=ORIGINAL_TITLE 
	AND GENRES LIKE '%Action%' 
order by PREMIERED DESC,T LIMIT 10;

3.2 q3_longest_running_tv

Find the top 20 longest running tv series.

Details: Print the title and the years the series has been running for. The series must have a non NULL premiered year. If the ended date is NULL, assume it to be the current year (2023). If multiple tv series have been running the same number of years, order them alphabetically. Print the top 20 results.

Your output should have the format: TITLE|YEARS_RUNNING Your first row should look like this:Looney Tunes|93

1
2
3
4
5
6
7
8
9

SELECT PRIMARY_TITLE,
CASE 
	WHEN ENDED IS NULL THEN 2023-PREMIERED 
	ELSE ENDED-PREMIERED 
END AS YEARS_RUNNING 
FROM TITLES 
WHERE PREMIERED IS NOT NULL 
	AND TYPE='tvSeries' 
ORDER BY YEARS_RUNNING DESC,PRIMARY_TITLE LIMIT 20;

3.3 q4_directors_in_each_decade

List the number directors born in each decade since 1900.(计算自1900年以来每10年出生的导演人数)

Details: Print the decade in a fancier format by constructing a string that looks like this: 1990s. Order the results by decade.

Your output should look like this: DECADE|NUM_DIRECTORS Your first row should look like this: 1900s|376

分析：从事领域存储在crew表的category,其中人的出生时期存储在people表，两表通过person_id联结，people的为主键，crew的为外键

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

SELECT decade || 's',
    COUNT(*)
FROM (
        SELECT DISTINCT(people.person_id),
            FLOOR(people.born / 10) * 10 AS decade
        FROM people
            INNER JOIN crew ON crew.person_id = people.person_id
        WHERE crew.category = 'director'
            AND people.born >= 1900
    )
GROUP BY decade
ORDER BY decade;

上面的group by decade1最重要，这样count()会以decade组区分进行统计

3.4 q5_german_type_ratings

Compute statistics about different type of works that has a German title.(计算具有德语标题的不同类型作品的统计数据。) Details: Compute the average (rounded to 2 decimal places), min, and max rating for each type of work that has a German title and the akas types is either imdbDisplay or original. Sort the output by the average rating of each title type.(计算具有德语标题且akas类型为imdbDisplay或original的每种类型的作品的平均值(舍入到小数点后2位)、最小值和最大值。按每个标题类型的平均评分对输出进行排序。)

Your output should have the format: TITLE_TYPE|AVG_RATING|MIN_RATING|MAX_RATING Your first row should look like this:movie|6.65|3.4|8.2

分析：titles表、akas和ratings表通过title_id进行联结，其中titles中作为主键，akas和ratings作为外键。要求akas.types in ('imdbDisplay','original') and akas.language='de',计算平均值、最大值、最小值。为三表查询

1
2
3
4
5
6
7
8

SELECT T.TYPE, ROUND(AVG(R.RATING),2),MIN(R.RATING),MAX(R.RATING)
FROM TITLES AS T
	INNER JOIN AKAS AS A ON T.TITLE_ID=A.TITLE_ID
	INNER JOIN RATINGS AS R ON T.TITLE_ID=R.TITLE_ID
WHERE A.TYPES IN ('imdbDisplay','original')
	AND A.LANGUAGE='de'
GROUP BY T.TYPE
ORDER BY T.TYPE;

3.5 q6_who_played_a_batman

List the 10 highest rated actors who played a character named "Batman".(请列出出演过“蝙蝠侠”角色的10位评价最高的演员) Details: Calculate the actor rating by taking the average rating of all their works. Return both the name of the actor and their rating and only list the top 10 results in order from highest to lowest rating. Round average rating to the nearest hundredth.(通过取所有作品的平均评分来计算演员的评分。返回演员的名字和他们的评分，并且只按评分从高到低的顺序列出前10个结果。四舍五入平均评级到最接近的百分之一。)

Make sure your output is formatted as follows: Kayd Currier|8.05

分析：name在people表，rating在ratings表，characters在crew表，其中三者的联结依赖主外键，ratings和crew通过title_id联结，crew和people通过person_id联结，要求crew.characters like '%Batman%'。可将people和crew先用person_id进行内连接得到actor,然后利用actor与ratings连接

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

WITH actors AS (
    SELECT DISTINCT(crew.person_id) AS person_id,
        people.name AS person_name
    FROM crew
        INNER JOIN people ON people.person_id = crew.person_id
    WHERE crew.characters LIKE '%"Batman"%'
        AND crew.category = "actor"
)
SELECT a.person_name,
    ROUND(AVG(rating), 2) AS average
FROM actors AS a
    INNER JOIN crew AS c ON c.person_id = a.person_id
    INNER JOIN ratings AS r ON c.title_id = r.title_id
GROUP BY a.person_id
ORDER BY average DESC
LIMIT 10;

上述等价于：

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

SELECT A.name,ROUND(AVG(R.rating),2) AS SCORE
FROM (SELECT DISTINCT(C.person_id),P.name,C.title_id
	FROM crew AS C
	INNER JOIN people AS P ON C.person_id=P.person_id
	WHERE C.characters LIKE '%"Batman"%'
		AND C.category = 'actor'
	) AS A
	INNER JOIN crew AS C ON C.person_id=A.person_id
	INNER JOIN ratings AS R ON C.title_id=R.title_id
GROUP BY A.person_id
ORDER BY SCORE DESC
LIMIT 10;

3.6 q7_born_with_prestige

List the number of actors or actress who were born on the year that "The Prestige" was premiered.(列出在《致命魔术》首映那一年出生的演员人数。) Details: Print only the total number of actors born that year. For this question, determine distinct people by their person_id, not their names. Do not hard code the query.(只打印当年出生的演员总数。对于这个问题，确定不同的人通过他们的person_id，而不是他们的名字。不要硬编码查询。)

分析：born在people表，primary_title在title表，因此需要将crew与people联结起来。加上条件category IN ('actor', 'actress')和primary_title = 'The Prestige'

1
2
3
4
5
6
7
8
9

SELECT COUNT(DISTINCT(p.person_id))
FROM people AS p
    INNER JOIN crew AS c ON p.person_id = c.person_id
WHERE c.category IN ('actor', 'actress')
    AND p.born IN (
        SELECT premiered
        FROM titles
        WHERE primary_title = 'The Prestige'
    );

3.7 q8_directing_rose.sql

Find all the directors who have worked with an actress with first name "Rose".(找出所有与名字为“Rose”的女演员合作过的导演。) Details: Print only the names of the directors in alphabetical order. Each name should only appear once in the output.

分析：category在表crew,name在people

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

WITH title_ids AS (
    SELECT c.title_id AS title_id
    FROM crew AS c
        INNER JOIN people AS p ON p.person_id = c.person_id
    WHERE p.name like 'Rose%'
        AND c.category = 'actress'
)
SELECT DISTINCT(p.name) AS name
FROM title_ids AS t
    INNER JOIN crew AS c ON t.title_id = c.title_id
    INNER JOIN people AS p ON p.person_id = c.person_id
WHERE c.category = 'director'
ORDER BY name;

3.8

1 虚拟内存

一个系统中的进程是与其他进程共享CPU和主存资源的。在之前我们明白一个进程会有4GB的内存，但实际中不可能为一个进程真实的分配这么多，否则对于8G的主存，只要两个进程就占满了。因此，计算机系统的设计者们引入了一中很聪明的做法——虚拟内存。

虚拟内存是硬件异常、硬件地址翻译、主存和磁盘文件和内核软件的完美交互：

1.1 虚拟寻址和地址空间

在计算机中每个字节都存在它唯一的地址，该地址就是物理地址，我们将通过真实物理地址进行寻址的方法称为物理地址。

而虚拟地址，是指由CPU生成一个虚拟地址（VA）来访问主存，如下图，这个虚拟地址在送到内存之前会经过MMU内存管理单元来翻译成物理地址，在这里会结合到后面的页表来进行翻译。通过虚拟地址寻址的方式就是虚拟寻址。现在计算绝大部分都是使用寻你寻址。

地址空间：

• 虚拟地址空间：虚拟地址空间一般以地址总线条数为基准，如32位的位\(2^{32}=4GB\)
• 物理地址空间：对应与实际内存挡住的M字节，一般来说，物理地址空间由进程运行过程中所实际使用的内存大小所决定

物理地址空间和虚拟地址空间是对应关系的，即由虚拟地址找到真实的物理地址。

1.2 虚拟内存是作为缓存的工具

在概念上，虚拟内存是指存放在磁盘上的N字节大小的内存区域，每个字节都要相应的虚拟地址，作物寻址索引。和存储结构的缓存一样，磁盘的数据也被分割成块，在这类为做区别称之为虚拟页，每个虚拟页大小由计算机系统决定为\(P=2^p\)，与之对应的是物理页，其大小也应该为P。

在任何时刻，我们都不能实际真实一股脑的为进程分配全部的存储空间，因此虚拟页面分为三个不相交的子集：

• 未分配的：VM系统还没有分配的页，此时未分配的块没有任何数据和它们管理，因此此时不会占有任何磁盘空间
• 缓存的：当前缓存的虚拟页在占有磁盘中的空间，当然由于缓存到内存。内存当中也会占有一定内存空间
• 维缓存的：在磁盘中占用空间，但并未缓存在内存中，当然不占用内存(此时当CPU要寻址该页当中一个数据时，由于未缓存在内存中，就会造成缺页异常。)

1 异常控制流

现代系统通过使控制流发生突变来对这些情况做出反应，我们把这些突变称为异常控制流(ECF)。

• 在硬件层，硬件检测到的事件会触发控制突然转移到异常处理程序；
• 在操作系统层，内核通过上下文切换将控制从一个用户进程转移到另一个用户进程；
• 在应用层，一个进程可发发送信号到另一个进程，而接受者会将控制突然转移到它的一个信号处理程序。

作为程序员，理解ECF很重要：

1 操作系统的基本概念

1. 操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
2. 操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬件和软件资源。 举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。
3. 操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。
4. 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。 内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

操作系统的内核（Kernel）

维基百科对于内核的解释： >内核（英语：Kernel，又称核心）在计算机科学中是一个用来管理软件发出的数据 I/O（输入与输出）要求的电脑程序，将这些要求转译为数据处理的指令并交由中央处理器（CPU）及电脑中其他电子组件进行处理，是现代操作系统中最基本的部分。它是为众多应用程序提供对计算机硬件的安全访问的一部分软件，这种访问是有限的，并由内核决定一个程序在什么时候对某部分硬件操作多长时间。 直接对硬件操作是非常复杂的。所以内核通常提供一种硬件抽象的方法，来完成这些操作。有了这个，通过进程间通信机制及系统调用，应用进程可间接控制所需的硬件资源（特别是处理器及 IO 设备）。

早期计算机系统的设计中，还没有操作系统的内核这个概念。随着计算机系统的发展，操作系统内核的概念才渐渐明晰起来了!

简单概括两点：

• 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。
• 操作系统的内核是连接应用程序和硬件的桥梁，决定着操作系统的性能和稳定性。

中央处理器（CPU，Central Processing Unit）

关于 CPU 简单概括三点：

• CPU 是一台计算机的运算核心（Core）+控制核心（ Control Unit），可以称得上是计算机的大脑。
• ** CPU 主要包括两个部分：控制器+运算器。**
• CPU 的根本任务就是执行指令，对计算机来说最终都是一串由“0”和“1”组成的序列。

CPU vs Kernel(内核)

可以简单从下面两点来区别：

• 操作系统的内核（Kernel）属于操作系统层面，而 CPU 属于硬件。
• CPU 主要提供运算，处理各种指令的能力。内核（Kernel）主要负责系统管理比如内存管理，它屏蔽了对硬件的操作。

2 操作系统的基本特性

操作系统的基本特性是并发性、共享性、虚拟性、异步性。

并发性

并行性和并发性(Concurrence)是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。（宏观并发微观串行）

并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统

操作系统通过引入进程和线程，使得程序能够并发运行。

共享性

指系统中的资源可供内存中多个并发执行的进程(线程)共同使用，相应地，把这种资源共同使用称为资源共享，或称为资源复用。目前主要实现资源共享的方式有：

• 互斥共享方式
• 同时访问方式

互斥共享方式

当一个进程 A 要访问某资源时，必须先提出请求。如果此时该资源空闲，系统便可将之分配给请求进程 A 使用。此后若再有其它进程也要访问该资源时(只要 A 未用完)，则必须等待。仅当 A 进程访问完并释放该资源后，才允许另一进程对该资源进行访问。我们把这种资源共享方式称为互斥式共享，而把在一段时间内只允许一个进程访问的资源称为临界资源或独占资源，例如打印机。

同时访问方式

系统中还有另一类资源，允许在一段时间内由多个进程“同时”对它们进行访问。这里所谓的“同时”，在单处理机环境下往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问。典型的可供多个进程“同时”访问的资源是磁盘设备，一些用重入码编写的文件也可以被“同时”共享，即若干个用户同时访问该文件。

虚拟性

虚拟技术把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

异步性

在多道程序环境下允许多个进程并发执行，但只有进程在获得所需的资源后方能执行。在单处理机环境下，由于系统中只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。进程是以人们不可预知的速度向前推进，此即进程的异步性。

3 操作系统的基本功能

操作系统的基本功能包括进程管理、内存管理、文件管理、设备管理。

• 进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度等
• 内存管理：内存分配、地址映射、内存保护与共享、虚拟内存等
• 文件管理：文件存储空间的管理、目录管理、文件读写管理和保护等
• 设备管理：完成用户I/O请求，方便用户使用各种设备，并提高设备的利用率，主要包括缓冲管理、设备管理、设备处理、虚拟设备等。

4 什么是系统调用/用户态和系统态是？

根据进程访问资源的特点，可以把进程在系统上的运行分为两个级别：

• ** 用户态(user mode) **: 用户态运行的进程或程序可以直接读取用户程序的数据。
• 系统态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

我们运行的程序基本都是运行在用户态，如果要调用操作系统提供的系统态级别的子功能，那就需要系统调用了！

也就是说在运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

这些系统调用按功能大致可分为如下几类：

• 设备管理。完成设备的请求或释放，以及设备启动等功能。
• 文件管理。完成文件的读、写、创建及删除等功能。
• 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
• 进程通信。完成进程之间的消息传递或信号传递等功能。
• 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

为什么要有用户态与内核态?

在 cpu 的所有指令中，有些指令是非常危险的，如果使用不当，将会造成系统崩溃等后果。为了避免这种情况发生，cpu 将指令划分为特权级(内核态)指令和非特权级(用户态)指令。

对于那些危险的指令只允许内核及其相关模块调用，对于那些不会造成危险的指令，就允许用户应用程序调用。

• 内核态(核心态,特权态): 内核态是操作系统内核运行的模式。 内核态控制计算机的硬件资源，如硬件设备，文件系统等等，并为上层应用程序提供执行环境。
• 用户态: 用户态是用户应用程序运行的状态。 应用程序必须依托于内核态运行,因此用户态的操作权限比内核态是要低的，如磁盘，文件等，访问操作都是受限的。
• 系统调用: 系统调用是操作系统为应用程序提供能够访问到内核态的资源的接口。

用户态切换到内核态的几种方式

• 系统调用: 系统调用是用户态主动要求切换到内核态的一种方式，用户应用程序通过操作系统调用内核为上层应用程序开放的接口来执行程序。
• 异常: 当 cpu 在执行用户态的应用程序时，发生了某些不可知的异常。于是当前用户态的应用进程切换到处理此异常的内核的程序中去。
• 硬件设备的中断: 当硬件设备完成用户请求后，会向 cpu 发出相应的中断信号，这时 cpu 会暂停执行下一条即将要执行的指令，转而去执行与中断信号对应的应用程序，如果先前执行的指令是用户态下程序的指令，那么这个转换过程也是用户态到内核台的转换。

5 计算机的局部性原理

一个编写良好的计算机程序常常具有良好的局部性，即他们更加倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用或的数据项本身，这种特性，常常称为局部性原理。局部性由两种不同的形式：时间局部性和空间局部性

• 时间局部性：被引用过一次的内存位置很有可能在不久的将来再次被多次引用。
• 空间局部性：一个内存被引用过了，那么极有可能在不久的将来会引用器附近的内存位置。在高速缓存中的表现形式是以数据块的形式进行缓存，弥补未命中时的惩罚

我们应该理解局部性原理，因为一般而言，一个良好局部性的程序比局部性差的程序运行得更快，这是由现代计算机系统得设计结构所决定得，在现代计算系统得各个层次之哦你给，都引入了局部性原理：

• 在硬件层，计算机设计者通过引入称为高速缓存存储器这样小而快得快速存储器来保存最近引用得指令和数据项，从而提高对主存得访问速度。
• 在操作系统中，系统使用主存作为虚拟地址空间，来存储最近被引用得数据项，来避免因从磁盘取数据过慢而导致CPU资源的浪费
• 类似的，用主存来缓存磁盘文件中最近被使用的磁盘块。
• 局部性原理在应用程序中也有应用，入Web浏览器将最近引用的文档放在本地磁盘上，利用的就是时间局部性。

1 链接器

1.1 链接是什么

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载到内存并执行。

• 链接可以执行与编译时，也就是源代码被翻译成机器代码时；
• 也可以执行与加载时，也就是在程序被加载器（loader)加载带内存并执行时
• 甚至也可执行于运行时，也就是有程序来执行

链接器在开发中是一个关键角色，因为它使得分离编译成为可能，我们不用将一个大型的应用程序组织为一个巨大的源文件，而是可以分解成更小、更好管理的模块。可以单独修改和编译这些模块。理解链接有以下的好处：

• 理解链接器将帮助你构造大型程序。构造大型程序的程序员经常会遇到缺少模块、库或者不兼容版本引起的链接器错误，当你理解了链接器如何解析引用、什么是库以及链接器是如何使用库来解析引用时，你就能够较好的解决这类问题

• 理解链接器将帮助你避免一些危险的编程错误。Linux链接器解析引用时所做的决定可以不动声色影响你程序的正确性。在默认情况下，错误的定义多个全局变量的程序将通过链接器，而不产生任何警告信息。

• 理解链接器将帮助你理解语言的作用域规则是如何实现的。全局变量和局部变量、static变量和static函数，在低层到底有何区别？

• 理解链接器帮助你理解其他重要系统概念。链接器产生的可执行目标文件咋子系统功能中扮演关键角色，如加载运行程序、虚拟内存、分页、内存映射。

• 理解链接器将使你能够利用共享库。共享库和动态链接在现代操作系统日益重要，掌握如何动态链接原理极其重要。