我们有一个C++应用程序,我们尝试提高性能.我们发现数据检索需要花费大量时间,并且想要缓存数据.我们无法将所有数据存储在内存中,因为它很大.我们希望在内存中存储多达1000个项目.这些项目可以通过long密钥编制索引.但是,当缓存大小超过1000时,我们想要删除最长时间未访问的项目,因为我们假设某种"引用位置",即我们假设最近访问的缓存中的项目可能会再次访问.
你能建议一种实现它的方法吗？
我最初的实现是拥有一个map<long, CacheEntry>存储缓存,并添加一个accessStamp成员,CacheEntry只要创建或访问条目,就会将其设置为增加的计数器.当缓存已满并需要新条目时,代码将扫描整个缓存映射并找到最低的条目accessStamp,并将其删除.这样做的问题是,一旦缓存已满,每次插入都需要对缓存进行全面扫描.
另一个想法是举行的名单CacheEntries,除了缓存地图,并在每个访问移动访问的条目到列表的顶部,但问题是如何快速地在列表中找到该条目.
你能建议一个更好的方法吗？
谢谢
splintor
Jaa*_*koK 15
拥有你的map<long,CacheEntry>但不是拥有访问时间戳CacheEntry,输入两个链接到其他CacheEntry对象,使条目形成一个双向链表.每当访问一个条目时,将其移动到列表的头部(这是一个恒定时间操作).通过这种方式,您可以轻松找到缓存条目,因为它可以从地图中访问,并且能够删除最近最少使用的条目,因为它位于列表的末尾(我的首选是将双向链表放在圆形,所以指向头部的指针也足以快速访问尾部.还要记住将您在地图中使用的密钥放入,CacheEntry以便在从缓存中逐出时从地图中删除该条目.