2021.06.03+1 衍复投资
std::atomic 和 std::memory_order
std::deque 的底层结构
http://c.biancheng.net/view/6908.html
本篇博文我们主要介绍了数据结构中双向队列deque以及其在STL中定义的接口，相信大家有了一定的认识。deque内部是小片的连续空间，小片间用链表相连，实际上内部有一个map的指针，因为知道类型，所以还是可以使用[]，只是速度没有vector快。快速的访问随机的元素，快速的在开始和末尾插入元素，随机的插入，删除元素要慢，空间的重新分配要比vector快,重新分配空间后，原有的元素不需要拷贝。
std::mutex 等待lock()的时候处于内核态or用户态。 spinlock呢？
字节对齐
移动语义 std::move
gdb 如何调试 release版本
linux kill 命令原理
算法题：
topK
链表倒数第N个结点
算法
KMP
int SubStr(const std::string& text, const std::string& pattern)
{
if (pattern.size() == 0)
return 0;
auto getNext = [](const std::string& pattern) -> std::vector<int> {
int n = pattern.size();
std::vector<int> next(n, 0);
int prefixlen = 0;
for (int i = 1; i < n; i++)
{
if (pattern[i] == pattern[prefixlen])
{
next[i] = ++prefixlen;
}
else
{
if (prefixlen > 0)
{
prefixlen = next[prefixlen - 1];
i--;
}
else
next[i] = 0;
}
}
return next;
};
auto next = getNext(pattern);
for (int i = 0, j = 0; i < text.size(); i++)
{
if (text[i] == pattern[j])
{
j++;
if (j == pattern.size())
return i - j + 1;
}
else
{
if (j != 0)
{
j = next[j - 1];
i--;
}
}
}
return -1;
}
智力题
一根木棒折成三段，能构成三角形的概率为多少？
1/4 https://blog.csdn.net/fanoluo/article/details/40374571
leveldb
leveldb是一个存储key-value的NoSQL数据库，基于LSM-TREE设计，利用磁盘的顺序写速度远大于随机写的特性。比较适合用在写多读少的场景
leveldb提供了Put，Get，Delete三种基本操作，以及Wrtie的Batch接口。
写：Delete是通过Put实现的，打了tag（type = Delete)表示要删除对应的key。
Put会调用Write，将 一条kv记录写入数据库中。
写的时候先APPEND写LOG，每个Write操作会生成日志，日志内容包括
sequence， count（Batch操作的数量），之后是count个kv值 （type，key size, key , value size, value)
日志存储通过Block实现，一个物理block32KB，日志头
checksum length type
4字节 2字节 FULL/FIRST/MIDDLE/LAST
写好LOG后，会把数据写到memtable中， kv会转化为Internal key, memtable由链表实现，内存通过arena分配
InternalKey size, key, sequence<< 56 | type, value size, value
当memtable内存到达一定程度后，会将当前memtable 转成immutable memtable，不再可写，并会将immutable memtable持久化到磁盘上。生成一个Level0的sstable文件
当level0的sstable文件数量过多的时候，会产生compaction，将sstable合并
多个level0的sst一起合并，因为level0的sst table可能有重叠。 leveln 可能和多个leveln+1的sst合并，因为每层的sst范围是不定的
compaction优先级： immtable -> level0 table， level0 -> level1 ， size compaction（某个level的sstable数量达到限制，触发与下一层的归并）， seek compaction，某层数据访问次数过多也会触发
sstable 格式：
data block
data block
data block
……
index
index
index
……
footer
读：按照 memtable-> immtable -> level0 sstable -> level n sstable 依次查询
sstable 有 tableCache，做index的缓存， BlockCache 做 Block的缓存
五、查找过程
通过通过sstable的key range，确定Key所在的level及sstable文件。
查找Table Cache，获取Index信息。
代码：TableCache::Get-> TableCache::FindTable
如果找到了，直接返回value，并获取到Table*指针。
如果没有在缓存中找到文件，那么打开SSTable文件，将其index部分读入内存。
根据Table*查找Block Cache，获取具体block记录。
代码：TableCache::Get-> Table::InternalGet -> Table::BlockReader
通过index_block判断记录是否存在，否直接返回。
如果存在，优先从Block Cache查找；找不到，则需要从文件获取到。
Manifest： 记录各个Level的sst文件分布，以及每个SST文件的Key范围
Current： 记录当前的Manifest名
虚函数底层实现原理
虚函数是通过虚函数表和虚函数指针来实现的
- 虚函数指针位于某类型的对象实例在内存中的最开始的位置
- 虚函数按照声明顺序放在表中
- 父类的虚函数，排在子类虚函数之前
instruction cmove
The purpose of cmov is to allow software (in some cases) to avoid a branch.
For example, if you have this code:
cmp eax,ebx
jne .l1
mov eax,edx
.l1:
then when a modern CPU sees the jne branch it will take a guess about whether the branch will be taken or not taken, and then start speculatively executing instructions based on the guess. If the guess is wrong there’s a performance penalty, because the CPU has to discard any speculatively executed work and then start fetching and executing the correct path.
For a conditional move (e.g. cmove eax,edx) the CPU doesn’t need to guess which code will be executed and the cost of a mispredicted branch is avoided. However, the CPU can’t know if the value in eax will change or not, which means that later instructions that depend on the results of the conditional move have to wait until the conditional move completes (instead of being speculatively executed with an assumed value and not stalling)
海量数据处理
https://cloud.tencent.com/developer/article/1557607
https://segmentfault.com/a/1190000021109127
bloom filter
https://juejin.cn/post/6844904007790673933
20220830 pdd
无锁队列https://zhuanlan.zhihu.com/p/352723264
cpu亲和性https://cloud.tencent.com/developer/news/699862
判断两个矩形是否相交
二叉树非递归后序遍历
假定矩形是用一对点表达的(minx, miny) (maxx, maxy)，那么两个矩形
rect1{(minx1, miny1)(maxx1, maxy1)}
rect2{(minx2, miny2)(maxx2, maxy2)}
相交的结果一定是个矩形，构成这个相交矩形rect{(minx, miny) (maxx, maxy)}的点对坐标是：
minx = max(minx1, minx2)
miny = max(miny1, miny2)
maxx = min(maxx1, maxx2)
maxy = min(maxy1, maxy2)
如果两个矩形不相交，那么计算得到的点对坐标必然满足：
（ minx > maxx ） 或者 （ miny > maxy ）
栈+记录node是否被访问过
class Solution
{
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> ret;
if (root == nullptr)
return ret;
unordered_set<TreeNode*> myset;
stack<TreeNode*> st;
st.push(root);
myset.insert(root);
while (!st.empty())
{
TreeNode* p = st.top();
if (p->left && !myset.count(p->left))
{
myset.insert(p->left);
st.push(p->left);
}
else if (p->right && !myset.count(p->right))
{
myset.insert(p->right);
st.push(p->right);
}
else
{
ret.push_back(p->val);
st.pop();
}
}
return ret;
}
};
miniMax
[cuda线程，内存模型]