tem*_*def 6 language-agnostic algorithm hash linked-list data-structures
前几天我出去买杂货,需要搜索我的钱包,找到我的信用卡,我的客户奖励(忠诚度)卡和我的带照片的身份证.我的钱包里有几十张其他卡片(工作证,其他信用卡等),所以我花了一段时间才找到所有东西.
我的钱包里面有六个插槽,我可以放卡片,每个插槽中只有第一张卡片最初可以看到.如果我想找到一张特定的卡片,我必须记住它所在的插槽,然后一次查看该插槽中的所有卡片以找到它.它越靠近插槽的前部,就越容易找到它.
在我看来,这几乎是一个数据结构问题.假设您有一个由k个链表组成的数据结构,每个链表都可以存储任意数量的元素.您希望以最小化查找的方式将元素分发到链接列表中.您可以使用任何系统将元素分发到不同的列表中,并可以随时重新排序列表.鉴于此设置,在任何假设下,是否有最佳的订购列表方式:
我在钱包中使用的非正式系统是根据用例(ID,信用卡,会员卡等)将卡"哈希"到不同的插槽中,然后将每个插槽中的元素按访问频率大致排序.但是,也许有更好的方法(例如,将k个最常用的元素存储在每个插槽的前面,而不管它们的用例如何).
有没有一个已知的解决这个问题的系统？这是数据结构中众所周知的问题吗？如果是这样,最佳解决方案是什么？
(如果这似乎与编程无关:我可以设想一个应用程序,其中用户有几个常用项目的下拉列表,并希望保持这些项目的订购方式,以最大限度地减少查找所需的时间一个特定的项目.)
尽管不是一般 k 的完整答案，Sleator 和 Tarjan 于 1985 年发表的这篇论文对 k=1 情况下几种动态列表更新算法的摊余复杂度进行了有益的分析。事实证明，移到前面非常好：假设每个项目的访问概率是固定的，它所需要的步数（移动和交换）永远不会超过最佳（静态）算法所需的步数（移动和交换）的两倍，其中所有元素均按概率非递增顺序列出。
有趣的是，其他一些看似合理的启发式方法（即在找到所需元素后与前一个元素交换，并根据显式频率计数维持顺序）并不具有这种理想的属性。奥托，第 14 页。2 他们提到，Rivest 早期的一篇论文表明，与前一个交换下的任何访问的预期摊余成本 <= 移至前端下的相应成本。
我只读了前几页，但它看起来与我相关。希望能帮助到你！