INGNIGHT的专栏

原创 Google Perf Tools安装以及使用

Google Performance Tools安装以及使用这边文章都记录在github：https://github.com/NIGHTFIGHTING/gperftools-tutorial一个优化的内存管理算法—tcmalloc性能优于malloc。一个用于CPU profile的工具，用于检测程序的性能热点，这个功能和gprof类似。一个用于堆检查工具，用于检测程序在是够有内存泄露...

原创 12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？归并排序和快速排序

下载APP。

原创 数据库不用mmap

但是当操作系统检索页面的时候，他会意识到内存中没有关联的物理页面，所以它需要触发一个页面错误才能从磁盘上获取它，然后OS向页面添加物理地址映射到虚拟地址的条目，映射也将被存储在称为转译后备缓冲区或TLB的特殊cpu缓存中，这将有助于加速未来的重复访问，所以我们不总是在页表中进行查找内容。其次是同步页表的开销，以及高竞争下关联的数据结构（本例中100个并发线程），TLB shootdowns（TLB缓存存储的是CPU中的页表条目），当页边被逐出时，这些条目需要删除，这需要昂贵的处理器间中断。

原创 brpc基于延迟最大并发度限流

server.cppglobal.cpp。

原创 tfs文件系统

tfs主从nameserver节点容错性—源码解读。tfs数据复制策略—源码解读。

原创 boost::intrusive_ptr的用法

链接：https://www.jianshu.com/p/dd9701219b27。商业转载请联系作者获得授权，非商业转载请注明出处。作者：JasonLiThirty。

原创 brpc负载均衡load balance和服务发现name servicing

2.2.3nsthread->Start，bthread_start_urgent创建一个协程RunThis->Run->_ns->RunNamingService。3.Channel：包含LoadBalancerWithNaming的指针_lb，new LoadBalancerWithNaming，lb->Init。1.SharedLoadBalancer（load_balancer.h）：包含LoadBalancer指针_lb。

原创 1359 · 有序数组转换为二叉搜索树

【代码】1359 · 有序数组转换为二叉搜索树。

原创 内存-虚拟地址到物理内存地址转换

512个2MB是1GB，第二层，每一项是512GB。512个4KB是2MB，第一层，每一项是1GB。512个526GB是256TB，第三层，每一项。第零层，每一项是4KB。

原创 阻塞、非阻塞、异步、同步

但当IO并发度愈发提高时，blocking IO阻塞一个线程的弊端便显露出来：内核得不停地在线程间切换才能完成有效的工作，一个cpu core上可能只做了一点点事情，就马上又换成了另一个线程，cpu cache没得到充分利用，另外大量的线程会使得依赖thread-local加速的代码性能明显下降，如tcmalloc，一旦malloc变慢，程序整体性能往往也会随之下降。内核把数据准备好了之后，它也是通过read返回的，read一返回，其实也就意味着数据是否准备好。

原创 复杂链式结构：跳表

原创 187. 重复的DNA序列

链接：187. 重复的DNA序列题解：

原创 1392. 最长快乐前缀

【代码】1392. 最长快乐前缀。

原创 1147. 段式回文

【代码】1147. 段式回文。

原创 将二叉搜索树转化为排序的双向链表

【代码】将二叉搜索树转化为排序的双向链表。

原创 面试题 17.24. 最大子矩阵

链接：https://leetcode.cn/problems/max-submatrix-lcci/solutions/137568/zhe-yao-cong-zui-da-zi-xu-he-shuo-qi-you-jian-dao-/我们以第i行为第一行，向下延申，设最后一行为第j行，我们就i在这么一个范围内，将二维问题转化为一维问题，再求解最大子序列和。这样我们就将二维问题转化为了一维问题，现在另一个问题就是怎么把所有情况都遍历到呢？作者：bugsmaker。

原创 540. 有序数组中的单一元素

如果 mid\textit{mid}mid 是奇数，则比较 nums[mid−1]\textit{nums}[\textit{mid} - 1]nums[mid−1] 和 nums[mid]\textit{nums}[\textit{mid}]nums[mid] 是否相等。因此在二分查找的过程中，不需要判断 mid\textit{mid}mid 的奇偶性，mid\textit{mid}mid 和 mid⊕1\textit{mid} \oplus 1mid⊕1 即为每次需要比较元素的两个下标。

原创 vector实现

【代码】vector实现。

原创 tcp拥塞控制原理

