知识卡片

普通读书笔记卡 · 1292.g.1.b.1.c · 生成模型:未记录

自组织查找权衡局部性与移动

理解等级:中级

查找成功后移到表头适合近期命中可能再次命中的访问;交换到前一位减少每次移动但适应较慢;预计不再访问时可移到末尾。收益取决于请求分布,数组整体移动可能需 O(n),并可能破坏原有顺序或影响并发读者。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      移动到最前面 这个策略适用于一个查找的元素t有更大的可能被再次查找到。当t在位置i找到时,将A[0,i-1]的所有元素移动到A[1,i],然后把t移动到A[0]。这个就是最多最近使用(MRU)分页算法的基础。 成功查找到则移动前一位 这个策略适用于如果一个查找的元素t有更大的可能能够被再次查找到;并

    参考来源

    - 位置:《算法技术手册》第5章《变种》(spine1538;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1501.html;u116-ch05-004)。 - 结论依据:116全文实读。 - 原始内容:移动到最前面 这个策略适用于一个查找的元素t有更大的可能被再次查找到。当t在位置i找到时,将A[0,i-1]的所有元素移动到A[1,i],然后把t移动到A[0]。这个就是最多最近使用(MRU)分页算法的基础。 成功查找到则移动前一位 这个策略适用于如果一个查找的元素t有更大的可能能够被再次查找到;并