GuGuBird

刷题回顾 现在我已经刷完hot 100 了，二刷开始记笔记+速记了呜呜呜 LTC 128. 最长连续序列 题目描述 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1： 123输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 12输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9 示例 3： 12输入：nums = [1,0,1,2]输出：3 提示： 0 <= nums.length <= 105 -109 <= nums[i] <= 109 题解 1234567891011121314151617181920212223242526272829class Solution {public: int longestConsecutive(vector<int>& nums) { ...

Cilk 实时系统 回顾cilk程序 我们回顾之前学过的关于并行程序的内容，这里主要是关于cilk的程序，关于一个triple nested loop的矩阵乘法的例子。 1234567for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { C[i][j] += A[i][k] * B[k][j]; } }} 这里我们令串行执行的时间为TsT_sTs​，同时我们令Cilk下的矩阵乘法的时间为TpT_pTp​，（在P个处理器下执行）。理想情况下，满足： Tp<TsT_p < T_s Tp​<Ts​ 我们仅仅需要在程序上加上cilk的关键字，就可以实现并行化的程序。这里我们需要注意的是，我们需要在程序上加上cilk的关键字，同时我们需要在编译器上加上cilk的编译器选项。 那么实际上，cilk是怎么做scheduling ...

基本数据结构 本篇文章主要讲实现一些基本的数据结构，并且讲一些对其理解，以及最后怎么样用数组去实现这些数据结构。 链表 链表是使用指针实现的动态数据结构的最好和最简单的示例。对于链表来说，其对于数组(array)的优势在于： 我们可以在一个列表的中间增加或者移除数据 我们并不需要去预先定义这个列表的大小 同时，链表的缺点如下： random access是不可能的，我们需要从头开始遍历链表 我们需要动态分配以及使用指针，代码会变得复杂，可能会有内存泄漏以及segment fault 链表的开销(overhead)要比数组大，因为动态分配的缘故，在内存的高效使用上不如数组，并且每一个在这种类型的list里面的item都需要一个额外的pointer 我们重新回顾一下关于链表的细节：链表就是一个node的set，每一个node都有一个value以及一个指向下一个node的指针。如果某个pointer是null，那么这个node就是list的最后一个node。并且如果这个pointer是第一个node，那么这个list就是空的。 下面是基本的链表功能实现，需要注意的如下： 涉及对 ...

