新型移至前端或中间（MFM）列表更新算法的实验研究

### 新型移至前端或中间（MFM）列表更新算法的实验研究 #### 1. 引言 列表更新问题（LUP）或列表访问问题（LAP）是在线算法和自组织数据结构领域中一个被广泛研究的问题。LUP 是一种通用的内存访问问题，它使用链表作为数据结构，因为链表具有简单性和动态内存分配的特点。该问题最早由 McCabe 在 1965 年进行研究，Sleator 和 Tarjan 在他们的开创性论文中对在线算法的竞争分析进行了研究，其中就包括 LUP。2000 年，离线列表更新问题被证明是 NP 难的，这给研究人员开发高效的列表更新算法带来了更大的挑战。 LUP 在数据压缩、字典维护、哈希表中的冲突解决、编译器符号表中标识符的存储以及计算几何中的点最大值和凸包计算等方面都有广泛的应用。在 LUP 中，给定一个大小为 l 的未排序列表 L 和一个大小为 n 的请求序列，每个请求可以是对列表中某个项的访问、插入或删除操作。由于插入和删除操作是访问操作的特殊情况，为了简单起见，通常只考虑访问操作，因此 LUP 也被称为列表访问问题。 #### 2. 基本列表更新算法 存在三种基本的列表更新算法： - **移至前端（MTF）**：当访问一个项 x 时，将 x 移动到列表的前端，而不改变列表中其他项的相对顺序。 - **转置（TRANS）**：当访问一个项 x 时，将 x 与其前一个项交换位置。 - **频率计数（FC）**：为每个项维护一个频率计数器。插入一个项时，将其频率计数器初始化为 0。访问一个项后，将其计数器加 1，然后重新组织列表，使列表中的项按频率非递增顺序排列。 根据可用的输入信息数量，列表更新算法可分为离线算法和在线算法。在离线算法中，整个输入请求序列是预先已知的；而在在线算法中，输入请求序列是部分已知的，请求逐个到达。竞争分析是分析在线算法性能的标准方法，通过将在线算法处理请求序列的成本与最优离线算法的成本进行比较，来评估在线算法的性能。MTF 被证明是目前文献中最好的在线算法。 下面通过一个例子来说明 MTF 算法的访问成本计算： 假设列表 L = <1, 2, 3>，请求序列 σ = <1 3 2 3 2 2 1>。 |请求项|位置|访问成本|列表配置| | ---- | ---- | ---- | ---- | |σ1 = 1|1|1|<1 2 3>| |σ2 = 3|3|3|<3 1 2>| |σ3 = 2|3|3|<2 3 1>| |σ4 = 3|2|2|<3 2 1>| |σ5 = 2|2|2|<2 3 1>| |σ6 = 2|1|1|<2 3 1>| |σ7 = 1|3|3|<1 2 3>| 总访问成本 CMTF(σ) = 1 + 3 + 3 + 2 + 2 + 1 + 3 = 15。 #### 3. 文献综述 列表更新问题的研究历程丰富： - 1965 年，McCabe 首次研究该问题，并引入了 MTF 和 TRANS 算法。 - Rivest 研究了一类用于维护顺序列表的算法，证明 MTF 和 TRANS 算法在常数因子内是最优的。 - Sleator 和 Tarjan 正式引入了在线确定性列表更新算法的竞争分析概念。 - Irani 提出了第一个随机在线列表更新算法 SPLIT，其竞争比为 1.932。 - Albers 等人提出了简单的随机在线算法 COMB，竞争比达到 1.6，是目前随机算法中最好的竞争比。 - Albers 引入了前瞻概念，提高了确定性在线算法的竞争比。 - Reingold 和 Westbrook 提出了一个最优离线算法。 - Bachrach 等人对在线列表更新算法进行了广泛的理论和实验研究。 - Angelopoulos 研究了 LUP 中的局部性引用，证明 MTF 优于所有算法。 -