Sy Blog

Thinking will not overcome fear but action will.

KMP算法

C++

KMP算法是一种字符串匹配算法，可以再$O(n+m)$的时间复杂度内实现两个字符串的匹配。这篇主要记录一下自己对KMP算法的理解。 字符串匹配 ​ 字符串匹配问题就是:字符串P是否为字符串S的子串？如果是它出现在s的哪些位置。其中S称为模式串，P称为子串。 暴力解(Brute-Force) ​ 对于A和B两个字符串是否相等，我们一般是首先比较长度$len(A)==le...

Posted by HustDsy on September 12, 2020

存储器层次结构

深入理解计算机系统

存储技术 随机访问存储器 ​ 随机访问存储器分为动态和静态两类，静态RAM(SRAM)比动态RAM(DRAM)要快的多，并且更加昂贵。SRAM一般应用于高速缓冲器，而DRAM一般用于主存,帧缓冲区。 ​ 传统的DRAM中的单元(位)被分为$d$个超单元(supercell)，每个超单元由$w$个DRAM单元组成，一个$d×w$的DRAM总共存储了$dw$位的信息。超单元被组成一个$r$...

Posted by HustDsy on September 11, 2020

9.顺序容器

C++

一个容器的就是一些特定类型对象的集合，顺序容器为程序员提供了控制元素存储和访问的能力。 9.1顺序容器概述 vector 可变大小数组。支持快速随机访问，在尾部之外的位置删除和添加元素很慢 deque 双端队列。支持随机快速随机访问。在头部和尾部插入/删除速度很快 list 双向链表，支持双向顺序访问，在链表的任何位置插入/删除操作都很快 forward_lis...

Posted by HustDsy on September 9, 2020

最小堆的实现

堆顶是最小的元素

最小堆的满足以下三个条件a.堆是一颗完全二叉树 b.堆树中某个节点的值总是不大于或不小于其孩子节点的值c.堆树中每个节点的子树都是堆树 直接上代码 #include<iostream> using namespace std; class PQ{ private: int sz;//优先队列的大小 int capacity;//优先队列的容量 int*p...

Posted by HustDsy on September 7, 2020

快速排序

一种时间复杂度为o(nlogn)的排序算法

​ 相对于快速排序来说，我们接触到的排序算法可能是冒泡排序和插入排序，然而当数据过多的时候，冒泡排序和插入排序的性能往往并不能满足我们的需求。这时候快速排序的优点就体现出来了，平均情况下快速排序的时间复杂度为$o(nlog_n)$，最坏的情况是$o(n^2)$。 快排的思路 快排的思路其实很简单，采用分治的策略。步骤如下 选择一个基准元素（pivot） 把比pivot小的放在...

Posted by HustDsy on September 7, 2020

IEEE浮点表示

浮点数

IEEE浮点标准采用$V=(-1){^s}×M×2^E$来表示一个数，其中s表示符号位，M是一个二进制小数，称作尾数，E的作用是对浮点数进行加权，这个权重是2的E次幂。 本文主要讨论单精度的情况！ 下图展示了将这三个字段装进字的最常见的形式。 在单精度浮点格式（C语言的float中，s=1，k=8，n=23） s代表一个单独的符号位 k位的阶码字段，$exp=e...

Posted by HustDsy on September 7, 2020

8.IO库

C++

之前我们已经接触到一些IO的操作了，比如istream，提供输入操作，对应 cin»；ostream提供输出操作，对应cout«，接下来简单了解一下IO类。 8.1 IO类 IO库类型和头文件 头文件 类型 iostream istream，wistram从流读入数据ostream...

Posted by HustDsy on September 7, 2020

Initial Experience with 3D XPoint Main Memory

测试Optane的性能

这是一篇对OPtane进行性能测试的文章 1.实验配置 AEP机器如上图所示，一个AEP机器包含两个3D XPoint模块(256GB)分别连接到两个不同的CPU上。对于单个CPU来说，一个是本地模块，一个是远程模块。这也在意味着在AEP机器中存在NUMA效应。作者使用PMDK对3D Xpoint进行访问。主要是想测试以下几个方面的性能。 写内容对Optan...

Posted by HustDsy on September 6, 2020

开题

开题奇奇怪怪，态度可可爱爱

1.NVM的cacheline的刷新次数影响性能，而修改的字的多少不会影响，比如现在NVM是1011，我写0100，1010性能都是一样的。所以条目移动是一个点子，想法厨子 LB+ tree 2.一般来说先写val再写key，这样子中间有个fence，为了增加搜索性能，一般有一个标志位，这样子的话val和key的写入顺序不用管了，但是需要管val，key和标志位的顺序，这也是一个fence...

Posted by HustDsy on September 6, 2020

10.泛型算法

C++

标准库容器定义的操作集合惊人得小。标准库并未给每个容器添加大量功能,而是提供了一组算法,这些算法中的大多数都独立于任何特定的容器。这些算法是通用的(generic,或称泛型的):它们可用于不同类型的容器和不同类型的元素。 10.1概述 大多数算法都定义在头文件$algorithm$中。标准库还在头文件$numric$中定义了一系列的数值泛型算法. 迭代器令算法不依赖...

Posted by HustDsy on September 6, 2020

FEATURED TAGS
树索引 C++ Primer idea Optane Performance CSAPP 算法 排序 Hash索引 过滤器 PMDK Git
ABOUT ME

我自是年少，韶华倾负！

✉️ 379644660@qq.com

FRIENDS