Letture più veloci, su un piano di griglia infinito, rispetto all'utilizzo di una tabella hash?

Non penso davvero che ci sia un modo per renderlo più veloce. Secondo MSDN , il tempo di recupero di Dictionary è vicino a O (1), che è il più veloce che puoi ottenere. E il modo in cui si calcola il valore hash non ha spazio per le collisioni hash.

L'unica cosa che puoi fare adesso è cambiare l'algoritmo per minimizzare il numero di letture.

Quindi, ho provato a fare un rapido benchmarking. Ho usato 3 algoritmi: HashSet, Dictonary e semplice implementazione Quadtree. Ho creato 2 set di dati, prima con distribuzione completamente casuale. Il secondo è stato fatto creando scatole casuali e riempiendole. Il set di dati di lettura era una distribuzione casuale. HashSet e Dictionary sono piuttosto simili. I risultati sono in tick:

• HashSet
  • Distribuzione uniforme: 350000
  • Distribuzione della casella: 430000
• Quadtree
  • Distribuzione uniforme: 1510000
  • Distribuzione della casella: 490000

Puoi ottenere la mia fonte qui: link

Il tuo test ha poco senso. Innanzitutto, perché stai risparmiando punti? Non dovresti salvare booleani o intarsi o qualcosa del genere? Inoltre, se stai riempiendo l'intero spazio, allora il dizionario non ha molto senso. In secondo luogo, il modo in cui leggi i dati ha un'enorme area di memoria. Sei sicuro di leggere i dati in modo sequenziale? Questo è il motivo per cui sto randomizzando l'ordine di accesso nel mio benchmark. La prossima cosa è quel tuo rettangolo. Sei sicuro di averne solo uno? Il tuo algoritmo si romperà se hai intenzione di avere più. E sei sicuro di essere in grado di ricostruire tale bounding box dai dati che hai sull'input? Questo algoritmo è direttamente utilizzabile nel tuo problema o è qualcosa che devi cambiare? Se dopo, i risultati sono inutili e non informativi.

Se i blocchi sono relativamente grandi e ne esiste un numero relativamente piccolo, posso vedere due approcci che potrebbero aiutarti:

1. Decomporre ciascun blocco in rettangoli e quindi memorizzarli in un albero R .
2. Dividi l'aereo in modo uniforme nei quadranti. Per ogni quadrante che non è omogeneo (completamente vuoto o completamente riempito), continuare a dividere in modo ricorsivo. Questa struttura si chiama quadtree .

I could use an array (by computing a bounding rectangle (bRect) around the data and then doing data=array[(y-bRect.Top)*bRect.Height+x-bRect.Left]) but then I'd have to rebuild the entire array each time bRect.Height changed, or bRect.Width increased.

Utilizza la funzione Cantor pairing come funzione di hash. Immagino anche che l'uso della funzione di accoppiamento cantor per indicizzare in un array semplice sia un po 'più veloce di una tabella hash perché è possibile evitare il sovraccarico di controllo di collisioni e operazioni di modulo.

Quanto è grande il tuo array? Se non si adatta alla cache L2, potresti prendere in considerazione le curve Z-order per aiutare con la località spaziale . È anche possibile usare curve hilbert con lo stesso risultato, ma sembra piuttosto costoso rispetto alle curve Z-order.

Devo anche notare che quando si ha una singola massa connessa, la memorizzazione dei dati per pixel potrebbe non essere l'approccio migliore. Potrebbe essere possibile velocizzare il tuo algoritmo generando mipmap (versioni a bassa risoluzione dei tuoi dati) e leggendo da esso per mantenere tutto in cache.

Dato che hai menzionato la lettura è il collo di bottiglia, spostare il calcolo sulla GPU può portare ad un certo grado di successo.