知识卡片
自组织查找权衡局部性与移动
查找成功后移到表头适合近期命中可能再次命中的访问;交换到前一位减少每次移动但适应较慢;预计不再访问时可移到末尾。收益取决于请求分布,数组整体移动可能需 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有更大的可能能够被再次查找到;并