本文分为三个部分,一是位图法的定义,二是使用位图法判断数据是否存在,三是使用位图法找出不重复的数据,并附上C++的实现。

位图法

假设我们有40亿的unsigned int 数据,若我们用unsigned int的方式加载到内存,那么需要:40亿 * 4 / 1024 / 1024 = 15258MB 的内存。若我们把每一个数字的值作为数组下标,用一个位数组来表示每个数字的状态,那么空间则缩短了32倍(假设int占用空间为4字节),即仅仅需要 15258 / 32 = ‭476MB 的内存。

这个方法就叫做位图法。

阅读全文

定义

  • LFU(Least Frequently Used) 算法

最近最不常使用,缓存容量满的时候,置换使用频次最小的那个。

  • LRU(Least Recently Used) 算法

最近最少使用,缓存容量满的时候,置换最长时间没有使用的那个。

  • LRU-K 算法

LRU-k 有两个队列,一个队列是数据队列,一个队列是缓存队列,只有当数据队列数据的访问次数到达 K次,才将它放入缓存队列。

缓存队列按照 LRU 的方法置换数据。

阅读全文

把 KMP 算法做个详细总结,写成博文。

主要分四个部分说明:KMP 中的前缀后缀、构建 Next数组、KMP算法匹配过程、完整实现的源码.

KMP 中的前缀后缀

我们以字符串 match = "12312" 为例。它的前缀指的是: 1, 12, 123, 1231。它的后缀指的是: 2, 12, 312, 2312

KMP 中需要预先计算字符串 最长相同前后缀的长度,用于加快比对过程,具体原理第三部分详细说明。

这个 最长相同前后缀的长度 保存在一个数组中,这就是我们要找的 Next 数组。Next[i] 表示的意思是:match[0] ~ match[i]这个子串最长相同前后缀的长度

比如: i = 3, 则表示 "1231" 这个字符串的 最长相同前后缀的长度,本例中值为 1。 (前缀 "1", 后缀 "1")

阅读全文

字典序算法

给定一个排列,如 "aazz" ,求按照字典排列方式的下一个字符,这里是:"azaz".

以 "aazz" 为例,字典序的算法步骤如下:

  • 从右至左遍历,找出第一个左邻小于右邻的字符,记下位置 left;

本例中为 'a', left = 1;

  • 再次从右至左遍历,找出第一个比 str[left] 大的字符,记下位置为 right;

本例中为 'z', right = 3;

  • 交换 str[left] 和 str[right]

本例变成:'azaz';

  • 将 left 以后的字符按照从小到大排列。

如果第一步中,找不到左邻小于右邻的字符,则说明已经是字典序的最后一个排列了。

最近复习 C++, 顺手总结一下 c/c++ 的编译器。

gcc/g++ 区别

  • gcc 默认将 .c结尾的文件以c方式处理,.cpp 结尾的文件以 c++ 方式处理。而 g++ 把两者都用 c++ 方式处理。(c++语法比c更严格)
  • g++ 在预处理、编译、汇编阶段会调用 gcc来完成
  • 通常 g++ 用作链接阶段,但 gcc只是不能缺省的链接c++库文件,需要手动指明(-lstdc++).

阅读全文

算是计算机网络的相关知识,不做前后端开发的话通常记不得这么详细,现在把它记录一下.

大类

  • 1~~ Informational

表示接受的请求正在处理。

  • 2~~ Success

表示发往服务端的请求已经处理完成。返回一个成功信息。

阅读全文

Hash 算法


这个很简单,主要就是将 key 映射到一个定长的 hash地址,相同的key得到相同的 hash地址。

常见的 hash 算法有:

  • MD4, 输出为 16 字节,128 bit
  • MD5, 输出为 16 字节,128 bit
  • SHA-1, 输出为 20 字节,160 bit
  • SHA-256, 输出为 32 字节,256 bit

阅读全文

C++ 随机数产生 API


C++ 只能用C库的api来产生随机数. 头文件:#include <cstdlib>

//参数随机数,数字范围为 0 ~ RAND_MAX 之间
int rand();
//在调用 rand 前调用,设置随机数种子
void srand(unsigned int seed);

通常随机数种子用当前时间来设定。例如下:

#include <ctime>

srand((unsigned)time(NULL));

另,一些通用的方法如下:

阅读全文