Un algorithme d'intersection de distance meilleur que O (n)?
https://stackoverflow.com/questions/303591
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
L'intersection de plages est un problème simple mais non trivial.
On a déjà répondu à deux fois:
La première solution est O (n) et la deuxième solution concerne une base de données (inférieure à O (n) bien sûr).
J'ai le même problème, mais pour un grand n et je ne suis pas dans une base de données.
Ce problème semble très semblable à Stockez des points 2D pour retrouver rapidement ceux qui se trouvent à l'intérieur d'un rectangle , mais je ne vois pas comment il correspond.
Dans quelle structure de données stockeriez-vous l'ensemble des plages, de sorte qu'une recherche sur une plage coûte moins que O (n)? (Crédit supplémentaire pour l’utilisation des bibliothèques disponibles pour Java)
EDIT:
Je souhaite obtenir un sous-ensemble de toutes les plages qui se croisent, ce qui signifie que la plage de recherche pourrait croiser plusieurs plages.
La méthode qui doit être inférieure à O (n) en Java est la suivante:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
Où Range est juste une classe contenant une paire d'int et de début.
Ce n’est pas une question impossible, j’ai déjà la solution, je voulais juste savoir s’il existait un moyen plus simple / plus simple de le faire
La solution
L'approche standard consiste à utiliser un arbre d'intervalle .
En informatique, un arbre d'intervalle est une structure de données arborescente destinée à contenir des intervalles. Spécifiquement, cela permet de trouver efficacement tous les intervalles qui se chevauchent avec un intervalle ou un point donné. Il est souvent utilisé pour les requêtes de fenêtrage, par exemple, pour rechercher toutes les routes sur une carte informatisée dans une fenêtre rectangulaire ou pour rechercher tous les éléments visibles dans une scène en trois dimensions. Une structure de données similaire est l'arborescence des segments.
La solution la plus simple est de visiter chaque intervalle et de vérifier s’il recoupe le point ou l’intervalle donné, ce qui nécessite O (n) temps, n étant le nombre d’intervalles de la collection. Etant donné qu'une requête peut renvoyer tous les intervalles, par exemple si la requête est un grand intervalle recoupant tous les intervalles de la collection, ceci est asymptotiquement optimal; Cependant, nous pouvons faire mieux en considérant des algorithmes sensibles à la sortie, où le temps d'exécution est exprimé en termes de m, le nombre d'intervalles produits par la requête. Les arbres à intervalles ont un temps de requête de O (log n + m) et un temps de création initial de O (n log n), tout en limitant la consommation de mémoire à O (n). Après la création, les arbres d'intervalle peuvent être dynamiques, permettant l'insertion et la suppression efficaces d'un intervalle dans O (log n). Si les extrémités des intervalles se situent dans une plage entière petite (par exemple, dans la plage [1, ..., O (n)]), il existe des structures de données plus rapides [1] avec le temps de prétraitement O (n) et le temps de requête O ( 1 + m) pour signaler m intervalles contenant un point de requête donné.
Autres conseils
Modifier: On dirait que cette solution est plus ou moins un arbre d'intervalle . Une implémentation plus complète d'un arbre d'intervalle est disponible ici . / p>
class TreeNode
{
public:
long pivot;
List<Range> leaves; //Any ranges that intersect the pivot
TreeNode left; //Tree nodes that fall to the left of the pivot
TreeNode right; //Tree nodes that fall to the right of the pivot
};
Préparer O (n log n):
- Créer la liste des plages
- Choisissez les points de pivot (éventuellement en utilisant une liste triée des dates de fin.) ??
- Construisez votre arbre.
Recherche:
- Utilisez la recherche binaire pour trouver le premier pivot qui est > = TestRange.End
-
Parcourez l’arbre jusqu’au pivot > TestRange.Start
2a. Ajoutez les feuilles à votre résultat.
Exemple:
Gammes:
- 0 - 2
- 1 - 2
- 2 - 3
- 1 - 4
- 2 - 4
- 0 - 5
- 4 - 5
- 2 - 6
- 3 - 7
Arbre:
4
--------------+------------------
3 | 7
| 1-4 |
| 2-4 |
| 0-5 |
| 4-5 |
---------+------ --------+--------
2 | null 6 | null
-----+---- 2-3 ----+---- 3-7
null | null null | null
0-2 2-6
1-2
Plages non superposées:
Préparer O (n log n):
- Créez un tableau / vecteur des plages.
- Trier le vecteur par la fin de la plage (séparer les liens en triant par le début de la plage)
Recherche:
- Utilisez la recherche binaire pour trouver la première plage avec une valeur finale de > = TestRange.Start
-
Iterator commençant à la recherche binaire jusqu'à ce que vous trouviez un début > TestRange.End:
2a. Si la plage actuelle est comprise dans la plage de test, ajoutez-la à votre résultat.
Cela dépend de votre problème exact. Dans la question liée, les plages distinctes, aucune partie commune et la plage recherchée peuvent s'étendre sur plusieurs plages. Si votre problème est le même, c'est vraiment facile: Prenez un tableau des plages, triez-les en fonction de leurs valeurs les plus basses (comme elles ne se chevauchent pas, ce serait également le même ordre que si elles étaient triées en fonction de leurs valeurs supérieures).
Maintenant, il suffit de faire une recherche par bin pour la valeur inférieure de votre cible (ou inférieure si elle n’est pas exacte) et une autre pour la valeur supérieure de la cible (ou supérieure si elle n’est pas exacte). Les index résultants sont les plages couvertes. Vous devez vérifier si les plages des index sont elles-mêmes incluses ou exclues, mais il ne s'agit que de 2 contrôles. Complexité globale O (log n).
Plages qui se chevauchent:
Préparer O (n log n):
- Créez un tableau / vecteur des plages.
- Trier le vecteur par la fin de la plage (séparer les liens en triant par le début de la plage)
-
Créez un second vecteur d'ints. Ceci représente le moment où vous pouvez arrêter de chercher.
int stop[size]; stop[size-1] = Ranges[size - 1].start; for (int i = size - 2; i >= 0; i--) { stop[i] = min(Ranges[i].start, stop[i+1]); }
Recherche:
- Utilisez la recherche binaire pour trouver la première plage avec une valeur finale de > = TestRange.Start
-
Itérateur commençant à la recherche binaire jusqu'à stop [i] > TestRange.End:
2a. Si la plage actuelle est comprise dans la plage de test, ajoutez-la à votre résultat.
Si les plages se chevauchent et que l'on souhaite récupérer toutes les plages qui chevauchent (ou contiennent) une plage cible donnée, la plupart des solutions ci-dessus ne semblent pas fonctionner.
Comme certains l'ont souligné, si (dans le pire des cas) toutes , les plages intersectent la plage cible (par exemple, si la plage cible est {0..MAXINT} ou similaire), alors bien sûr, il faut O (n) pour renvoyer les n plages.
Mais ce n’est pas le cas intéressant et typique / moyen, où seulement un très petit% des n plages totales intersectent la plage cible? Appelez le numéro que font intersectez "m". - dans ce cas, vous pourriez éventuellement être capable de faire aussi bien que O (m). Et si n = 10 ^ 9 et m = 10, c'est une différence décisive.
Prenons le cas simple d’un document texte comportant plusieurs régions marquées pour leur "type". - Peut-être souhaitez-vous rechercher toutes les unités annotées qui contiennent ou intersectent une plage de texte contiguë donnée (par exemple, un paragraphe). En HTML, XML ou similaires, ceux-ci ne peuvent être que des ancêtres du ou des nœuds de texte contenant au moins certains caractères de la plage cible. Dans les représentations typiques avec des pointeurs parents dans chaque nœud, c'est O (m) - bien meilleur que O (n), en particulier parce que m est (pour des plages cibles courtes ou synchrones) simplement la profondeur d'imbrication de l'arbre, qui tend même à être inférieure à ln (n) car, dans la pratique, les gros documents XML ne sont pas plus épais.
Le cas intéressant est plus difficile: que se passe-t-il si vos "éléments" ne formez pas un arbre comme dans XML, mais peut se chevaucher comme dans MECS, CLIX, LMNL et quelques autres systèmes? Vous souhaitez toujours rechercher toutes les régions / "éléments". qui chevauchent votre cible, mais ils ne sont pas aussi faciles à organiser.
D’autre part, vous devriez pouvoir très bien vous en tirer, car dans de nombreuses applications, les plages de marquage sont le plus souvent petites - il y a beaucoup plus de mots, de phrases et de paragraphes dans un livre que de chapitres. Ainsi, même s’il peut y avoir un très grand nombre de plages qui commencent avant la cible et un nombre énorme qui se terminent après, l’intersection sera en moyenne très petite.
Je pense que c'est ce à quoi le questionneur initial voulait en venir et je crains de ne pas avoir vu de réponse à ce problème. Si ce n’est pas l’objet de la question initiale, alors j'aimerais la poser comme une nouvelle question.
On dirait que vous avez besoin d’une classe qui implémente l’interface SortedSet. TreeSet est l'implémentation fournie avec l'API principale.
Ayez un ensemble contenant les plages triées par la valeur la plus basse et l'autre par la plus haute valeur.
Vous pouvez ensuite implémenter l'équivalent de l'algorithme de base de données à l'aide des jeux en mémoire.
Quant à savoir si cela est réellement plus rapide que O (n), je ne saurais le dire.
Tout comme un arbre quad fonctionne pour un ensemble de points 2D, un simple arbre binaire devrait fonctionner dans ce cas. Construisez un arbre avec vos gammes.
Pour expliquer davantage: Chaque nœud de l'arborescence contient deux entiers, le début et la fin de la plage et les deux enfants s'il ne s'agit pas d'un nœud feuille. Pour rechercher les plages couvertes par votre plage d’entrée, commencez en haut de l’arbre
- if the node range intersects the input range:
- if it's a leaf node, then add the range to your result list
- if it's not a leaf node, then traverse down to the child nodes and repeat this process.
Cela devrait être O (logN)
Autres détails: L'arbre binaire serait structuré comme une version 1-d d'un arbre quad. Chaque nœud aurait trois entiers (désolé j'en ai dit deux ci-dessus, mais maintenant je réalise que vous en avez besoin de trois), le plus bas représentant la valeur la plus basse de la plage la plus basse située sous ce nœud, le plus haut représentant la valeur la plus élevée de la plage la plus basse noeud, et le pivot. L'enfant de gauche s'étendrait du plus bas de ce nœud à son pivot. Le bon enfant s'étendrait du pivot de ce nœud au plus élevé de ce nœud. S'il n'y a qu'une seule plage allant de " le plus bas " Pour "plus haut", vous n'auriez pas de pivot et ce serait une feuille. Idéalement, vous choisiriez les pivots de chaque nœud pour maintenir l’arbre en équilibre.
Lorsque j'ai eu ce problème, j'ai utilisé un tableau trié de plages et une recherche binaire pour rechercher des intersections. C’est (je crois) une performance de O (log n), avec un peu de surcharge pour traiter les plages qui se chevauchent.
La réponse à votre question peut, je pense, être déduite du code ci-dessous, mais en deçà de l'insertion. Je présente l'ensemble du code pour éviter toute confusion liée à la diversité du contexte. J'avais besoin d'insérer une plage de points de code Unicode dans une liste de plages de points de code.
- EDITER -
L’adaptation du code ci-dessous pour déterminer les intersections de plusieurs plages implique une recherche simple en avant à partir du point d’insertion jusqu’à la découverte d’une plage qui ne se coupe plus.
- END EDIT -
La classe Range contient:
final int lower; // lower end of range
final int upper; // upper end of range
public int compareTo(Object obj) {
if(obj==null) { return -1; }
Range oth=(Range)obj;
if(lower<oth.lower) { return -1; }
if(lower>oth.lower) { return 1; }
if(upper<oth.upper) { return -1; }
if(upper>oth.upper) { return 1; }
return 0;
}
Insertion de plage:
public Builder addRange(int fir, int las) {
if(fir!=-1) { fir&=0x001FFFFF; }
if(las!=-1) { las&=0x001FFFFF; }
if(codepoints==null || codepoints.length==0) {
codepoints=new Range[]{new Range(fir,las)};
}
else {
int idx=Range.findChar(codepoints,fir);
int ins=(idx<0 ? -(idx+1) : idx);
if(idx<0) {
if (ins>0 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); } // new range adjoins the following range (can't overlap or idx would be >=0)
else if(ins<codepoints.length && las>=(codepoints[ins ].lower-1)) { idx=ins; } // new range overlaps or adjoins the following range
}
if(idx<0) {
codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
}
else {
boolean rmv=false;
for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
codepoints[xa]=null;
rmv=true;
}
if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
}
if(rmv) { codepoints=Range.removeNulls(codepoints); }
}
}
return this;
}
Recherche binaire:
static int findChar(Range[] arr, int val) {
if(arr.length==1) {
if (val< arr[0].lower) { return -1; } // value too low
else if(val<=arr[0].upper) { return 0; } // value found
else { return -2; } // value too high
}
else {
int lowidx=0; // low index
int hghidx=(arr.length-1); // high index
int mididx; // middle index
Range midval; // middle value
while(lowidx<=hghidx) {
mididx=((lowidx+hghidx)>>>1);
midval=arr[mididx];
if (val< midval.lower) { hghidx=(mididx-1); } // value too low
else if(val<=midval.upper) { return mididx; } // value found
else { lowidx=(mididx+1); } // value too high
}
return -(lowidx+1); // value not found.
}
}
