最後に使用された要素を効率的に見つけることによってキャッシュ（マップ）を小さく維持する

Question

大きなタイル画像の再サンプリングされた領域を処理するJavaアプリケーションがあります。

連続した領域クエリは互いにしばしば近いため、イメージタイルをハッシュマップにキャッシュするのが理にかなっています。今、私はこのキャッシュを無限に成長させないようにしたいと思います。

パフォーマンスを落とさないためには、最も長い時間アクセスされていないマップ要素を見つけるO（1）/ O（logN）メソッドが必要です。これを行う方法はありますか？また、キャッシュからランダムな要素を削除するだけと比較する方法はありますか？

ヒープまたはbstを使用すると、最後にアクセスされたアクセスのリストを並べ替えることができますが、そのうちの1つのアクセスを最後に更新すると線形時間がかかります。最も長い時間前にロードされた画像は、ちょうど秒前にアクセスされた可能性があるため

Map<Point, BufferedImage> loadedImages = new ConcurrentHashMap<>(); 
Deque<Point> lastUsed = new ConcurrentLinkedDeque<>(); 

int getRGB(double tileX, double tileY) { 
    Point point = new Point((int) tileX, (int) tileY); 
    if (!loadedImages.containsKey(point)) { 
     loadedImages.put(point, ImageIO.read(new File("R:\\tiles\\22\\" + point.y + "_" + point.x + ".jpg"))); 
     lastUsed.addLast(point); 
    } 
    BufferedImage img = loadedImages.get(point); 
    if (loadedImages.size() > 1000) { 
     loadedImages.remove(lastUsed.pollFirst()); 
    } 
    //do stuff with img 
} 

これは最適ではありません。

は、ここで私が現在使用しているコードからの抜粋です。

Answer 1

一緒Collections.synchronizedMap(linkedHashMap)とのLinkedHashMapトリックをしました。 LinkedHashMapのremoveEldestEntryメソッドは、最後にアクセスされたエントリをいつ削除するかを条件を定義することを可能にします。

final int MAX_BUF_SIZE = 1000; 

Map<Point, BufferedImage> loadedImages = new LinkedHashMap(MAX_BUF_SIZE + 1, .75F, true) { 

    @Override 
    protected boolean removeEldestEntry(Map.Entry eldest) { 
     return size() > MAX_BUF_SIZE; 
    } 
}; 

int getRGB(double tileX, double tileY) { 
    Point point = new Point((int) tileX, (int) tileY); 
    if (!loadedImages.containsKey(point)) { 
     loadedImages.put(point, ImageIO.read(new File("R:\\tiles\\22\\" + point.y + "_" + point.x + ".jpg"))); 
    } 

    BufferedImage img = loadedImages.get(point); 
    //do stuff with img.. 
} 

Answer 2

LRUCacheとして使用のLinkedHashMap - 簡単な例：

public class LRULinkedHashMap extends LinkedHashMap<Integer, String> { 

    /** 
    * 
    */ 
    private static final long serialVersionUID = 1L; 
    private int capacity; 

    public LRULinkedHashMap(int capacity) { 
     // initialise the capacity, and when to 'double' the capacity (75% of capacity) and 
     // 'true' if the ordering should be done based on the last 
     // access (from least-recently accessed to most-recently accessed) 
     super(capacity, 0.75f, true); 
     this.capacity = capacity; 
    } 


    /** 
    * Returns true if this map should remove its eldest entry. 
    * This method is invoked by put and putAll after inserting a new entry into the map. 
    * It provides the implementor with the opportunity to remove the eldest entry each 
    * time a new one is added. This is useful if the map represents a cache: it allows 
    * the map to reduce memory consumption by deleting stale entries. 
    */ 
    @Override 
    protected boolean removeEldestEntry(Entry<Integer, String> eldest) { 
     // this will return true and remove the eldest entry every time the size of the map 
     // is bigger than the capacity - the size() will never go beyond double the capacity 
     // (it will double automatically when it hits 75% of original capacity) as this ensures 
     // any 'put' entry over the capacity is removes the eldest object 
     return size() > this.capacity; 
    } 



    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     // Last Recently Used LinkedHashMap Cache 
     LRULinkedHashMap cache = new LRULinkedHashMap(6); 

     // put some objects into the map 
     cache.put(1, "one"); 
     System.out.println(cache); 
     cache.put(2, "two"); 
     System.out.println(cache); 
     cache.put(3, "three"); 
     System.out.println(cache); 
     cache.put(4, "four"); 
     System.out.println(cache); 
     cache.put(5, "five"); 
     System.out.println(cache); 
     cache.put(6, "six"); // capacity (6) reached 
     System.out.println(cache + " <-- Capacity Reached"); 
     cache.put(7, "seven"); // 1 is removed - eldest 
     System.out.println(cache + " <-- 1 removed"); 
     cache.put(8, "eight"); // 2 is removed - next eldest 
     // access an object before it is removed 
     System.out.println(cache + " <-- 2 Removed"); 
     cache.get(4); // 4 retrieved placed after 8 - nothing removed (we've only changed the order, not put anything into the map) 
     System.out.println(cache + " <-- '4' Retrieved, access order changed only"); 
     cache.put(9, "nine"); // 3 is removed - next eldest (4 was retrieved!) 
     System.out.println(cache + " <-- 3 Removed"); 
     cache.put(10, "ten"); // 5 removed - next eldest 
     // first item is always the eldest - will be next to go if item retrieved or put in map 
     System.out.println(cache + " <-- 5 Removed"); 

    } 

}