Blooooog~

问题描述如下图所示，长度为k的滑动窗口在数组中从左往右移动，求出在移动过程中，窗口中的最大值的集合。(窗口的长度不长于数组长度) 初步解法——使用优先队列考虑示例中的nums[1]，显然可知的是，nums[1]作为最大值的有效窗口只能是区间[0, 2]和[1, 3]，一旦某个时刻的窗口起始位置大于了最大值x的位置，那么x就不再有效了。 由于最大值的判定和位置十分相关，所以我们在记录最大值的时候，也很有必要将它的位置一并记录下来，如下所示： 1using Pir = pair<int, int>; // <元素值，元素位置> 接下来就是思考有哪些数据结构可以在低于线性复杂度的情况下找到最值。优先队列就是其中的一种。重点来了，本题适合选用优先队列的原因就在于：对于固定的一个最值x，其服务的窗口区间仅仅是离他最近的那些区间。倘若在某一个时刻我们发现，当前的窗口区间对于最值x已经不再有效，那么对于之后时刻的窗口区间更加不会有效。故之前将其舍弃即可。 讲到这里，优先队列的解法也就很明了了。 123456789101112131415161718192021class ...

问题描述如图所示的仅包含 0，1 元素的二维数组，找出最大的矩形面积。矩形需要满足：内部元素全为 1 (图中的最大矩形面积显然为 6) 问题分析先将问题转化为这样一个问题：柱状图的最大矩阵面积，如下图示意。显然，对于该图而言，最大矩形面积为 10 如何解决柱状图的最大矩形面积问题呢？我们需要从图中找到规律。 首先可以明确：最大矩形面积肯定不小于每个柱体的面积，因此，我们先找到一个方法去计算最大柱体的面积。最简单的方法肯定就是直接去遍历柱体的高度呗。但这样不具有普遍性，因为对于柱体连接之后所构成的更大的矩形，就不能用这种方法去计算了。 还是以该图举例。对于柱体 6，我们发现其两旁的柱体都低于 6，因此对于该柱体的面积，就等于两边柱体的距离(柱体 5 和柱体 2 的距离)乘以该柱体的高度。 可这个方法对于柱体 5 而言呢？其两旁比它低的柱体分别是柱体 1 和柱体 2，按照这个方法算出来恰好就是我们想要的答案 10！ 我们需要一个理由和理解来对这个方法进行支撑。思考之后，给出这样的断言： 计算一个柱状图的最大矩形面积，等价于柱状图的宽度乘以柱状图中最低的柱体 可能有人会问了，拿上图来举例， ...

注：本文为阅读《Linux 多线程服务端编程：使用 muduo C++网络库》的一点笔记 空闲连接指的是一段时间内没有受到任何数据的连接。我们需要做的是每隔一段时间断开这些空闲连接，以免浪费资源。剔除空闲连接这一任务大概有如下两个特点和需求： 无需精准定时：只需要一个大致的间隔，比如说 10s 左右未受到数据，则判定其为空闲连接 应尽量简单：剔除空闲连接应该是一个简洁明了的操作，不应占据太多的计算或空间资源 time wheel 运用了桶排序的思路，在系统中设置 N 个桶，共同组成一个队列。第 i 个桶中存放 i 秒后将要变为空闲连接的连接。这样一来，我们只需要每秒剔除第 0 个桶中的连接即可，无需遍历全部连接，剔除之后，将第 0 个桶移动到尾部。而一个连接如果接收到了新数据，那么该连接就将自己重新放入最后一个桶中。 接下来，我先用自己的语言描述一下书中作者所使用的数据结构： 桶中存放TcpConnection？: 我们在断掉连接之前还需要判断其是否还处于连接状态，结合 RAII 技术，使用using Entry = std::weak_ptr<TcpConnection& ...

前言 - std::chrono 的用法三种主要类型 clocks: 包括一个起始点(epoch)以及一个变动率(tick rate) time point: 自特定 clock 的 epoch 之后经过的 duration duration: 指时间跨度，包括衡量跨度的时间单位以及有多少个单位(count of ticks) 关于 clock 的用法 steady_clock和system_clock的区别： 前者绝对单调，不可调整；后者基于真实系统时钟，不一定单调； 前者更适合测量 time interval；后者是唯一可以转换为 c-style time(std::time_t)的 clock 类型； 使用 clock 记录时间点以及函数执行用时不同的时钟类型都拥有一个函数now()来指示当前的时刻 123456789101112131415161718192021// 使用std::chrono库记录函数执行用时#include <chrono>#include <iostream>using namespace std::chrono;in ...

让我坚定使用using而不是typedef进行类型声明的原因，除了因为它是新标准以外，更重要的就是using的模板声明能力。 首先考虑如下一个类中的各个回调函数的形式声明。可以看到，声明中多次使用了冗余的std::function。虽然使用的是using，但并没有体现出using的优势。 123456789101112131415class TcpConnectionPtr;class TcpConnection : // noncopyable public std::enable_shared_from_this<TcpConnection>{ // kDisconnecting - LIKE POLLRDHUP, the write endian is closed enum StateEnum {kConnecting, kConnected, kDisconnecting, kDisconnected}; using ConnectionCallback = std::function<void (const TcpCo ...

