前几天我出去买东西，需要在我的钱包里找我的信用卡、顾客奖励卡和带照片的身份证。我的钱包里有几十张卡(工作证、其他信用卡等)，所以我花了很长时间才把它们都找出来。
我的钱包里有六个插槽，我可以放卡片，每个插槽中只有第一张卡片在任何时候都是可见的。如果我想找到一张特定的牌，我必须记住它在哪个槽里，然后一次一张地查看槽里的所有牌来找到它。离槽的前面越近，越容易找到。
我突然想到这是一个数据结构的问题。假设您有一个由k个链表组成的数据结构，每个链表可以存储任意数量的元素。您希望以最小化查找的方式将元素分布到链表中。您可以使用任何系统将元素分布到不同的列表中，并且可以随时对列表进行重新排序。给定这种设置，在任何假设下，是否存在排序列表的最佳方法:
- 预先给定访问每个元素的概率，并且访问是独立的，或者
- 你事先不知道什么时候会访问哪些元素?
我在钱包中使用的非正式系统是根据用例(id、信用卡、会员卡等)将卡"散列"到不同的插槽中，然后根据访问频率大致对每个插槽中的元素进行排序。然而，也许有更好的方法来做到这一点(例如，将k个最常用的元素存储在每个槽的前面，而不管它们的用例如何)。
有解决这个问题的已知系统吗?这是数据结构中一个众所周知的问题吗?如果有，最优的解决方案是什么?
(如果这看起来与编程无关:我可以想象一个应用程序，其中用户有几个常用项的下拉列表，并希望以最小化查找特定项所需时间的方式保持这些项的顺序。)
虽然不是一般k的完整答案，但Sleator和Tarjan在1985年发表的论文对k=1的情况下几种动态列表更新算法的分摊复杂度进行了有益的分析。事实证明，move-to-front是非常好的:假设每个项目的访问概率是固定的，它所需要的步数(移动和交换)永远不会超过最优(静态)算法所需的两倍，在最优(静态)算法中，所有元素按概率的非递增顺序列出。
有趣的是，其他几个看似合理的启发式方法——即在找到所需元素后与前一个元素交换，并根据显式的频率计数保持顺序——并不共享这个理想的性质。OTOH，在第2页，他们提到Rivest之前的一篇论文表明，swap-with-previous下的任何访问的预期摊销成本<= move-to-front下的相应成本。我只看了前几页，但它看起来与我有关。希望能有所帮助!
您需要查看跳跃表。在有特快列车和普通列车的列车系统中，安排车站也存在类似的问题。快车只在快车站停靠，而普通列车在普通站和快车站停靠。
快速列车的停靠站应设置在何处，以使从始发站到任何站的平均停靠次数减至最少。解决方案是使用三进制数(即，1,3,6,10等，其中T_n = n * (n + 1)/2)的站。
这是假设所有的stop(或card)被访问的可能性是相等的。
如果你提前知道n张卡的访问概率，你有k个钱包槽，并且访问是独立的，那么贪婪解决方案是不是很明显是最优的?也就是说，访问频率最高的k张牌放在口袋的前面，访问频率次之的k张牌放在口袋的后面，以此类推?(你永远不希望低概率的卡牌排在高概率的卡牌之前。)
如果你不知道访问概率，但你知道它们存在，并且牌的访问是独立的，我想象对牌进行类似的排序，但根据迄今为止的访问次数而不是渐近最优。(Move-to-front也很酷，但我看不出有什么明显的理由在这里使用它。)
如果你也惩罚纸牌移动，也许你会得到一些有趣的东西;如果我有任何已知的卡片访问的概率分布，无论是否独立，我只要在每次访问时贪婪地重新排序卡片。