J'essaie de mettre en œuvre un algorithme qui se remplit. Le problème est que je ne suis pas sûr de quelle manière je devrais la mettre en œuvre E.g récursif - non récursif.
Je sais que chacun a ses défauts, mais l'un d'entre eux doit être plus rapide que l'autre. La récursive ouvre une nouvelle fonction sur la pile lorsque les non récursifs allouent 4 nouveaux points à chaque fois.
Exemple pour la non-itérative:
Stack<Point> stack = new Stack<Point>();
stack.Push(q);
while (stack.Count > 0)
{
Point p = stack.Pop();
int x = p.X;
int y = p.Y;
if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
continue;
byte val = vals[y, x];
if (val == SEED_COLOR)
{
vals[y, x] = COLOR;
stack.Push(new Point(x + 1, y));
stack.Push(new Point(x - 1, y));
stack.Push(new Point(x, y + 1));
stack.Push(new Point(x, y - 1));
}
}
4 Réponses :
Faire un masque - un réseau parallèle 2 DIM d'octets. Les octets de zones non cochées ont 0, pour la frontière fraîche de la zone inondée, il aura de la valeur 1. Pour l'intérieur de la zone inondée - Valeur 2. et conserver la liste des points de frontière courants aussi.
à une extrémité du cycle extérieur, vous avez le masque avec bordure courante marquée, dans une zone intérieure et extérieure et la matrice des points de bordure. Vous ne vérifierez donc que les nouveaux points uniquement à la frontière. Et tout en vérifiant la première arracheliste de points de bordure, vous créez la deuxième arraylist frontalier et le deuxième masque. À l'étape suivante, vous recréez le premier tableau de bord et masque. Aller de cette façon, nous pouvons utiliser un cycle simple BTW, vous avez oublié de vérifier les coordonnées des nouveaux points pour être sur la frontière dessinée ou à la frontière de l'ensemble du rectangle.
Quant au cyclisme à travers tous les points voisins, regardez mon algorithme ici pendant au lieu de récursivité, pour la structure de données que vous vérifiez à n'importe quelle étape est très simple.
Je sais pour un fait que c'est un mauvais conseil. La récursion est la plus rapide. BEAUCOUP. et la plus simple (50 lignes) si vous écrivez votre propre matrice de mémoire dans la boucle de récursion. C'est le plus léger. Les récursions peuvent être stockées dans des grilles non des arbres. Les grilles sont 1x taille de la mémoire image, les arbres sont 100 gygabytes. C'est aussi un peu vite. J'ai écrit un message à propos de la boîte. J'ai essayé de documenter mes recherches ici Unity3dmc.blogspot .COM / 2017/02 / ... Parce que cela dérive les codes ScanLine et sa programmation Zimpler plus petite ZE. JE Te LE Garantie Emphaition.
J'ai réalisé cet algorithme sur l'ordinateur avec la vitesse 340 opérations / seconde. Et ça a fonctionné. S'il vous plaît, expliquez-vous comment voulez-vous utiliser le marquage et la récursion des zones de frontière / de couleurs / sans espace? Je ne peux pas imaginer cela. Si vous voulez dire totalement une autre façon, vous avez mentionné votre réponse, essayez de l'expliquer aux personnes qui le lisent. Le test existant est illisible. Je n'étais pas un des bowards de votre message. Maintenant je suis aussi. L'efficacité d'un poste illisible est 0.
J'ai atteint 2 millions de pixels par seconde. La boucle récursive est d'environ 40 instructions de l'ASM et un PC peut exécuter des flops de 80 millions. D'où obtenez-vous 340 tops? S'il vous plaît commencer un message "Comment puis-je commander des tableaux de mémoire dans une récursion pour le remplissage des inondations" et je promets que je vais vous expliquer sa logique simple. La récursion est très facile: comparez les couleurs voisines avec «Instruction IF-VAL», Marquez Résultats dans les tableaux, recueil à nouveau, lecture des tableaux. Qu'est-ce que tu ne comprends pas? Démarrer une requête s'il vous plaît.
@ COM.PREHENSIBLE 1. Parler de la vitesse pratique de l'algorithme sans mentionner la vitesse de Comp est insensée. 2. Expliquez votre méthode dans votre réponse, s'il vous plaît. 3. La récursion n'est pas une commande d'assembleur. Il est toujours basé sur des opérations plus primitives. Et cela ne peut être plus simple que dans le sens du volume du code écrit et / ou de la lisibilité. Dans d'autres aspects, il réduisait toujours l'efficacité de l'algorithme. 4. 340 op / sec? Il y avait des moments où la vitesse de Comps était plus faible. Probablement, je suis un peu plus long que vous dans la programmation :-)
@ COM.PREHENSIBLE essayant d'expliquer mieux mon algorithme, j'ai remarqué que dans un aspect, vous avez raison. Ici, nous pouvons utiliser la récursion sans pertes notables. Et le code sera plus simple dans la compréhension. Mais nous devrons créer des structures de données plus complexes. Et, bien sûr, la récursivité ne sera jamais plus efficace, même un peu. Ça ne peut tout simplement pas.
Vous êtes très gentil, vous prétendez 340 opérations par seconde. Je gère 4 000 000 opérations par seconde, 1000 fois plus rapidement que votre version. Dans un aspect, c'est probablement la fin de l'histoire pour votre mise en œuvre générique. Désolé, je vous ai révoqué cependant, car j'avais 2 descendances anonymes pour une réponse éprouvée des codeurs boiteux, j'étais un peu ennuyé et j'ai ensuite évanoui toutes les réponses qui sont 1000 fois plus lentes que ma version du code: YouTube.com/watch?v=4HQ1WA4SL4C&feature=YOUTU.be Vous avez 340 opérations par seconde, Single I7 Core peut faire 15 gigaflops ?!
@ COM.PREHENSIBLE 340FLOPS était la vitesse de l'ordinateur, non de la version ou de l'algorithme. Et désolé, votre logique ou votre compréhension est tellement endommagée, je ne peux pas continuer la discussion, c'est une perte de temps. Et mon moins n'était pas anonyme.
Un remplissage d'inondation récursif peut déborder la pile, si l'image est complexe. Utilisez le remplissage des inondations non récursives.
Si vous vous souciez des allocations, vous pouvez représenter un point comme une valeur emballée de type long et codez votre propre aspiration longue qui stocke intérieurement les valeurs longues dans un tableau.
Le non-récursif est plus lent, car il a beaucoup de conditions. Utilisez des doublons de votre toile pour stocker les étapes de votre récursivité. Il devient l'adressage de la mémoire en vitesse de traitement brute à la vitesse de l'ASM.
Ce semble être le La mise en œuvre la plus efficace d'un remplissage d'inondation J'ai trouvé ...
i mentionne la technique de remplissage frontière mentionnée dans Cette réponse comme une bonne, mais pas aussi bonne que la quickfill. < / p>
Ordinateurs Processus XY Loops et matrices 2D de manière très efficace.
Vérifiez cette vidéo pour voir ce qui se passe si vous mettez la routine récursive standard dans une boucle:
https://www.youtube.com/watch?v=lvacRisl99Y
Au lieu d'utiliser une logique complexe pour suivre les espaces voisins précédemment vérifiés, vous pouvez avoir un tableau 2D qui enregistre tous les espaces vérifiés. La lecture de la matrice vérifiée est de 2-3 instructions: si le pixel [23,23] est vérifié, puis remplissez-le et vérifiez qu'il s'agit de voisins.
C'est vraiment dépendant de la mise en œuvre.
Vous devriez dire quelle langue vous utilisez. En C ou Java, vous voudriez la solution itérative.
C ++ principalement .. S'il y a un moyen plus rapide d'utiliser cuda / omp ..
N'utilisez pas d'une pile, car l'ordinateur peut effectuer 20 copies de n'importe quel pixel dans la liste des piles et réactualiser les instructions 20 fois. Écrivez votre propre matrice 2D pour enregistrer des espaces vérifiés et sur deter Array Wich enregistre l'image remplie complète, puis lisez-les et écrivez-les à l'aide de ce système de boucle: youtube.com/watch?v=lvacrisl99y