利用概率算法估算集合大小

原理

设集合 $ X $ 中有 $ n $ 个元素，如果有放回地随机均匀和独立地从 $ X $中选取元素，设取第 $ k $ 次时，恰好第一次重复出现之前所选取的元素。如果 $n$ 足够大，那么 $k$ 的期望趋近为：

$$ E(k) = \beta \sqrt{n} $$

其中，

$$ \beta = \sqrt{\pi/2} \approx 1.253 $$

more >>

展开全文 >>

论文阅读：基于闪存的缓冲区管理算法

SSD和传统的磁盘相比，有着许多不同的特性，比如读写不对称性，异地更新，先擦除后写入等。当为闪存设计缓存策略时，我们应该充分考虑到这些特性，如果直接把针对磁盘设计的缓冲区管理算法应用到闪存上，并不能充分发挥算法的性能。

这篇文章主要介绍了目前学术界关于闪存缓冲区管理的一些算法设计。前面部分介绍的是传统的缓冲区管理算法，后面部分介绍的是基于闪存优化的缓冲区管理算法。

more >>

展开全文 >>

论文阅读：针对闪存的成本感知的缓冲区管理策略（DASFAA 2015）

原文：Jiang Z, Zhang Y, Wang J, et al. A cost-aware buffer management policy for flash-based storage devices[C]. International Conference on Database Systems for Advanced Applications. Springer International Publishing, 2015: 175-190. [下载]

1. Abstract

由于读写的不对称性，传统的基于磁盘的缓冲区管理策略在闪存中并不能达到最优。这篇文章提出了一种针对闪存的名叫 CARF 的成本感知的缓冲区管理策略。提出了一种新颖的低开销的能够准确地确定驱逐页的成本模型。而且，这个成本模型能区分读写操作，还有更好的扫描抵抗力(scan resistance)。基于人工的trace和基准测试的trace表明，CARF的性能比当前最好的闪存管理策略还要高27.9%。

more >>

展开全文 >>

论文阅读：SSD内部多级并行性的探索和利用（TOC 2013）

原文：Hu Y, Jiang H, Feng D, et al. Exploring and Exploiting the Multilevel Parallelism Inside SSDs for Improved Performance and Endurance[J]. IEEE Transactions on Computers, 2013, 62(6):1141-1155. [下载]

1. Abstract

假设 SSD 内部有四个级别的并行性：通道并行性，chip并行性，die并行性和plane并行性，那么要如何去利用这些不同级别的并行性来提高 SSD 的性能呢。反过来，这个问题又是主要由这三个内在因素决定的：advanced commands，allocation schemes 和 4个并行性的优先级。该篇论文通过实验分析了这三个因素对 SSD 性能的影响。得出了如下结论：（1）提供不同 advanced command 的 flash 可以在 SSD 内部开发出不同级别的并行性，他们可以降低也可以提高 SSD 的性能，这取决于你怎么使用这些并行性。（2）不同的物理页映射方式会使用不同的 advanced command，从而具有不同级别的内在并行性，会对 SSD 性能产生不同的影响。（3）在三个内在因素中，4个级别的并行性的优先级顺序对 SSD性能产生的影响最大。4个级别的并行性最好的优先顺序是：通道并行性，die级别并行性，plane级别并行性，chip级别并行性。

more >>

展开全文 >>

论文阅读：SSD中基于PSO的缓冲区管理算法（ICITCS 2015）

原文：Wang Y L, Lee B J, Lee J J, et al. A PSO-based Buffer Management Scheme for Improving Hit Ratio of Solid State Drive[C]. IT Convergence and Security (ICITCS), 2015 5th International Conference on. IEEE, 2015: 1-5. [下载]

1. Abstract

随着闪存的普及和基于闪存的固态硬盘(SSD)具有耐冲击性，非易失性，低能耗和高I/O速度等优点，固态硬盘被广泛应用于企业计算环境。同时，固态硬盘还具有异地更新和读，写，擦除操作之间的非对称I/O延迟的特性，固态硬盘的写入和擦除操作要比读操作慢很多。因此，缓冲器替换算法需要很好地反映这种不对称性。该文中提出了一种以粒子群优化算法（PSO）为基础的缓冲管理算法来准确预测在缓冲区中的每个逻辑页中存的是热数据还是冷数据。该预测是页面级FTL方案的一个关键标准。被预测为热数据的页面将被保持在缓冲器，从而提高固态硬盘缓冲区的命中率。仿真结果表明，这篇论文提出的方案在读写命中次数和命中率方面要优于现有方案。

more >>

展开全文 >>

利用二级指针删除链表节点

删除单向链表的某个节点的只要将前一个节点的 next 指向当前节点的 next 指向的对象，即下一个节点（即：prev->next = curr->next），然后释放当前节点。

通常的做法是：首先判断删除的是不是头节点，然后还需要维护待删除节点的前一个节点的指针。

more >>

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true