Adobe intervista: quale struttura dati utilizzare per memorizzare migliaia di punti (x, y) per eseguire certe operazioni più velocemente

Question

Dobbiamo memorizzare migliaia di punti (x, y, c) c qui è per il colore di quel punto. Principalmente relativo ai pixel sullo schermo. Dobbiamo eseguire operazioni: dato x = i, dobbiamo cambiare il colore di tutti i punti aventi x = i. Similare, dato y = i, dobbiamo cambiare il colore di tutti i punti che hanno y = i.

Ho proposto una soluzione di matrice 2D. Quindi separa la tabella hash per le coordinate xey. Poi mi ha chiesto una soluzione ancora migliore. Quali combinazioni migliori di strutture dati possiamo usare?

Answer 1

Non è necessario un array 2D e hashtables separati. Se i tuoi dati sono densi, rappresentano tutti (o la maggior parte) di una regione rettangolare, quindi un array 2D di per sé è sufficiente. Si potrebbe chiedere come seguito che è più probabile che le coordinate siano usate per la ricerca, e quindi strutturare gli array facendo che la coordinata esterna sia quella in modo che la ricerca in quella coordinata sia localizzata nella memoria, altrimenti non si può fare molto meglio. Al contrario, per i dati sparsi le hashtable sono le migliori che puoi fare. (Sto assumendo che stiate tagliando le coordinate a una serie di oggetti punto.) Esistevano forse più informazioni sulla natura dei dati o su come è più probabile che vengano usati?

Answer 2

Se nessun recupero su una coordinata: è possibile proporre hashing x, y coppie di coordinate. Post propone un hash con bassa collisione, così come lo hash = (y << 16)^x;.

Ma si desidera accedere al proprio valore di scrittura per xey. La struttura per memorizzare punti ed eseguire efficientemente operazioni su di essa è un punto QTree o Quad Tree. See here.

Il quadrifoglio punto è un adattamento di un albero binario utilizzato per rappresentare i dati del punto bidimensionale . Condivide le caratteristiche di tutti i quadrif. ma è un vero albero poiché il centro di una suddivisione si trova sempre su un punto .

Un nodo di un punto Quadtree è simile a un nodo di un albero binario, con la principale differenza che ha quattro puntatori (uno per ogni quadrante) invece di due ("sinistra" e "destra") come in un ordinario albero binario . Anche una chiave è solitamente scomposta in due parti, facendo riferimento a x e alle coordinate y. Pertanto un nodo contiene le seguenti informazioni: 4 Indicatori: quad ['NW'], quad ['NE'], quad ['SW'] e quad ['SE']; che a sua volta contiene: chiave; solitamente espresso come x, y coordinate valore; ad esempio un nome

Quindi, è possibile avere una funzione ricorsiva per interrogare tutti i punti all'interno di un intervallo AABB. È possibile adattare questa implementazione di QueryRange()

class QuadTree 
{ 
    function queryRange(AABB range) 
    { 
    Array of XY pointsInRange; // Prepare an array of results 

    // Check objects at this quad level 
    for (int p := 0; p < points.size; p++) 
    { 
     if (range.containsPoint(points[p])) 
     pointsInRange.append(points[p]); 
    } 

    pointsInRange.appendArray(northWest->queryRange(range)); 
    pointsInRange.appendArray(northEast->queryRange(range)); 
    pointsInRange.appendArray(southWest->queryRange(range)); 
    pointsInRange.appendArray(southEast->queryRange(range)); 

    return pointsInRange; 
    } 
}