什么是弗兰塔-马里活动列表？

Question

这个问题的最佳答案引用了 Franta-Maly 事件列表。什么是 Franta-Maly 事件列表及其用例是什么？

Answer 1

Franta -Maly 事件列表（或事件集）在WR Franta 和 Kurt Maly 于1977 年发表的论文《模拟事件集的高效数据结构》中进行了描述。在本文中，他们提出了一种新的事件调度算法，该算法改进了之前发布的算法。根据摘要：

首先，新算法的性能对偏态分布相当不敏感，其次，其最坏情况的复杂度为 O(sqrt(n))，其中 n 是集合中事件的数量。此外，估计平均复杂度的测试表明它几乎与 n 无关。

该论文提出了作者所说的 TL（两级）算法，用于将事件插入事件集中：

抛开模拟术语，我们需要一个有效的解决方案来解决以下问题：为动态变化的记录集合设计一个物理数据结构，支持使用最小值键检索记录。在模拟环境中，记录是事件通知，每条记录都包含标识事件的信息，关键是事件发生的预定时间。安排的时间称为事件时间，记录收集器¹称为事件集。

...

TL算法的基本思想是限制必须扫描插入的通知的数量。通过为每个间隔动态创建辅助密钥列表并将它们与正确的边界虚拟密钥相关联，可以满足此要求。每个辅助键都指向一个间隔内通知子列表的开头...每当这些子列表之一变得不平衡（即太大）时，就会通过将通知移动到相邻列表或使用其创建一个新子列表来调整结构。关联的辅助密钥。

^{1 我想指出，也许“记录收集者”是原论文中的一个拼写错误，而“记录收集”可能就是这里的意思。}

Franta-Maly 论文链接：http://staff.ii.pw.edu.pl/~gjb/aal/index_lists.pdf

^{注意：本答案引用的部分受以下版权声明的约束：}

^{Communications of the ACM，1977 年 8 月，第 20 卷，第 8 期。版权所有 (c) 1977，Association for Computer Machinery, Inc。在 ACM 版权声明的前提下，授予重新发布本材料全部或部分内容的一般许可，但不得以营利为目的并提及该出版物、其发行日期以及经计算机协会许可授予重印权的事实。作者地址：明尼​​苏达大学计算机科学系，明尼阿波利斯，明尼苏达州 55455。}