La distanza tra due posizioni non è in realtà un attributo di nessuno dei due. Se calcolare la distanza è così pesante da rendere vantaggiosi i risultati della memorizzazione nella cache, probabilmente dovresti introdurre un DistanceCalculator con una funzione
float calculateDistance(Position a, Position b)
Ciò consentirebbe di nascondere tutti i trucchi di ottimizzazione nell'oggetto DistanceCalculator. Ciò consentirebbe anche di sfruttare facilmente il fatto che la distanza è simmetrica: dist (a, b) = dist (b, a).
Se le tue posizioni sono modificabili, la funzione dovrebbe essere davvero di forma
float calculateDistance(Location a, Location b)
con posizioni immutabili come parametri. Non è preferibile avere oggetti mutabili come chiavi di una mappa o anche come parametri di una funzione pura (o qualcosa che in realtà dovrebbe essere una funzione pura). Non vuoi occuparti di domande come "Cosa succede se la posizione a
cambia mentre sto calcolando la distanza tra a
e b
?".
Se desideri ancora che gli oggetti Posizione forniscano una funzione di distanza al resto della tua app, puoi anche includere l'oggetto DistanceCalculator come oggetto a livello di classe all'interno della classe Position e utilizzarlo quando fornisci la distanza:
float distanceTo(Position anotherPosition) {
return distanceCalculator.calculateDistance(this, anotherPosition);
}
Modifica: ecco alcuni punti sul calcolo e sulla memorizzazione nella cache delle distanze.
Prima di tutto è importante notare che una distanza tra i 2d punti è uguale - o piuttosto la stessa cosa - alla lunghezza del loro vettore di differenza. In secondo luogo, la lunghezza di qualsiasi vettore 2D (a, b) è uguale alla lunghezza del vettore (abs (a), abs (b)) e del vettore (abs (b), abs (a)). Quindi hai solo bisogno di memorizzare le lunghezze dei vettori con componenti positivi a > 0, b > 0, con un > b. Otterrai la distanza di molte possibili coppie di punti sul piano 2d calcolando la lunghezza di un singolo vettore.
Se le tue coordinate rientrano in un intervallo piuttosto limitato e la distanza tra i punti deve essere eseguita in modo molto efficiente, ti suggerisco di memorizzare le distanze in un array 2D e magari anche di calcolarle tutte in una volta. Se calcolare le radici quadrate è la parte che vorresti evitare, forse potresti semplicemente usare una tabella per le radici quadrate. Si noti inoltre che non è necessario calcolare le radici quadrate quando si confrontano solo le distanze.
Se le tue coordinate hanno un intervallo troppo ampio per qualsiasi cache basata su tabella, puoi provare a utilizzare una mappa (int, int) - > galleggiante. Avresti bisogno di una classe per quella coppia di int in Java con equals
e hashCode
implementate. In alternativa puoi provare a usare Long come una chiave, comprimendo x in alto int e y in basso int. Sfortunatamente l'implementazione hashCode()
di Long potrebbe rivelarsi un po 'problematica per questo approccio. Dovresti anche decidere quanti risultati desideri archiviare in caso di rischio di riempimento della memoria con risultati memorizzati nella cache.
Mi chiedo cosa intendi dicendo "il calcolo della distanza è complesso" nel tuo caso? Non penso che il recupero di un valore da una mappa sia necessariamente più veloce del semplice scricchiolio di alcuni numeri, ovvero fare sqrt(dx*dx + dy*dy)
. Probabilmente potresti evitare le collisioni molto bene con una buona funzione di hash (vedi link ) , ma la memorizzazione e il recupero dei valori da una mappa è ancora relativamente complicata.
Dovrebbe essere facile provare diversi approcci. Introduci DistanceCalculator come interfaccia e scrivi un paio di implementazioni: una senza cache, una con una mappa e forse una con un tavolo. Il passaggio tra le implementazioni dovrebbe richiedere al massimo un piccolo cambiamento nella tua classe Point.
Qualunque sia la soluzione ottimale per il tuo caso, potrebbe essere nascosta nell'implementazione di DistanceCalculator:
class CachingDistanceCalculator implements DistanceCalculator {
// Whatever proves an effective way to cache the lengths of vectors:
//
// private float[][] lengthTable;
// or
// private Map<IntVector2, Float> lengthMap;
// or
// private Map<Long, Float> lengthMap;
public float distance(Position a, Position b) {
int dx = Math.abs(a.getX() - b.getY());
int dy = Math.abs(a.getY() - b.getY());
return dx >= dy ? length(dx, dy) : length(dy, dx);
}
private float length(int dx, int dy) {
if (isCached(dx, dy)) {
return cached(dx, dy);
} else {
float length = calcLength(dx, dy);
cacheLength(length, dx, dy);
return length;
}
}
}
public class Point {
private static DistanceCalculator distanceCalculator;
...
public distanceTo(Point anotherPoint) {
return distanceCalculator.distance(this, anotherPoint);
}
}
EDIT2: Ok, dal momento che il problema potrebbe riguardare maggiormente il rilevamento delle distanze di una quantità limitata di oggetti in costante movimento, ecco un altro schizzo grezzo.
Quando si tiene una registrazione delle distanze tra un insieme relativamente piccolo di oggetti, una matrice simmetrica è a portata di mano. È necessario un indice per ciascun oggetto per utilizzare una matrice.
È ancora molto importante calcolare solo le distanze tra i punti fissi. Per gestire in sicurezza il cambio di posizione, un oggetto Location immutabile come proprietà mutabile di un oggetto in movimento funziona bene. È importante che entrambe le coordinate vengano cambiate contemporaneamente.
L'approccio sotto calcola le distanze pigramente, solo quando vengono richieste, non tutte le volte che un oggetto si muove. Il movimento attiva solo la cancellazione delle distanze calcolate in precedenza per l'oggetto specifico. Alcune sincronizzazioni possono essere aggiunte se è importante bloccare calcoli e movimenti simultanei. La logica di tracciamento della distanza può essere spostata in una classe e utilizzata attraverso un'istanza statica di tale classe.
public class MovingObject {
private static int nextObjectIndex = 0;
private static DynamicSymmetricMatrix<Float> distanceMatrix
= new DynamicSymmetricMatrix<>(Float.class);
private Location location;
private int index;
public MovingObject(Location initialLocation) {
this.location = initialLocation;
this.index = nextObjectIndex++;
}
public float distanceTo(MovingObject anotherObject) {
return getDistance(this, anotherObject);
}
public Location getLocation() {
return location;
}
public void moveTo(Location newLocation) {
this.location = newLocation;
updateDistanceMatrix();
}
private void updateDistanceMatrix() {
distanceMatrix.clearRowAndColumn(getIndex());
}
private int getIndex() {
return index;
}
private static float getDistance(MovingObject a, MovingObject b) {
Float distance = distanceMatrix.get(a.getIndex(), b.getIndex());
if (distance == null) {
distance = calcDistance(a, b);
distanceMatrix.set(a.getIndex(), b.getIndex(), distance);
}
return distance;
}
private static float calcDistance(MovingObject a, MovingObject b) {
return a.getLocation().distanceTo(b.getLocation());
}
}