Supponiamo di avere un ampio elenco di coppie:
struct {x: double, y: double} pair;
vector<pair>
Qual è il modo più efficace per trovare tutte le coppie in cui (x1 < x < x2) AND (y1 < y < y2)?
O (n) non è accettabile, l'ordinamento in base a una variabile e la scansione di un'altra non ha un bell'aspetto.
La pre-elaborazione è accettabile quindi scambiare memoria aggiuntiva per le prestazioni è OK
Quello che stai cercando è chiamato Indice spaziale .
Nel tuo caso, stai cercando il caso più semplice di ottenere tutti i punti 2D all'interno di un rettangolo. Anche il semplice quad tree dovrebbe essere un grande miglioramento se hai molti punti.
Il problema di questo tipo di algoritmi e strutture di indicizzazione è che dipendono strongmente dalla forma dei dati. Sebbene abbiano tutti una piacevole complessità teorica, sarebbe meglio se investissi un po 'di tempo nel provare diversi algoritmi, quindi ne trovi uno che si adatta meglio ai dati del tuo mondo reale.
Suppongo che tu voglia un costo basso ammortizzato , cioè la pre-elaborazione è accettabile.
Stai cercando di trovare un elemento dati con proprietà specifiche. Non lasciarti ingannare dal fatto che la proprietà è espressa come quattro diversi confronti numerici. È davvero una proprietà dell'elemento intero . Ciò significa che devi ordinare i tuoi dati in base a una misura che tiene conto delle condizioni tutte e poi cerca prima la misura combinata .
In questo caso, cerca una coppia con 10 < x < 12 e 3 < y < 5 significa cercare una coppia dove 13 < x + y < 17. Potresti semplicemente ordinare la tua lista di coppie e la loro somma e trovare rapidamente tutti i candidati che soddisfano la condizione combinata.
Non tutti soddisfano le condizioni individuali, ma puoi definire un criterio di ordinamento secondario che richiede ad es. il valore x in considerazione. Questo è spesso abbastanza buono da poter essere risolto con l'ordinamento standard di un algoritmo di ricerca, senza definire strutture di dati collegate bidimensionali specifiche dell'attività.
(nota che è abbastanza veloce per i tuoi scopi dipende da quali sono i tuoi scopi. È del tutto possibile che tu abbia bisogno di una preelaborazione più complicata per raggiungere il tuo obiettivo aziendale. è meglio modificare gli algoritmi esistenti e semplici piuttosto che introdurre uno specifico di un compito, se non altro perché gli ordinamenti e le ricerche di librerie standard sono probabilmente ottimizzati molto meglio di quanto si possa fare da soli.)
Leggi altre domande sui tag algorithms indexing