内存故障下的数据结构与字典实验研究

### 内存故障下的数据结构与字典实验研究 在现代计算平台中，内存并非完全可靠，内存故障可能会对计算产生严重影响。本文将探讨内存故障下的数据结构，特别是字典的实现，并通过实验研究不同字典实现的性能。 #### 1. 内存故障问题及背景 现代计算平台的内存可能会因制造缺陷、电源故障、宇宙辐射和α粒子等环境条件而出现内容损坏的情况。对于处理大量数据的应用，如Web搜索引擎，即使很小的故障概率也可能导致索引中的位翻转，从而影响关键字搜索的准确性。 传统处理内存故障的方法包括错误检测和纠正机制，如冗余、汉明码等，但这些方法在时间和金钱上成本较高，在大规模PC集群中并不总是被采用。因此，在应用层面设计对内存故障具有弹性的算法和数据结构是很有必要的。 #### 2. 故障RAM模型 本文关注的是故障RAM模型，在该模型中，自适应对手可以在任何时间覆盖任何内存字的值，且无法直接区分损坏的值和正确的值。算法执行或数据结构生命周期内的内存故障总数有一个上限δ，同时有O(1)个安全内存字，其内容永远不会被损坏。 在故障RAM模型中，设计算法和数据结构的一种自然方法是数据复制。一个弹性变量由(2δ + 1)个标准变量的副本组成，其值由多数副本决定。但这种方法会在空间和运行时间上产生Θ(δ)的乘法开销。例如，基于AVL树的标准字典的简单弹性实现需要O(δn)的空间和O(δ log n)的时间来执行每个搜索、插入和删除操作，只能容忍O(1)个内存故障。 #### 3. 弹性排序和搜索问题 - **弹性排序问题**：给定一组n个键，目标是计算一个忠实排序的排列，使得忠实键的子序列是有序的。该问题可以在O(δ n log n)时间内简单解决，也有O(n log n + δ³)时间的算法和Ω(n log n + δ²)的下界，以及最优的O(n log n + δ²)运行时间的ResSort算法。对于多项式有界整数键，还可以实现O(n + δ²)的改进运行时间。 - **弹性搜索问题**：给定一个忠实排序的n个键的序列和一个搜索键κ，目标是返回值为κ的键（故障或忠实）。该问题有一个简单的O(δ log n)时间算法，也有Ω(log n + δ)的下界，还有O(log n + δ²)的确定性算法、最优的O(log n + δ)的随机算法ResSearch和确定性算法。 #### 4. 弹性字典 弹性字典的插入和删除操作定义与普通字典相同，搜索操作需要具有弹性。目前有几种弹性字典的实现： - **Finocchi等人的实现**：使用O(log n + δ²)的摊销时间执行每个操作。 - **Brodal等人的实现**： - **Rand算法**：通过维护动态变化的区间集和相应的键来实现。每个区间包含Θ(δ)个键，存储在经典的AVL树中，标准变量被弹性变量取代。搜索操作通过随机读取一个副本，最后可靠地读取最终区间的边界来检查是否包含搜索键。插入和删除操作类似，当区间中的键数