È buono memorizzare distanza come quella?

2

Ho una classe Position con i campi int x e int y . Ho un sacco di punti e alcuni di loro hanno bisogno di conoscere la distanza da tutti gli altri punti. Ha senso memorizzarlo in Map<Position, float> distances (questo è un altro campo nella classe Position )? Altri punti non hanno bisogno di quell'informazione, quindi il loro campo distances è null .

C'è qualcosa di evidentemente sbagliato in questo, cioè un cattivo design? Calcolare la distanza in questo caso è abbastanza complesso, quindi ha certamente senso archiviare i risultati in una raccolta invece di calcolarlo al volo.

    
posta user5539357 30.03.2016 - 14:31
fonte

3 risposte

8

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());
    }
}
    
risposta data 30.03.2016 - 16:16
fonte
1

Una distanza viene calcolata tra due punti. Non credo che una mappa in cui la chiave sia un oggetto Point funzionerà. Hai davvero bisogno di una tupla di due punti e della distanza associata. Anche in questo caso, puoi utilizzare una mappa di ordinamento per memorizzare i calcoli della distanza, magari come x1 + "," + y1 + "|" + x2 + "," + y2 . Due punti: x:3, y:5 e x:6, y:12 verrebbero memorizzati nella cache di distanza con una chiave di 3,5|6,12 .

public class Point {
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    private int x;
    private int y;

    private static Map<String, float> cachedDistances = new Map<String, float>();

    public float calculateDistance(Point other) {
        String key = getDistanceCacheKey(other);

        if (!cachedDistances.containsKey(key)) {
            // Calculate distance and save to cache
        }

        return cachedDistances[key];
    }

    private String getDistanceCacheKey(Point other) {
        return this.x + "," + this.y + "|" + other.getX() + "," + other.getY();
    }
}

Ora la sfida diventa mantenere la cache sincronizzata con gli oggetti punto e rimuovere le chiavi quando gli oggetti punto vengono distrutti. Se le coordinate x o y di un oggetto punto cambiano, è necessario eliminare tutti i valori della cache di distanza che contengono le vecchie coordinate x e y. Ciò diventa ancora più difficile se due o più punti esistono con le stesse coordinate.

Questo potrebbe anche essere un caso di ottimizzazione prematura. Vorrei solo calcolare la distanza ogni volta. Solo dopo aver incontrato un problema di prestazioni, proverei a implementare un meccanismo di memorizzazione nella cache, che a dire il vero sarebbe preferibile come una sua classe e ogni oggetto Point dovrebbe ottenere il proprio identificatore univoco.

    
risposta data 30.03.2016 - 15:30
fonte
1

Può avere senso farlo se il numero di volte che la distanza verrà recuperata è molto più di una volta per cambio di distanza. Prima di tutto, nascondilo dietro un metodo nella classe Position, ad es. distance(Position other) in modo che il resto del codice non abbia bisogno di sapere come viene fatta la salsiccia. La vera considerazione sarà intorno assicurandosi che la cache delle distanze sia mantenuta aggiornata. È necessario assicurarsi di aggiornare (o almeno invalidare) la voce sulla mappa ogni volta che viene modificata la posizione. Se si è multi-thread, questo diventa molto più complicato. Questo è probabilmente il più grande problema qui.

Potresti prendere in considerazione l'idea di utilizzare una mappa a livello di classe qui. Poiché la distanza da A- > B presumibilmente è la stessa di B- > A, c'è un potenziale di ottimizzazione (usa una tupla priva di ordini come chiave). Inoltre, è più facile assicurarsi di avere aggiornato tutte le distanze quando cambia una posizione. Se lo lasci sull'oggetto, devi sapere quando sono cambiate le altre posizioni, non solo this e ciò può risultare complicato. È potenzialmente possibile introdurre più contese, ma ottenere la soluzione giusta è la tua preoccupazione principale qui.

    
risposta data 30.03.2016 - 15:25
fonte

Leggi altre domande sui tag