Come cercare una vasta gamma di serie di gamme contigue per il numero dato

Question

Così semplicemente metti, questo è ciò che sto cercando di fare:

Ho una raccolta di oggetti Range che sono contigui (non sovrapposti, senza spazi vuoti tra loro), ciascuno contenente un start e end int e un riferimento a un altro oggetto obj.Queste gamme non sono di dimensioni fisse (il primo potrebbe essere 1-49, il secondo 50-221, ecc.).Questa collezione potrebbe crescere abbastanza grande.

Spero di trovare un modo per cercare la gamma (o più specificamente, l'oggetto che fa riferimento) che include un dato numero senza dovertitare sull'intera collezione, controllando ogni intervallo per vedere se include il numero.Queste ricerche saranno eseguite frequentemente, quindi velocità / prestazioni è la chiave.

Qualcuno conosce un algoritmo / equazione che potrebbe aiutarmi qui?Sto scrivendo a Java.Posso fornire maggiori dettagli se necessario, ma ho pensato che cercherei di tenerlo semplice.

Grazie.

Answer 1

Se suona come vuoi usare un TreeMap , dove la chiave è il fondo dell'intervallo e il valore è l'oggetto Range.

Quindi per identificare l'intervallo corretto, basta utilizzare il metodo floorEntry() per ottenere molto rapidamente il RangetagCode più vicino (minore o uguale), che dovrebbe contenere la chiave, come:

    TreeMap<Integer, Range> map = new TreeMap<>();
    map.put(1, new Range(1, 10));
    map.put(11, new Range(11, 30));
    map.put(31, new Range(31, 100));

    // int key = 0; // null
    // int key = 1; // Range [start=1, end=10]
    // int key = 11; // Range [start=11, end=30]
    // int key = 21; // Range [start=11, end=30]
    // int key = 31; // Range [start=31, end=100]
    // int key = 41; // Range [start=31, end=100]
    int key = 101; // Range [start=31, end=100]
    // etc.

    Range r = null;
    Map.Entry<Integer, Range> m = map.floorEntry(key);
    if (m != null) {
        r = m.getValue();
    }
    System.out.println(r);

.

Poiché l'albero è sempre ordinato per l'ordinamento naturale del limite del limite inferiore, tutte le vostre ricerche saranno al peggiore delle O (Log (N)).

Vuoi aggiungere qualche controllo sanitario per quando la chiave è completamente fuori limite (ad esempio, quando la chiave è oltre la fine della mappa, restituisce l'ultimo Range nella mappa), ma questo dovrebbe dareSei un'idea come procedere.

Answer 2

Supponendo che le tue ricerche siano della massima importanza, e puoi risparmiare o (n) memoria e circa o (n ^ 2) tempo di pre-elaborazione, l'algoritmo sarebbe:

.
• Introdurre un generatore di classe ObjectsInRange, che contiene: Avvio della gamma (int startOfRange) e un set di oggetti (Set<Object> objects)
• Introdurre un ArrayList<ObjectsInRange> oir, che conterrà ObjectsInRange ordinato dal startOfRange
• Per ogni Range r, assicurarsi che esistono ObjectsInRange (li chiamiamo a e b) in modo tale che a.startOfRange = r.start e b.startOfRange = b.end. Quindi, per tutti i ObjectsInRange x tra a, e fino a (ma non incluso) b, aggiungi r.obj al set di x.objects

La ricerca, quindi, è la seguente:

.
• Per Integer x, trova tale i che generanodicetagcode e oir[i].startOfRange <= x
• Nota: oir[i+1].startOfRange > x può essere trovato con Bisection in O (log n) TIME!
• I tuoi oggetti sono i

Answer 3

Se la raccolta è in ordine, è possibile implementare una ricerca binaria per trovare la portata giusta in O (log (n)) tempo.Non è così efficiente come hashing per collezioni molto grandi, ma se hai meno di 1000 o così gamme, potrebbe essere più veloce (perché è più semplice).