algorithm - 最佳地重新排序钱包中的卡？

Question

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

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

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

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

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

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

(如果这看起来与编程无关:我可以想象一个应用程序，其中用户有几个常用项目的下拉列表，并且希望以最小化时间的方式保持这些项目的顺序需要找到一个特定的项目。)

Answer 1

虽然不是一般 k 的完整答案，this 1985 paper by Sleator and Tarjan对 k=1 情况下的几种动态列表更新算法的摊销复杂性进行了有用的分析。事实证明，移至前端非常好:假设每个项目的访问概率都是固定的，它所需要的步数(移动和交换)永远不会超过最优所需步数的两倍(静态)算法，其中所有元素按概率的非递增顺序列出。

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

我只读了前几页，但它看起来与我相关。希望对您有所帮助!