Implementera cache

Hej!

Jag behöver implementera en cache för att spara undan gegrafisk data. Tänkte implementera som en prioritetskö i form av en Heap. Är det någon som har ngn erfarenhet av detta?

Jag har implementerat en prioritetskö med hjälp av ett TreeSet. Det ger något sämre tidskomplexitet men blir oerhört enkelt att implementera. Skillnaden i tid är att add och removeMin får O(log n) istället för average O(1) respektive worstTime O(log n). Men med en heap har du å andra sidan worstTime O(n) för add-metoden (då din array är full och du måste skapa en större). Valet beror på vilka operationer du kommer göra ofta och hur mycket tid du har på dig.

Jag skulle välja varianten med ett TreeSet, mycket enklare och bra prestanda. Det är klurigt att implementera en heap. Om du är intresserad kan jag slänga upp koden för den, det är inte många rader.

Tack för svaret!

Vill du får du gärna slänga upp koden!

Den behöver lite putsning men här kommer den:

import java.util.*;

/**
 * A priority queue implemented with a TreeSet. To allow
 * multiple objects with the same priority the private object
 * PQPair is used.
 */
public class PriorityQueue {
	private int count;
	private TreeSet tree;
	
	/**
	 * Constructor
	 */
	PriorityQueue() {
		tree = new TreeSet();	
	}
	
	/**
	 * Adds an object to the queue.
	 * @param int priority: The priority of this object
	 * @param Object o: The object itself
	 */
	public void add(int priority, Object o) {
		count++;		
		PQPair pair = new PQPair(count, priority, o);				
		tree.add(pair);
	}
	
	/**
	 * @return The element in the queue with lowest priority.
	 */
	public Object removeMin() {
		// Get the element with highest
		// priority and remove it from the queue
		PQPair temp = (PQPair)tree.first();
		tree.remove(temp);
		
		return temp.getData();
	}
	
	/**
	 * @return The size of the priority queue.
	 */
	public int size() {
		return tree.size();
	}
	
	/**
	 * @return Whether the priority queue is empty or not.
	 */
	public boolean isEmpty() {
	 	return tree.isEmpty();
	}
	
	/**
	 * A private class used for having multiple objects
	 * with the same priority.
	 */ 	
	private class PQPair implements Comparable {
		// A counter used for comparing objects with the same priority
		private int count;
		private int priority;
		private Object data;
	
		/**
		 * Constructor for PQPair
		 * @param int count: An id for this object.
		 * @param int priority: The priority
		 */ 
		PQPair(int count, int priority, Object data) {
			this.count = count;
			this.priority = priority;
			this.data = data;
		}

    	/**
    	 * Compares two PQPair objects first by their priority. If the
    	 * priority is equal the count field is compared.
    	 * @param Object o: The PQPair object to compare to
    	 * @return A positive integer if the other city is larger, if
    	 * it's smaller a negative integer is returned and if they are equal 0.
    	 */
		public int compareTo(Object o) {
			PQPair pair = (PQPair)o;
		 	
		 	// First compare the priorities
			if (this.priority < pair.getPriority())
		 		return -1;
		 	else if (this.priority < pair.getPriority())
		 		return 1;
		 	else {
		 		// The priorites are equal. Therefore compare count
		 		// The object with the lowest count should be
		 		// considered larger.
				if (this.count < pair.getCount())
		 			return -1;
		 		else if (this.count > pair.getCount())
					return 1;
		 		else
					return 0;
			}
		}

		/**
		 * @return The data in this PQPair
		 */		
		public Object getData() {
			return data;
		}
		
		/**
		 * @return The priority of this PQPair.
		 */ 
		public int getPriority() {
			return priority;
		}
		
		/**
		 * @return The count field
		 */ 
		public int getCount() {
			return count;
		}
	}
}

Om du undrar över något i koden är det bara att fråga.

Tack så mkt för det!!

Tänkte bara höra varför en heap är svår att implementera? Finns inte en sådan datastruktur färdigt i Java API:t?

Det finns många trevliga datastrukturer i API:t men en prioritetskö och vanlig kö saknas.

Det är inte jättesvårt att implementera en heap men det kräver lite arbete. Jag hittade en rätt kort implementation som du kanske vill titta på: http://www.cogs.susx.ac.uk/local/teach/dats/notes/html/node86.html

Det luriga är att flytta det nya elementet till rätt plats och att se till att det minsta elementet alltid ligger först.

Jag skulle även vilja kunna begränsa cachen till en max byte-storlek.. Kan man få reda på ett objekts bytestorlek på nåt sätt?
Utan att behöva manuellt titta på class-filen... :-)

Hmmm.. cachen jag behöver ska innehålla ett antal objekt av olika id och behöver därför kunna söka i cachen för att se om objektet med rätt id finns i cachen. Alltså kommer inte 'removeMin' att räcka eftersom den inte garanterar att objektet med rätt id returneras.

Är det fortfarande lämpligt att använda en prioritetskö? eller är det onödigt? Det som behövs är ju egentligen ett cachningsobjekten sorteras efter LRU eller LFU regler..
Dvs sannolikheten att objektet med rätt id har högst prioritet är störst, men inte lika med 1.

(Nån som fattar?)

Eftersom jag måste söka i cachen så är det kanske lämpligare att använda ett binärt sökträd istället...