scribble

466300750.github.io

Blog GitHub

20 Jul 2020
数据结构和算法

让CPU占用率曲线听你指挥

  1. 让CPU占用率固定在50%，为一条直线。
  2. 也为直线，但是占用率的值由命令行参数决定。
  3. 正弦曲线

解答：

  1. 简单解法：让busy时间和sleep时间各占50%。如果sleep 1s，需要busy循环多少次呢？ 假设运行代码的CPU是P4 2.4Ghz，现代CPU每个时钟周期可以执行两条以上的代码，平均值2： 2 400 000 000 * 2 /5 = 960 000 000(循环/秒)

    为了不让波形成一个锯齿状，可以降低两个数量级。

  2. 上述时间需要根据CPU的不同进行调整，缺少适应性。可以用GetTickCount()可以得到系统启动到现在所经历时间的毫秒值，最多能够统计到49.7天。 
     DWORD startTime = GetTickCount();
 while(true) {
     DWORD startTime = GetTickCount();
     while((GetTickCount() - startTime) <= busyTime) ;
		
     Sleep(idleTime);
 }
  3. 上面的解法都只考虑了只有这个进程的情况，如果还有其它进程呢，那就需要得到当前的性能数据，

中国象棋将帅问题

用比较巧妙的数学思想。

由于1-9分别是两个数组的位置，所以可以采用1-89的自然数：

while(i--) {
	if(i/9%3 == i%9%3)
		continue;
	printf("A=%d, B=%d/n", i/9+1, i%9+1)
}

数据结构

1. 布隆过滤器

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

如何选择哈希函数个数和布隆过滤器长度

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

2. Bitmap

3. B+树

B树是平衡多叉树

B树定义如下（其中m为阶数）：

  1. 每个节点最多有m-1个关键字（可以存有的键值对）
  2. 根节点最少可以只有一个关键字
  3. 非根节点至少有m/2个关键字
  4. 每个节点中的关键字都按照从小到大的顺序排序，每个关键字的左子树中的所有关键字都小于它，而右子树的所有关键字都大于它。
  5. 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
  6. 每个节点都存有索引和数据，也就是对应的key和value。

所以根节点的关键字数量范围：1 <= k <= m-1，非根节点：m/2 <= k < m-1

B树插入和删除过程中如果破坏了上述规则，则需要进行相应的分裂和合并。

B+树和B树非常相似：

  1. 根节点至少一个关键字
  2. 非根节点：m/2 <= k < m-1

不同点：

  1. 非叶子节点不存储数据，只存储索引，数据都存在叶子节点。
  2. 每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依关键字的大小自小而大顺序链接。
  3. 父节点存有右孩子的第一个元素的索引。

B+树相比B树的优势：

  1. 单一节点存储的元素更多，使得查询的IO次数更少，所以也就使它更适合作为数据库MYSQL的底层数据结构了。
  2. 所有的查询都要查找到叶子节点，查询性能是稳定的。
  3. 所有的叶子节点形成一个有序链表，更加便于查找。

LSM Tree（Log Structured Merge Trees）

LSM的思想，在于对数据的修改增量保持在内存中，达到指定的限制后将这些修改操作批量写入到磁盘中，相比较于写入操作的高性能，读取需要合并内存中最近修改的操作和磁盘中历史的数据，即需要先看是否在内存中，若没有命中，还要访问磁盘文件。原理：把一颗大树拆分成N棵小树，数据先写入内存中，随着小树越来越大，内存的小树会flush到磁盘中。磁盘中的树定期做合并操作，合并成一棵大树，以优化读性能。对应于使用LSM的Leveldb来说，对于一个写操作，先写入到memtable中，当memtable达到一定的限制后，这部分转成immutable memtable（不可写），当immutable memtable达到一定限制，将flush到磁盘中，即sstable.，sstable再进行compaction操作。

原理上，无论是B+-Tree还是LSM-Tree都是针对现代存储器的特点而设计的，前者注意利用了Bulk读写，而后者则是力求减少Seek操作，可以说各有侧重。

位运算

  1. X & 1 == 1 OR 0 判奇偶
  2. X & (X-1) 清除低位的1
  3. X & (-X) 得到最低位的1

Til next time,
at 12:14

scribble