我们在向对端发送数据时，并不是一股脑子任意发送，因为TCP建立连接后，就是建立了一根管道，这跟管道上，实际上有很多的工作设备，比如路由器和交换机等等，他们都会对接收到的TCP包进行缓存，以便实现排序，然后发送，但是这些设备并不是只为一个TCP连接中转数据包，大量的网络包也许会耗尽存储空间，从而导致TCP连接的吞吐量急剧下降。

原创 tcp滑动窗口原理

另外，你需要知道网络上有个MTU，对于以太网来说，MTU是1500字节，除去TCP+IP头的40个字节，真正的数据传输可以有1460，这就是所谓的MSS（Max Segment Size）注意，TCP的RFC定义这个MSS的默认值是536，这是因为 RFC 791里说了任何一个IP设备都得最少接收576尺寸的大小（实际上来说576是拨号的网络的MTU，而576减去IP头的20个字节就是536）。要知道，我们的TCP+IP头有40个字节，为了几个字节，要达上这么大的开销，这太不经济了。

原创 string cow方法实现

【代码】string cow方法实现。

原创 752. 打开转盘锁

【代码】752. 打开转盘锁。

原创 index倒排拉链的查询和merge

2.2.1找到不小于doc_id的doc_id后，判断下找到的doc_id和token[0]的doc_id是否匹配，如果不匹配则将该doc_id设置为next_doc_id。2.2.2如果next_doc_id存在则将token[0]的doc_id调整到不小于next_doc_id的位置。2.2如果所有的token的都存在和token[0]相等的doc_id，则该doc_id符合求交接。2.按照token[0]的倒排拉链进行便利，先使用第一个token[0]的第一个doc_id，

原创 06-数据库检索：如何使用B-树对海量磁盘数据建立索引？

你好，我是陈东。在基础篇中，我们学习了许多和检索相关的数据结构和技术。但是在大规模的数据环境下，这些技术的应用往往会遇到一些问题，比如说，无法将数据全部加载进内存。再比如说，无法支持索引的高效实时更新。而且，对于复杂的系统和业务场景，我们往往需要对基础的检索技术进行组合和升级。这就需要我们对实际的业务问题和解决方案十分了解。所以，从这一讲开始，我会和你一起探讨实际工作中的系统和业务问题，分享给你一些工业界中常见的解决方案，帮助你积累对应的行业经验，让你能够解决工作中的检索难题。

原创 496. 下一个更大元素 I

【代码】496. 下一个更大元素 I。

原创 Log日志库

【代码】Log日志库。

原创 400. 第 N 位数字

【代码】400. 第 N 位数字。

原创 670. 最大交换

【代码】670. 最大交换。

原创 13. 罗马数字转整数

【代码】13. 罗马数字转整数。

原创 12. 整数转罗马数字

【代码】12. 整数转罗马数字。

原创 96. 不同的二叉搜索树

【代码】96. 不同的二叉搜索树。

原创 402. 移掉 K 位数字

【代码】402. 移掉 K 位数字。

原创 复习leetcode

​​​​​​460. LFU 缓存31. 下一个排列322. 零钱兑换力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

原创 圆环回原点问题

【代码】圆环回原点问题。

原创 1268. 搜索推荐系统

【代码】1268. 搜索推荐系统。

原创 1339. 分裂二叉树的最大乘积

【代码】1339. 分裂二叉树的最大乘积。

原创 malloc Memory Allocators 101 - Write a simple memory allocator

【代码】Memory Allocators 101 - Write a simple memory allocator。

原创 1269. 停在原地的方案数

题解：坐标型动态规划。

原创 cpu和net和disk命令查询

w可以查看上下文切换（主动切换，不主动切换：上下文切换：进程间切换[包括内核栈，寄存器，虚拟内存的保存和恢复]，线程间切换，影响：频繁切换影响，cpu的TLB缓存被更新，CPU缓存命中率变低）。vmstat 1 1，可以查看系统上下文切换情况（查看cpu，内存（剩余内存，系统缓存磁盘/文件，swap换入/唤出速度），cpu的idl，以及等待io使用率iowait）mpstat 1 1或者mpstat -P ALL查看每个cpu使用状态，（用户态cpu是用来，内核态cpu使用率，等待IO使用率）

原创 内存池/对象池设计与实现

2.栈，使用最近归还的对象，进行对象池对象分配。1.new 重载placement new。3.静态对象需要在类外进行初始化。