J'ai un grand tableau avec 100 membres. Les premiers membres X sont 0, et le reste est 1. Trouver X.
Je résolvez-le par une recherche binaire: Vérifiez l'élément 50, s'il s'agit de 0 - Vérifiez le membre 75, etc. jusqu'à ce que je trouve adjacent 0 et 1.
Je cherche un algorithme optimisé pour le même problème en 2 dimensions:
J'ai une matrice en 2 dimensions 100 * 100. Ces membres qui sont sur des lignes 0-X et sur des colonnes 0-y sont 0 et le reste sont 1. Comment trouver Y et X?
4 Réponses :
Exécutez votre recherche binaire deux fois. Premier Déterminez X en exécutant une recherche binaire sur la dernière ligne, puis déterminez Y en exécutant une recherche binaire sur la dernière colonne.
Solution simple: Allez d'abord dans la direction X, puis dans la direction en Y.
chèque (0,50); Si c'est 0, vérifiez (0,75); Jusqu'à ce que vous trouviez adjacent 0 et 1. Ensuite, passez à la direction de y à partir de là.
deuxième solution:
Vérifiez le membre (50,50). S'il est 1, chèque (25,25), jusqu'à la recherche de 0. Continuez, jusqu'à ce que vous trouviez adjacent (x, x) et (x + 1, x + 1) qui sont 0 et 1. Testez (x, x +1) et (x + 1, x). Ni l'un ou l'autre d'entre eux ne sera 1. Si vous n'êtes pas non plus, vous avez terminé. Si seulement un, disons par exemple (x + 1, x), vous savez que la taille de la boîte est comprise entre (x + 1, x) et (100, x). Utilisez une recherche binaire pour trouver la hauteur de la boîte.
edit : Comme Chris a souligné, il semble que l'approche simple soit plus rapide.
deuxième solution (modifiée):
Vérifiez le membre (50,50). S'il est 1, chèque (25,25), jusqu'à la recherche de 0. Continuez, jusqu'à ce que vous trouviez adjacent (x, x) et (x + 1, x + 1) qui sont 0 et 1. Testez (x, x +1). S'il est 1, alors effectuez une recherche binaire sur la ligne (x, x + 1) ... (x, 100). Sinon faire une recherche binaire sur la ligne (x, x) ... (100, x).
Même alors je frappe probablement un cheval mort ici. Si ce sera plus rapide, alors par une quantité négligeable. Ceci est juste pour le plaisir théorique. :)
EDIT 2 Comme Fezvez et Chris l'a dit, la recherche binaire divise l'espace de recherche dans deux les plus efficaces; Mon approche divise la zone à 1/4 et 3/4 morceaux. FEZVEZ a souligné que cela pourrait être corrigé en calculant le facteur de division au préalable (mais ce serait un calcul supplémentaire). Dans la version modifiée de mon algorithme, je choisis la direction où aller (direction X ou Y), ce qui divise efficacement l'espace de recherche en deux, puis effectuez une recherche binaire. Pour conclure, cela montre que cette approche sera toujours un peu plus lente. (et plus compliqué à mettre en œuvre.)
Merci, Igor Oks, pour une question intéressante. :)
J'aime cette approche. Cela fait effectivement la recherche binaire sur X et Y en même temps jusqu'à ce que vous ayez déterminé un, puis continue de trouver l'autre ayant déjà réduit la région de recherche. Plus efficace que de faire x et y indépendamment.
@Chris: Il n'est certainement pas plus efficace que de faire deux recherches de manière indépendante. C'est parce que l'espace de recherche est supérieur à Quadraticaly. Donc, la grande complexité théorique o est la même journal (n * n) == 2 * journal (n). Cette solution est tout simplement simple et plus compliquée. Je pense que cette solution est moins efficace que deux recherches indépendantes, car elle ne divise pas l'espace de recherche de manière égale à chaque itération.
Ce n'est peut-être pas clair de mon message, mais je l'ai entendu comme une recherche binaire. (diviser l'espace de recherche également). En outre, la grande complexité est une chose et le temps d'exécution d'une autre. Je supposerais que ce programme est x fois plus rapide en moyenne, où 1
Peut-être. Je garde les mathématiques confuses dans ma tête. Je suis d'accord qu'ils sont tous les deux des mêmes ordres, mais je me sens toujours comme si cette méthode prendra moins de comparaisons. Je soupçonne que le seul pour moi de me satisfaire serait d'écrire et de courir et de voir comment cela ressort. Peut-être que ce soir ... Je ne pense pas que mon patron approuverait de moi le doigt sur le temps de travail. :)
Et je vais essayer d'écrire une preuve. Ne devrait pas non plus faire cela en temps de travail :)
Ummm ... ne dit pas à mon patron mais j'ai écrit un programme pour tester cela ... On dirait que l'approche indépendante est plus rapide. On dirait que ceci est en grande partie dû aux 2 tests supplémentaires nécessaires pour déterminer si la chose que vous avez trouvée sur la diagonale est le bord de la X ou Y. Lorsque votre zone de recherche augmente de taille, ces 2 deviennent moins significatifs mais suffisamment pour le balancer il semble.
En pensant à une preuve parce que le cas dépendant utilise toujours 2 autres chèques pour trouver le premier résultat que les connaissances acquises doivent être meilleures que celles qui pourraient être gagnées par 2 recherches supplémentaires sur l'indépendante. La recherche binaire est suffisamment efficace que 2 recherches supplémentaires signifient que beaucoup de connaissances supplémentaires sont nécessaires et je ne pense pas que vous obteniez cela.
Je pense que vous êtes dirigé, Chris. Mon algorithme pourrait être modifié pour ne faire que 1 chèque au lieu de 2: test seulement (x, x + 1) == 1 et si c'est faux, puis effectuez une recherche binaire sur (x, x) ... (100, x) ; sinon faire une recherche binaire sur (x, x + 1) ... (x, 100). J'ai essayé de prouver ce qui est plus rapide, mais je ne peux pas sembler le comprendre. Ils semblent vraiment proches les uns des autres - Chris, pouvez-vous vérifier qui est plus rapide dans la pratique?
Je pense que Fèsezz a dit qu'il est le mieux dans sa réponse que pour ce faire, tout ce que vous avez à faire est de diviser l'espace de recherche en deux à chaque étape et de le jeter. La méthode X d'abord que Y a-t-elle de manière très simple et je pense que quelque chose d'autre, surtout quelque chose qui nécessite des contrôles supplémentaires pour déterminer quelle section à jeter, ne peut pas être plus rapide.
Utilisez une recherche binaire sur les dimensions et le boîtier 1D:
Je suis vraiment désolé pour le poste long et convoluté que j'ai fait ci-dessous. Ce que le problème consiste fondamentalement consiste à trouver un point dans un espace contenant 100 * 100 éléments. Le mieux que vous puissiez faire est de diviser à chaque étape de cet espace en deux. Vous pouvez le faire de manière convoluée (celle que j'ai faite dans le reste de la poste), mais si vous réalisez qu'une recherche binaire sur l'axe X divise toujours l'espace de recherche en deux à chaque étape (la même chose va pour le y Axis) Ensuite, vous comprenez que c'est optimal.
Je laisse toujours la chose que j'ai faite, et je suis désolé de faire certaines affirmations péremptoires.
Cependant, si vous voulez un algorithme optimal, vous pouvez rechercher la limite sur x et sur y en même temps. (Vous devez noter que les deux algorithmes ont la même complexité asymptotique, mais l'algorithme optimal sera toujours plus rapide)
Dans tous les graphiques suivants, le point (0, 0) est dans le coin inférieur gauche.
Si vous choisissez le point (la croix noire) et que le résultat est de 1 (lignes rouges), cela signifie que le point que vous recherchez peut pas être dans l'espace gris (donc doit être dans la zone blanche restante)
D'autre part, si la valeur est 0 (lignes bleues), cela signifie que le point que vous recherchez peut Le point que vous recherchez est soit dans le rectangle 1, 2 ou 3. Vous devez simplement vérifier les deux coins du rectangle 3 pour savoir lequel du rectangle 3 est le bon.
L'algorithme est donc ce qui suit:
Remarque où sont le coin inférieur gauche et supérieur du rectangle avec lequel vous travaillez.
une recherche binaire Vérifiez les 2 autres coins du rectangle 3 (vous avez déjà connu déjà les valeurs des deux coins sur la diagonale) Il est possible de vérifier qu'un seul coin pour connaître le bon rectangle (mais vous allez avoir à vérifier les deux coins si le rectangle droit est le rectangle 3)
Déterminez si le point que vous recherchez est dans le rectangle 1, 2 ou 3
Répétez en réduisant le problème au bon rectangle jusqu'à ce que le rectangle final soit réduit à un point: c'est la valeur que vous recherchez
Edit: Si vous souhaitez que l'optimalité de Supremum, vous n'ayez pas le moment où vous choisissez le point (50, 50), vous ne coupez pas l'espace dans une partie égale. On a trois fois plus grand que l'autre. Idéalement, vous choisirez un point qui coupe l'espace en deux régions égales (zone sage)
Vous devez calculer une fois au début la valeur de
facteur = (1.0 - 1.0 / sqrt (2.0)) . Ensuite, lorsque vous souhaitez couper les valeurs Bewteen A et b , choisissez le point de coupe comme A + facteur * (B-A) . Lorsque vous coupez le rectangle initial 100x100 au point (facteur 100 *, 100 * facteur), les deux régions auront une zone (100 * 100) / 2, la convergence sera donc plus rapide.
Cela semble comme une meilleure explication de l'algorithme suggéré par Rauni. Mais comme je l'ai noté, je me demande s'il est vraiment plus rapide que deux recherches linéaires. Il semble que ce soit juste plus compliqué.
Très drôle ce que vous avez dit, et oui, ils sont similaires. Ce que Rauni Algorithm est qu'il continue à rechercher les lignes bleues et rouges jusqu'à ce que les rectangles restants soient de largeur de 1 "pixel". Ensuite, il cherche (x, x + 1) et (x + 1, x), qui est identique à la recherche des 2 autres coins du 3ème rectangle. Maintenant, en ce qui concerne la complexité, je ne suis pas trop sûr. Je pense simplement que lorsque vous faites une recherche linéaire, vous défausez la moitié des informations (vous vous souciez de l'autre axe) alors que voici toutes les informations sont prises en compte.
@FezVez: Vos commentaires Dans la modification du fait que la recherche binaire veut principalement diviser l'espace en deux est une excellente perspicacité que j'avais du mal à venir à venir. +1 pour cela seul. :)
@Chris: Merci! Eh bien, je suis assez énervé pour avoir tellement cherché pour rien, mais j'étais assez heureux de souligner le fait que ce que vous voulez vraiment faire à chaque itération est de diviser l'espace en deux! Merci pour le soutien! =)