6

前几天我出去买杂货，需要在钱包里搜索我的信用卡、客户奖励（忠诚）卡和带照片的身份证。我的钱包里还有几十张其他卡（工作证、其他信用卡等），所以我花了一段时间才找到所有东西。

我的钱包里有六个可以放卡片的插槽，每个插槽中的第一张卡最初都是可见的。如果我想找到一张特定的卡，我必须记住它在哪个插槽中，然后一次查看该插槽中的所有卡以找到它。越靠近插槽的前面，就越容易找到它。

我突然想到这几乎是一个数据结构问题。假设你有一个由 k 个链表组成的数据结构，每个链表可以存储任意数量的元素。您希望以最小化查找的方式将元素分配到链接列表中。您可以使用任何您想要的系统将元素分配到不同的列表中，并且可以随时重新排序列表。鉴于此设置，在任何假设下，是否存在对列表进行排序的最佳方法：

  1. 预先给定了访问每个元素的概率，并且访问是独立的，或者
  2. 您事先不知道什么时候会访问哪些元素？

我在钱包中使用的非正式系统是根据用例（ID、信用卡、会员卡等）将卡“散列”到不同的插槽中，然后将每个插槽中的元素按访问频率粗略排序。但是，也许有更好的方法来做到这一点（例如，将 k 最常用的元素存储在每个插槽的前面，而不管它们的用例如何）。

是否有解决此问题的已知系统？这是数据结构中众所周知的问题吗？如果是这样，最佳解决方案是什么？

（如果这似乎与编程无关：我可以想象一个应用程序，其中用户有几个常用项目的下拉列表，并希望以最小化查找所需时间的方式保持这些项目的顺序一个特定的项目。）

4

3 回答 3

3

虽然不是一般 k 的完整答案，但 Sleator 和 Tarjan 于 1985 年发表的这篇论文对 k=1 的情况下几种动态列表更新算法的摊销复杂度进行了有益的分析。事实证明，前移非常好：假设每个项目的访问概率是固定的，它永远不需要超过最佳（静态）算法所需的步骤（移动和交换）的两倍，其中所有元素都按概率的非递增顺序列出。

有趣的是，其他一些似是而非的启发式方法——即在找到所需元素后与前一个元素交换，并根据明确的频率计数保持顺序——并不共享这个理想的属性。OTOH，第 1 页。2 他们提到，Rivest 较早的一篇论文表明，在 swap-with-previous 下任何访问的预期摊销成本 <= 在 move-to-front 下的相应成本。

我只阅读了前几页，但它看起来与我有关。希望能帮助到你！

于 2013-01-07T03:25:31.743 回答
0

您需要查看跳过列表。为有特快列车和普通列车的列车系统安排车站也存在类似问题。特快列车仅在特快车站停靠，而普通列车则在普通车站和特快车站停靠。应该在哪里放置快车站点，以便在从起点站到任何站点时，可以最大限度地减少平均停靠站数。

解决方案是使用三进制数的站点（即，1、3、6、10 等，其中 T_n = n * (n + 1) / 2）。

这是假设所有站点（或卡）都有可能被访问。

于 2013-01-07T02:56:01.523 回答
0

如果你事先知道你的n张卡的访问概率，并且你有k个钱包插槽并且访问是独立的，那么贪婪的解决方案是不是很明显是最优的？也就是说，最常访问的k张牌放在口袋的前面，其次最常访问的k张放在后面，等等？（您永远不会希望将较低概率的牌排在较高概率的牌之前。）

如果您不知道访问概率，但您确实知道它们存在并且卡访问是独立的，我想类似地对卡进行排序，但是按目前看到的访问次数是渐近最优的。（移到前面也很酷，但我看不出在这里使用它的明显理由。）

如果你也惩罚纸牌移动，也许你会得到一些有趣的东西；如果我对卡片访问有任何已知的概率分布，无论是否独立，我都会在每次访问时贪婪地重新排序卡片。

于 2013-01-07T06:08:29.853 回答