并行存储分配 上一节课的相关回顾 Allocation void* malloc(size_t s); 其作用为分配并返回一个指针指向一个大小至少为s个字节的内存块 Aligned Allocation void* memalign(size_t alignment, size_t s); 其作用为分配并返回一个指针指向一个大小至少为s个字节的内存块，并且这个内存块的地址是alignment的倍数，并且alignment必须是2的幂次方。 Deallocation void free(void *p); 其作用为释放指针p指向的内存块 为什么我们要去做内存对齐？ 为了做cache line对齐，提高cache的命中率 矢量化指令要求数据对齐 Virtual Memory Allocation mmap() mmap() 是一种系统调用，通常它将磁盘上面的文件映射到内存中，但是它也可以用来分配虚拟内存，无需映射文件。 1234567void *p = mmap(0, // don't care where size, // size of the memory bl ...

存储分配 Stack allocation, deallocation 最简单的存储模式就是栈。 如果我们申请x bytes，我们主要做法就是： 12sp += x;return sp-x; 上述与实际上的函数调用都是同理。 当我们free x bytes的时候： 1sp -= x; 并且所有在sp之后的东西，都可以被认为是空闲的。 上述代码实际上一般要去检查栈溢出，但是一般编译器不这样做，因为如果有溢出，就是bug，你得处理它。 然而，栈的使用是有局限性的，也就是说，我们不会track中间的部分，但是栈很快！（实际上，栈是向下增长的，也就是说从高地址到低地址，这里方便理解才这样说） Heap 由于栈有缺陷，这里就有了堆，堆是一种动态分配的内存，我们可以在程序运行时动态的分配内存。同时，这里的堆与数据结构与算法、C++里面的堆是不同的。 C语言提供了malloc和free函数来分配和释放内存。C++提供了new和delete来分配和释放内存。不像Java和Python，这些语言有自己的垃圾回收机制，所以不需要手动释放内存。堆存储一旦被分配，就必须手动释放，否则会造成内存泄漏。同时我 ...

度量与计时 为什么没有第9课？因为感觉第9课没有什么记录的必要，因为实际上第九课告诉我们的是，编译器能做什么以及不能做什么，从四个角度告诉了我们编译器做的优化：优化标量、优化结构体、优化函数调用、优化循环。前两个主要是说的是我们不需要对参数先store再load，而是直接在寄存器中进行操作，后两个主要是说的是我们可以对函数调用进行内联优化，以及对循环中的有些变量可以提出来，减少循环次数。这些优化都是编译器可以做的，但是我们不需要关心，因为编译器会帮我们做好。 同时，最后还讲了编译器在某些情况下，比如内存重叠的情况下(Memory Aliasing)不能给数据做vectorize，因此我们一般要加个修饰符restrict，告诉编译器这个数据不会重叠，可以进行vectorize。 写在前面 To Mearsure Is To Know. 我们进行度量是为了更好的优化，而度量的目的是为了知道我们的程序的性能瓶颈在哪里，我们应该如何去优化。 Case Study 我们来看一个对排序进行时间度量的代码： 1234567891011121314151617181920212223242526# ...

多线程算法分析 这一章节的内容主要是关于对分支递归的并行性分析 🥵 算法回顾，分治递归的并行性 首先我们来看递归树，可以知道深度为log⁡bn\log_{b}nlogb​n，并且我们可以计算出来每一层的时间复杂度为O(nlog⁡ba)O(n^{\log_{b}a})O(nlogb​a)，所以我们可以得到总的时间复杂度为O(nlog⁡ba)O(n^{\log_{b}a})O(nlogb​a)。上述T(n)=aT(nb)+f(n)T(n)=aT(\frac{n}{b})+f(n)T(n)=aT(bn​)+f(n)，其中aaa是子问题的个数，bbb是每个子问题的规模，f(n)f(n)f(n)是合并子问题的时间复杂度。并且nlog⁡ban^{\log_{b}a}nlogb​a与$ a^{\log_{b}n} $是等价的，只需要对两个式子取对数即可得到（取log以b为底的对数）。 现在有一个问题：这些级别的工作量是多少？——我们要比较f(n)f(n)f(n)与nlog⁡ban^{\log_{b}a}nlogb​a的大小： 上述符号中，Big O符号表示的是一个上界，Big Ω\Omeg ...

竞争与并行性 上一节我们对于cilk有一个认识，就是Cilk keywords 是授予并行执行的权限，它们并不要求并行执行。编译器可以选择不并行执行，而是按照顺序执行。这种选择是为了提高性能，因为并行执行有时候会带来额外的开销。在这一节中，我们将讨论一些并行执行的问题，包拋竞争和死锁。（就像爱情一样，强扭的瓜不甜，两个人最好是都有各自奋斗的目标 😎 ） Determinacy Races 确定性竞争 定义：两个逻辑上并行的指令访问同一个内存位置，并且至少有一个是写操作。 我们用一个cilk_for 引入确定性竞争： 12345int x = 0;cilk_for (int i = 0; i < 100; i++) { x++;}assert(x == 2); 实际上，上述代码我们可以得到这样的图片，并且实际上执行increment操作是需要三步骤的，通过寄存器实现。因此，这样就会出现竞争，出现不同寄存器都要写入同一个位置的情况。那么对于执行的结果而言，不一定每次都是错误的，比如说我左边的那条路先跑完，然后再跑右边的路，这样就与顺序执行结果相同 ...

HPC Algorithm 回顾 这部分博客主要是对于HPC Algorithms的书籍回顾，进行总结，该部分内容和性能优化学习笔记相关联，写这个笔记记录主要是方便回顾，如果想看细节就回去看原文 第一章到第二章 第一章的目录如上图所示，主要包括： 经典的计算复杂度定义 同源复杂度，BIG O 摩尔定律的失效 不同种类的编程语言 其中，对于摩尔定律失效这一章节，讲了关于如何更高效使用更多的晶体管来驱动计算架构设计： 重叠执行指令，使 CPU 的不同部分保持忙碌（流水线）； 执行操作时不一定要等待前一个操作完成（投机和无序执行）； 增加多个执行单元，同时处理独立运算（超标量处理器）； 增加机器字的大小，以至于可以添加指令，对分成组的 128、256 或 512 位数据块执行相同的操作（SIMD）； 在芯片上增加多层高速缓存，以加快 RAM 和外部存储器的访问速度（存储器并不完全遵循硅扩展定律）； 在芯片上增加多个相同的内核（并行计算、图形处理器）； 在主板上使用多个芯片，在数据中心使用多台更便宜的计算机（分布式计算）； 使用定制硬件解决特定问题，提高芯片利用率（ASIC、FP ...

多核编程 这里的引言就是随着摩尔定律的终结，单核处理器的性能提升已经非常有限，而多核处理器的出现为我们提供了一种新的性能提升途径。多核处理器的出现，使得我们可以通过并行的方式来提高程序的性能，但是多核编程也带来了一些新的问题，比如线程之间的通信、数据共享、数据一致性等问题。本文将介绍多核编程的一些基本概念和技术，希望对大家有所帮助。 这门课学到的一个单词组：Argument Marshelling 就是说将参数打包成一个结构体，然后传递给函数。（参数编组） Shared-Memory Hardware Cache Coherence(缓存一致性) 现在有一个x=3在主存里面，这里有多个处理器，处理器想要获取x的值，要把x的值加载到自己的缓存里面，这个时候就会出现缓存一致性的问题，比如处理器1把x的值加载到自己的缓存里面，然后处理器2也把x的值加载到自己的缓存里面，这个时候处理器1修改了x的值，这个时候处理器2的缓存里面的x的值就是过期的，这个时候就会出现缓存一致性的问题。 值得注意的是，如果某个处理器想要获取这个x的值，它可以通过从其它处理器的缓存中获取，这样会更快一点。 这里有 ...