Comment trouver la gamme de ensemble contigu de plages pour nombre donné

Question

donc, tout simplement, c'est ce que je suis en train de faire:

J'ai une collection de Range les objets qui sont contigus (sans chevauchement, sans espace entre eux), contenant chacune un start et end int, et une référence à un autre objet obj.Ces plages ne sont pas de taille fixe (le premier pourrait être 1-49, la deuxième 50-221, etc.).Cette collection pourrait pousser à être assez grande.

Je suis l'espoir de trouver un moyen de regarder en haut de la gamme (ou plus précisément l'objet qu'elle les références) qui comprend un nombre donné, sans avoir à parcourir l'ensemble de la collection de la vérification de chaque plage pour voir si elle comprend le nombre.Ces recherches seront effectuées fréquemment, de sorte vitesse, et les performances est la clé.

Quelqu'un sait-il d'un algorithme/équation qui pourrait m'aider ici?Je suis en train d'écrire en Java.Je peux fournir plus de détails si nécessaire, mais j'ai pensé que je voudrais essayer de garder les choses simples.

Merci.

Answer 1

Si les sons comme vous voulez utiliser un TreeMap, où la clé est le bas de la fourchette, et la valeur de l' Range objet.

Ensuite, pour identifier la plage correcte, il suffit d'utiliser la floorEntry() méthode très rapidement obtenir le plus proche (inférieur ou égal) Range, qui devrait contenir la clé, comme suit:

    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);

Depuis l'arbre est toujours triés par ordre naturel des le bas de l'échelle des limites, toutes vos recherches seront au pire O(log(n)).

Vous aurez envie d'ajouter un peu de raison de vérifier si votre clé est complètement en dehors des limites (par exemple, lorsque l'on est au-delà de la fin de la carte, il retourne la dernière Range dans la carte), mais ce devrait vous donner une idée de la façon de procéder.

Answer 2

En supposant que vous avez les recherches sont de la plus haute importance, et vous pouvez épargner O(N) de mémoire et d'environ O(N^2) temps de prétraitement, l'algorithme serait:

• introduire une classe ObjectsInRange, qui contient:début de la plage (int startOfRange) et un ensemble d'objets (Set<Object> objects)
• introduire un ArrayList<ObjectsInRange> oir, qui contiendra ObjectsInRange triées par ordre de startOfRange
• pour chaque Range r, de s'assurer qu'il existe ObjectsInRange (appelons-la a et b) tels que a.startOfRange = r.start et b.startOfRange = b.end.Alors, pour tous ObjectsInRange x entre a, et jusqu'à (mais non compris) b, ajouter r.obj à leur x.objects ensemble

La recherche, alors, est comme suit:

• pour entier x, trouver de telles i que oir[i].startOfRange <= x et oir[i+1].startOfRange > x
• note: i peut être trouvé avec la bissection en O(log N) le temps!
• vos objets sont oir[i].objects

Answer 3

Si la collection est en ordre, vous pouvez mettre en œuvre une recherche binaire pour trouver la bonne gamme en O(log(n)) de temps.Ce n'est pas aussi efficace que le hachage pour de très grandes collections, mais si vous avez moins de 1000 plages, il peut être plus rapide (parce que c'est plus simple).