如何实现一个网络库的多线程机制？实际上，并不需要各种繁杂的锁机制。先用一句话来阐述核心思想：以函数执行线程的转移作为实现线程安全的机制。具体来说，分为如下几点： one loop per thread : 其中的每个线程均和一个独立的 EventLoop 关联 EventLoopThreadPool : 线程池，从池中取出一个新的线程，等价于取出一个新的 EventLoop 线程安全性 : 通过EventLoop::runInLoop()函数，使得函数的执行能够在线程间进行转移 线程切换：整个流程中，线程切换仅发生在 Connection 建立和 Connection 删除这两个步骤中，其余的阶段都为单线程执行 新建 Connection：Server 所在线程负责新建连接，随后利用EventLoop::runInLoop()将新连接的控制权转移到线程池中的 IO 线程； 删除 Connection：由于 Server 中保存有 Connection 的副本，因此需要将删除 Connection 的操作转移到 Server 所在线程，方式还是利用EventLoop::runInLoo ...

C++标准库中的底层同步原语。理解std::condition_variable，着重就在于理解std::condition_variable::wait()这个函数，签名为void(std::unique_lock<std::mutex>& lk, Predicate pred)，Predicate代表谓词。 wait 的作用一句话解释：阻塞当前线程，直至被其他线程通过notify_all()或者notify_one()唤醒，并且满足谓词条件。notify*()也是std::condition_variable的成员函数。 如何调用线程在调用`wait()`之前必须先获得锁，也就是说，必须是如下所示配套的调用： 12345std::condition_variable cv;std::mutex mutex_;std::unique_lock<std::mutex> lk(mutex_); // 争取获得锁cond.wait(lk, []{/*谓词*/}); // OK, 已经获得锁了，可以开始wait 内部流程如图 1 所示。 ...

注：本文为阅读 muduo 网络库源码 Buffer 部分的体悟 本文中 Buffer 一词均指代 muduo 网络库的 class Buffer。 为非阻塞网络库设计一个合理的缓冲区机制是很重要的一环1。muduo 网络库源码中的 Buffer 部分中，我觉得最能体现精华的就是关于设计缓冲区大小这一部分，其核心就是下方所贴出的ssize_t Buffer::readFd(int fd, int *savedErrno)函数，其作用是读取fd指示的对端发来的数据，并保存于内部的vector<char> buf_变量中。下面就是对这一函数体现的设计思路的解析。 如何为每个 TCP 连接分配合理大小的缓冲区呢？如果太大，那么当 TCP 连接数增多之后，内存必然负担过大；而如果过小，那么会增加系统调用(::read(), ::write())的次数，时间开销陡增。作者给出的方案很巧妙，即使用分散/聚集 IO，也称为向量 IO。 初始时，Buffer 的内置缓冲vector<char> buf_的初始大小其实很小，在源码中仅设置为 1K 字节。但在进行::readv() ...

注：本文为研究 muduo 源码库之后的理解和代码实战 TcpServerTcpConnection 和 TcpServer 是紧密相连的，因为 connection 就是由 server 进行创建得到。因此，在阐述 TcpConnection 的实现细节之前，我们先思考一下 TcpServer 的一些重点。 TcpServer 是 Acceptor 的唯一使用者在之前关于 Acceptor 的文章之中，我们已经阐述了 Acceptor 的详细细节和原理。TcpServer 是 Acceptor 的唯一使用者，或者说是唯一拥有者。Acceptor 在探测到连接请求并使用::accept()成功创建了对端 socket 和网络地址之后，执行的 user callback 就是来自 TcpServer 的 callback。Acceptor 仅为 TcpServer 服务。 callback 的具体流程思考一下 TcpServer 在收到了对端 socket 和网络地址之后，应该做些什么。其实很简单，一句话概括便是：创建对应 TcpConnection，并在其中注册网络库实际用户的回调 ...

注：本文为阅读 muduo 源码库和作者著作之后的网络库复现和笔记 在传统的 IO 多路复用系统中，定时操作通常是直接去设置poll()等函数的超时时间，系统超时之后去执行对应的定时回调。但现代 Linux 系统已经将时间也抽象为了一种事件，并提供了对应的文件描述符fd机制，其能够被poll()等多路复用函数进行监视，因此可以很简洁地融入到我们之前实现的 Reactor 机制中。这也是更科学的做法。 底层 API int timerfd_create(int clockid, int flags)根据用户指定的标识符生成 timer，并返回对应的fd。clockid设置时钟的类型，flags则是设置fd的各个标志位，比如是否阻塞等等。 int timerfd_settime(int fd, int flags, const struct itimerspec *new_value, struct itimerspec *old_value)通过new_value去设定 timer 的超时时间（expiration time）以及是否重复（repeat via same iterval ...