Supposons que vous ayez une large gamme d'entiers consécutifs en mémoire, dont chacun appartient exactement à une catégorie. Deux opérations doivent être O (log n): déplacer une plage d'une catégorie à une autre et trouver la catégorie compte pour une plage donnée.
Je suis à peu près sûr que la deuxième opération est résolue de manière triviale une implémentation correcte pour la première opération.
Chaque entiers commence dans une catégorie, j'ai donc commencé avec un ensemble de BST équilibré. Déplacement d'un sous-arbre d'une BST à une autre (par exemple, déplacer une plage à une catégorie différente) a un montant d'exécution équivalent à la fusion de deux BSTS, qui est O (N1 * N2) [ 1 ].
Ceci est trop lent (en Python et C n'est pas une option), et je ne pouvais pas comprendre un moyen de tirer parti de la structure inhérente de mes données afin de créer une opération de fusion BST efficace.
Je regarde maintenant AVL, rouge-noir et intervalles, des tas binaires et des TEAP. La comparaison de leurs propriétés est écrasante. Quelle structure dois-je utiliser?
Une demande donnée peut déplacer toute gamme possible d'entiers dans n'importe quelle catégorie. En d'autres termes, les gammes se chevauchent dans le sens de la catégorie catégorie (CAT3, I, J) . Ma solution actuelle crée un arbre avec un nœud pour chaque entier dans la gamme. C'est trop lent pour la taille de mon ensemble de données, donc je suis heureux de ré-architecte si une meilleure méthode.
(CAT1, 1, 10) suivi de la catégorie (CAT3, 5, 15) , mais sans chevauchement dans le Sens que tous les entiers seront exactement dans une catégorie à tout moment.
5 Réponses :
Vous pouvez avoir un dictionnaire pur python de la forme suivante Les touches sont le début de votre plage et les valeurs contiennent la fin de la plage et la catégorie de cette plage tombe dans . P> Étant donné que les dictionnaires ont une durée constante pour accéder aux éléments, vous pouvez écrire un code qui déplace une autre catégorie facilement et efficacement: dans le pire des cas, vous devrez vous restructurer en quelque sorte votre dictionnaire, si votre La gamme divise les gammes précédentes en deux ou plus. Par exemple, si vous souhaitez attribuer la plage de (4, 8) dans une autre catégorie, vous vous retrouverez avec: p> 1 : { "stop" : 3, "category" : "C1"},
4 : { "stop" : 8, "category" : "new category"},
9 : { "stop" : 19, "category" : "C23"},
etc
Comment stockez-vous deux gammes à partir du même entier? Je veux dire ce qui se passe si vous avez la plage (4, 8) et la plage (4, 10) ?
@Andreaambu à partir de la question: "Chacun appartient exactement à une catégorie"
@RPLNT Je pense que je manque du sujet là-bas, j'ai compris que c'était chacun gamme appartenir à une catégorie particulière, car l'OP définit les opérations en termes de gammes, mais dans cette phrase chacun signifie numéro . A l'air ambigus pour moi, merci.
@Andreaambu - Les gammes ne se chevauchent pas.
Aussi loin que j'ai compris la question que vous avez une gamme [A, B] et des requêtes de la forme -
1:8
1:4 5:8
1:2 3:4 5:6 7:8
1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8
Cela fonctionnera-t-il si je reçois des demandes de différentes gammes? Par exemple, catégorie (CAT3, 1, 10) , puis catégorie (CAT1, 5, 7) ? Les arbres segment doivent être des gammes statiques. Oui, le nombre de catégories est très petit (<10), comparé aux chaînes (millions de nombres avec des gammes de centaines de milliers).
Yup ça va. Les gammes resteront en effet statique. Vous devez simplement modifier les données de catégorie associées au nœud correspondant. J'ajoute un petit exemple dans la réponse existante à clarifier. Je ne sais pas si cela vous aidera, mais j'ai résolu un problème à l'aide d'un arbre de segment en C ++ (sans utiliser la propagation paresseuse bien que). Vous pouvez renvoyer le code de mise à jour et de requête là-bas. Ils changeront en fonction des exigences. Problème - lien code - link
Vous pouvez construire une structure d'arborescence sur des tableaux d'entiers consécutifs assez facilement, ce qui devrait aider à votre facteur constant. D'abord renuméroter la séquence pour commencer à 0 et s'arrête quelle est la plus petite puissance de deux qui est plus grande que la plage de la séquence.
considère maintenant l'arbre suivant formé à partir des entiers 0-7, que je peux contenir comme Quatre matrices, chaque tableau passant horizontalement. donné un numéro et un niveau, je peux trouver un décalage dans le tableau pour ce niveau, juste en déplaçant le nombre de numéros Montant en fonction du niveau. Dans chaque élément, je peux mettre un marqueur qui dit "mixte" ou donne la catégorie pour chaque élément à ou sous ce nœud de l'arborescence. Je peux résoudre ce que la catégorie d'un nœud est en train de suivre le chemin de la racine de l'arbre à une feuille, s'arrêtant dès que je vois un nœud qui ne dit pas "mixte". Je peux changer la catégorie pour un intervalle de chiffres dans le temps LG N, car j'ai au maximum deux nœuds à chaque niveau pour représenter la catégorie: Si j'en avais trois, deux d'entre eux auraient le même parent et je pouvais les fusionner. Vous devrez peut-être vouloir jouer un peu avec les bords pour obtenir des gammes voisines correctes, mais je pense que cela fonctionne dans LG N Time.
C'est une approche très intéressante! Cela nécessite beaucoup plus d'espace, mais cela ne devrait pas être un problème. J'espère que les deux opérations (catégorie de déplacement et de catégorie) sont O (log n) comme vous proposez.
La seule nouvelle idée ici est la structure de l'arborescence qui, comme vous dites que vous dites le meilleur espace de cas de la simplicité. Dans le cas où les catégories sont "un nombre pair" et "nombre impaire", il peut être compétitif dans l'espace. Pour les comptes de catégorie Vous devrez stocker des informations récapitulatives sur les nœuds d'arborescence, mais si vous pouvez résoudre ce problème avec l'une des structures d'arborescence que vous avez mentionnées, vous devriez être capable de le résoudre avec cela.
Hypothèses:
représente des gammes par Si vous devez déplacer une plage Scannez votre arborescence et mettre à jour chaque nœud / plage entièrement inclus dans La recherche d'arborescence est logarithmique et les scissions de nœud sont O (1).
Si votre arbre devient jamais trop fragmenté, vous pouvez envisager de fusionner des nœuds qui ont des gammes adjacentes. Ce sera toujours un parent et un enfant résultant d'un insert ou d'une scission; Les chèques et les jointures semblent toujours être o (1). (début, fin, catégorie) tuples. Les gammes ne se croisent pas pour que vous puissiez construire un arbre d'entre eux. C'est Loin plus économique qu'un arbre d'entiers individuels. Pour commander des gammes (c'est-à-dire des nœuds), vous pouvez simplement utiliser la valeur de démarrage, car elle est unique et ne peut pas appartenir à une autre plage.
[A, B] dans une autre catégorie, vous devez:
[a, b] plage. C'est un simple premier traversé de profondeur. Pendant la traversée
actuel_node.start B , arrêtez la recherche.
actuel_node.start> = A et actuel_node.end> b , vous devez diviser courant_node dans deux; [actuel_node.start, b] appartiendra à une nouvelle catégorie, le reste sera de sa catégorie d'origine.
actuel_node.start , vous avez divisé l'inverse.
Nous pouvons représenter les états actuels comme quelque chose comme:
0:cat1 200:cat2 500: cat0 700:cat6 800:cat1
Pourriez-vous clarifier le n ° 2? Je conviens que c'est O (k), mais je ne suis pas clair sur la manière dont il peut être O (1) amorti. Une valeur moyenne de K sera sur le même ordre que O (n), ce qui rendrait cette étape O (n).
@knite, il est amorti lorsque vous le considérez avec l'insertion. Chaque retrait doit être précédé d'une insertion. Donc, dépenser un supplémentaire O (1) pour enlever, c'est la même chose que de dépenser un supplémentaire O (1) pour l'insérer. L'insertion est déjà O (log n) afin que nous puissions le négliger.
@knite, la mise en œuvre honnêtement des structures de données complexes comme tend ainsi à ne pas bien fonctionner dans Python.
La plage est-elle enregistrée comme la liste des entiers ou comme tuple comme
(début, fin) ?Avant de commencer à mettre en œuvre des arbres, vous devriez essayer d'utiliser les types de données intégrés tels que les dicts et les ensembles. Ceux-ci sont très optimisés et très performants.
Donc, vous avez une liste avec des tuples [(Number1, Cat1), ....] ???
Je ne suis pas sûr de bien comprendre le problème, alors je vais d'abord poser quelques questions. Comment représentez-vous une gamme? Comme tous les entiers dans une structure de données ou juste premier + dernier (ou premier + compte)? Avez-vous déjà eu à scinder et rejoindre les gammes en faisant ces opérations? Qu'est-ce qu'une catégorie? Peut-il être décrit par un nombre? Qu'est-ce que cela signifie de se déplacer entre les catégories?
En déplaçant une plage d'une catégorie à une autre, vous voulez dire que pour une plage [x, y] 1) tous les entiers x <= i <= y seront dans la nouvelle catégorie, ou 2) uniquement des entiers x <= i <= y dans une autre catégorie sera dans la nouvelle catégorie?
Je ne sais pas si l'édition de mon entrée ping les commentateurs. J'ai clarifié le domaine de problème pour spécifier que je stocke actuellement un nœud par entier, mais je peux changer mon code pour stocker la plage (par exemple, nœud.start et node.end).
Alex - une catégorie peut être représentée de toute façon que vous le souhaitez. J'utilise actuellement une liste d'entiers Python pour représenter mes nœuds d'arbre, comme: [Catégorie de Val de gauche à droite], où les sous-arbres gauche et droit sont les sous-arbres gauche et droit. @jpalecek - Je reçois un nombre de demandes pour déplacer toute plage possible dans une autre catégorie. Ma question modifie-t-elle votre question?
Quelle est la portée de la gamme d'entiers consécutifs avec lesquels vous traitez?
Le lien que vous donnez réclamer O (N1 * N2) pour la fusion de 2 BSTS donne en réalité plusieurs réponses O (N1 + N2)! Essentiellement: Convertissez chaque BST en une liste triée en temps linéaire, fusionner ces listes dans Temps linéaire et convertissez le résultat à une BST en période linéaire.
@j_Random_hacker, il a besoin d'O (journal n). Le * est probablement une faute de frappe.