- 博客(59)
- 收藏
- 关注
RSS订阅原创 NP完全问题与例题
一个算法的运行时间是输入规模nnn的某个多项式函数，就称这个算法的时间复杂度是“多项式时间”。形式上：如果一个算法的运行时间是OnkO(n^k)Onk，其中kkk是某个常数，那么我们说它是“多项式时间算法”。
2025-04-09 11:30:41
964
原创 广告基础知识总结
随着技术的进步，这种竞价机制变成了实时的（在100ms内完成），即针对某个新的pv，供应方平台将广告位置和用户属性发送给Ad Exchange平台，然后后者将其发送给所有接入的广告主，然后系统开始实时出价，价高者得。GD广告即Guaranteed Delivery广告，也叫保证交付量广告，担保式保量投放，广告主与广告平台或者媒体签订合同，明确广告投放的位置、时间、数量等。外循环的好处是品牌或商家可以拥有更大的自由度，掌控更多数据，建立自己的私域流量池，但因为用户离开平台，复购和留存的可控性较弱。
2025-03-05 15:58:15
979
原创 clean code阅读笔记——如何命名？
有个词叫做”以小见大“。以建筑作喻，宏大建筑中最细小的部分，比如关不紧的门、未铺平的地板，甚至时凌乱的桌面，都会将整个大局的魅力毁灭殆尽，这就是整洁代码之所系。
2025-01-27 14:53:00
1136
原创 linux网络编程11——线程池
这是一个非常基础的线程池，没有尝试使用无锁编程。线程池关闭可能被无限延迟（关闭一般是在程序结束运行时，所以一般问题不大）。另外对于任务类型，设计的也比较简单，没有考虑future和promise等，这个可以留给用户提供的task去自定义。
2025-01-20 00:29:06
1042
原创 基于异步IO的io_uring
io_uring使用了一种异步IO机制，它通过一对环形缓冲区(ring buffer)实现用户态于内核态之间的高效通信，用户只需将IO请求放入提交队列，当内核完成IO请求时，会将结果放入完成队列，然后用户从完成队列中提取结果并进行后序处理。io_uring中的两个队列是映射到用户态的共享内存区域，用户态和内核态可以直接通过这个区域交换数据，减少了系统调用上下文切换。用户也可以一次性提交多个IO请求，减少了系统调用次数。
2025-01-12 20:58:22
761
原创 spdlog高性能日志系统
`spdlog` 是一个快速、简单、功能丰富的 C++ 日志库，专为现代 C++ 开发设计。它支持多种日志后端（如控制台、文件、syslog 等），并提供灵活的格式化和线程安全的日志输出。
2024-12-10 23:43:18
1267
1
原创 Redis4——持久化与集群
本文讲述了1.redis在内存占用达到限制后的key值淘汰策略；2.redis主从复制原理；3.redis的哨兵模式；4.redis集群模式。
2024-12-04 18:18:18
1243
原创 Redis2——协议与异步方式
本文讲述了Redis pipeline技术，它被用于一次发送和执行多个命令；事务的ACID特性，Redis只能部分满足；最后介绍了实现了Redis客户端的同步连接和异步连接方式。
2024-11-28 21:16:12
846
原创 MySQL4——缓存策略
本文讲述了Mysql缓存方案的原理、其它改进方案、缓存读写策略、缓存一致性的分析与实现，数据增量同步的实现方式：伪装从库、udf+触发器。最后还分析了该缓存方案可能出现的故障及解决方案，以及其弊端。
2024-11-25 18:46:03
862
原创 linux网络编程10——内存池
本文讲述了内存池的概念、原理、好处，并且实现了两种类型的内存池：固定大小的内存池和分级内存池。最后分别对这两种内存进行了性能测试，测试结果表明，在简单的频繁分配和释放动态内存块的场景下，这两种内存池至少能够提高一倍的性能。
2024-11-18 16:50:12
1142
原创 高级数据结构——hash表与布隆过滤器
本文讲述了hash表的原理与实现、hash冲突及解决方法、基于位图和hash函数实现的布隆过滤器、以及用于负载均衡的分布式一致性hash等。
2024-11-16 20:29:36
1258
原创 linux网络编程8——原子操作CAS与锁实现
本文讲述了原子操作的原理、缓存一致性协议MESI、和原子操作的6种内存序，最后利用原子变量和内存序实现了一个自旋锁。
2024-11-12 17:19:25
865
原创 高级数据结构——跳表skiplist
跳表是redis采用的实现有序集合的数据结构之一, 具有查询效率高和实现相对简单的优势。本文介绍了跳表的原理和代码实现，参考的是《redis5设计与源码分析》这本书。
2024-11-08 00:00:15
898
原创 算法详解——链表的归并排序非递归解法
本文使用倍增法加上归并排序操作实现了对链表的快速排序，比起一般的递归式归并排序要节省空间并且实现要简单的多，比起一般的迭代式归并排序实现也要简单。
2024-11-07 16:14:01
1249
原创 算法详解——线段树
线段树是一个高度平衡二叉树，它主要用来高效动态地管理一个序列。线段树叶子结点存储序列元素值，分支结点存储一个连续地子区间的某种聚合信息，例如最值、均值等信息。
2024-10-31 13:02:09
1212
原创 linux网络编程6——基于UDP的可靠传输协议KCP/QUIC
本文详细介绍了KCP协议基本原理，并简要介绍了KCP的使用方式以及QUIC协议。
2024-10-26 18:08:10
1554
原创 linux网络编程5——Posix API和网络协议栈，使用TCP实现P2P通信
本文介绍了linux Posix API涉及网络编程的常用函数，并解释其原理和涉及的网络协议栈。最后，利用TCP三次握手中同时打开建立连接的情况实现了P2P通信。
2024-10-25 13:26:57
1309
1
原创 linux网络编程4——WebSocket协议及服务器的简易实现
本文详细介绍了WebSocket协议的特点、与HTTP的区别以及应用场景；然后分析了WebSocket协议的主要内容；最后借助前面的底层reactor的代码实现了一个WebSocket协议的Web服务器。
2024-10-23 13:52:10
1590
原创 linux网络编程3——http服务器的实现和性能测试
是一款针对 Http 协议的基准测试工具，它能够在单机多核 CPU 的条件下，使用系统自带的高性能 I/O 机制，如 epoll，kqueue 等，通过多线程和事件模式，对目标机器产生大量的负载。可以在连接中保存一个status字段，表示当前连接的状态，当status为0，表示还没有发送任何信息，为1表示已经发送了头部，正在发送文件块，为2表示已经全部发送完毕。缺点是，由于不经过用户空间，无法对文件分块发送，在阻塞IO模式下发送大文件可能长时间陷入阻塞。ET 只在状态变化的那一刻通知，不会持续通知。
2024-10-22 22:12:43
932
原创 linux网络编程2——reator事件处理模型及服务器百万并发的实现
在阻塞IO模式下，发送缓冲区爆满会导致send函数陷入阻塞，直接导致连接增长停止。在非阻塞IO模式下send函数会直接返回-1，这可能导致短时间内频繁系统调用上下文切换，从而导致cpu占用提升，连接增长变缓慢。例如当.bss段大于4GB时，采用相对引用的话，其与代码段的偏移可能超过32为地址所能表示的范围，因此需要改用更大的代码模型。由于客户端也需要为每一个连接在本地分配一个端口，如果用于测试的客户端针对同一个远程ip和端口建立的连接太多，会导致客户端端口不足。可以尝试扩大TCP缓冲区，在。
2024-10-22 17:07:29
392
原创 linux网络编程1——IO管理（select/poll/epoll)
以上讲的IO多路复用关注的都是IO事件的管理，epoll对于大量并发连接的场景性能很好，poll适用于IO连接很少的时候，select的可移植性强。IO事件管理任何网络应用程序都需要的，与业务层无关。
2024-10-22 17:06:05
1002
原创 linux链接、目标文件全解析
在编译时，编译器向汇编器输出每个全局符号，要么是强，要么是弱，汇编器会把强弱信息隐含在符号表中。所谓强符号，是指函数和已初始化的全局符号，而弱符号就是未初始化的全局变量。请牢记定义。规则1：不允许有多个同名的强符号。规则2：如果有一个强符号和多个弱符号同名，那么选择强符号。规则3：如果有多个弱符号同名，那么从这些弱符号中任意选择一个。// 强符号int y = 12;// 强符号int main()f();return 0;
2024-10-22 16:59:23
1089
原创 设计模式基础知识以及典型设计模式总结（上）
设计模式是指在软件开发中，经过验证的，用于解决在特定环境下重复出现的特定问题的解决方案。简单的说，设计模式是解决问题的固定套路。慎用设计模式。在父类中定义处理流程的框架，在子类中实现具体处理的模式。模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特性。定义了对象间的一种一对多的依赖关系，当一个对象（subject）的状态发生变化时，所有依赖于他的对象（Observers）都得到通知，并自动更新。本质是“触发联动”。 **定义一系列算法，把他们一个个封装起来，并使其可相互替换。
2024-10-22 16:45:28
995
原创 算法题：所有可能的真二叉树
另一种是策略是：每次都从当前结点选择其左右子树结点的数量，如果需要从当前结点开始构建一个n个结点的真二叉树，那么左右子树的结点总数为n-1，左右子树的结点数量也都为奇数，因此可以将左子树的结点数量从1开始每次加2进行遍历，这样就可以枚举出所有情况。当n==1时就可以结束递归。一种策略是：每次都从度为0的结点中选择一个，给它填充左右子结点。但是这样会导致最终答案重复。首先能想到用递归来构建每一种可能的情况。那么每次递归时应该怎样进行选择呢？由题可得，真二叉数的结点数量必定为奇数。
2024-04-02 17:00:38
367
原创 算法题：子树的大小
子节点的个数就是$ rchild - lchild$。要算出子树的结点总数，可以从k结点出发，将各层子节点数量相加，直到rchild > n，此时如果lchild > n则最后一层没有子节点，否则最后再加上lchild - n + 1。个结点的完全二叉树，结点按从根到叶、从左到右的顺序依次编号。个结点对应的子树拥有的结点数量。的结点的子节点最右端为。，最左端的子节点序号为。
2024-03-16 00:34:15
743
原创 算法题：太阳
将所有线段从高到底排序，之后依次遍历计算其在x轴上的投影，如果与已有的投影段重合，则说明不能被太阳照到。需要特别注意投影段的更新过程，这里采用map保存阴影段的左端点和右端点横坐标，应该有更简洁的实现方法。，有m条平行于x轴的线段，其坐标、长度和高度为。，问多少条线段能够被太阳照到。在二维坐标系中，太阳的高度位。
2024-03-15 19:30:17
608
原创 算法题：奇怪的数
位满足题设条件的分布种数。设dp[a][b][c][d]表示后4位数分别选择a、b、c、d时前。要求n位数的数字A中任意5位的和不能超过m，问这样的数字A有多少种。位数字的可能分布情况。此题应该使用动态规划。
2024-03-14 17:30:50
519
原创 C++内存对齐的原因
原因硬件原因，cpu不是一个字节一个字节读取内存的，而是一次读取一块，因此按照块的大小进行内存对齐，可以提高cpu访问内存的速度。平台原因，不是所有硬件平台都支持访问任意地址的内存，某些平台只能在一些地址处获取特定类型的数据，否则抛出硬件异常。
2023-11-18 10:46:12
142
原创 static_cast，const_cast，reinterpret_cast, dynamic_cast的功能与区别
这四种类型转换操作符功能有所不同，对应不同的使用场景。
2023-10-19 15:29:00
135
原创 解析为什么不能自动合成的而又未显示删除的移动操作（move operations）会处于未定义状态
Explain why is a move operation that is not automatically synthesized but does not show deletion left undefined.
2023-10-16 22:25:02
165
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人