Comment trouver la gamme de ensemble contigu de plages pour nombre donné
-
20-12-2019 - |
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.
La solution
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.
Autres conseils
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 contiendraObjectsInRange
triées par ordre destartOfRange
- pour chaque
Range r
, de s'assurer qu'il existeObjectsInRange
(appelons-laa
etb
) tels quea.startOfRange = r.start
etb.startOfRange = b.end
.Alors, pour tousObjectsInRange x
entrea
, et jusqu'à (mais non compris)b
, ajouterr.obj
à leurx.objects
ensemble
La recherche, alors, est comme suit:
- pour entier
x
, trouver de tellesi
queoir[i].startOfRange <= x
etoir[i+1].startOfRange > x
- note:
i
peut être trouvé avec la bissection en O(log N) le temps! - vos objets sont
oir[i].objects
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).