Son kullanılan öğeyi verimli bir şekilde bularak önbelleği (harita) küçük tutun

Question

Büyük bir çini görüntüye yeniden örneklenmiş alanlar sunan bir java uygulamasına sahibim.

Ardışık alan sorguları genellikle birbirine yakın olduğu için, görüntü eşiklerini bir karma haritada önbelleğe almak anlamlıdır. Şimdi bu önbelleğin süresiz olarak büyümesini engellemek istiyorum.

Performansı kaybetmemek için, en uzun süredir erişilemeyen harita öğesinin bulunmasıyla ilgili bir O (1)/O (logN) yöntemine ihtiyacım var. Bunu yapmanın bir yolu var mı ve rasgele öğeleri önbellekten kaldırmaya nasıl benziyor?

Bir yığın veya bst, son erişilenler listesini sıralamamı sağlar, ancak bunlardan birinde son erişimin güncellenmesi doğrusal zaman alır. En uzun süre önce yüklendi görüntü sadece bir saniye önce erişilmiş olabilirdi çünkü

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 
} 

Bu optimum değildir:

İşte şu anda kullanıyorum koddan bir alıntı.

Answer 1

bir araya Collections.synchronizedMap(linkedHashMap) ile LinkedHashMap hile yaptı. LinkedHashMap'in removeEldestEntry yöntemi, son erişilen girdinin ne zaman kaldırılacağı konusunda bir koşul tanımlamayı sağlar.

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 olarak kullanın LinkedHashMap - Basit Örnek:

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"); 

    } 

}