Étant donné la description de deux images prises à une minute d'intervalle qui repèrent la présence d'un drone ou d'un oiseau, vous souhaitez identifier le plus grand sous-ensemble de points repérés sur la première image, que l'on peut retrouver sur la deuxième image, après un déplacement identique. On nommera ce sous-ensemble l'essaim de drones. Notez qu'il est possible que l'essaim ne se soit pas déplacé entre les deux images radar.
Entrée
La première ligne de l'entrée contient deux entiers : L le nombre de lignes et C le nombre de colonnes. Les 2*L lignes suivantes contiennent C entiers valant 0 ou 1, séparés par des espaces. Les L premières lignes contiennent la grille de la première image radar, alors que les L suivantes représentent la deuxième. À une position donnée, un 1 représente la présence d'un drone ou d'un oiseau à cette position, et un 0 représente une absence d'objet.
Sortie
Sur la première ligne de la sortie, vous devez afficher un entier : le nombre de points du plus grand groupe d'objets pouvant s'être déplacé de la même manière. Vous devez afficher ensuite autant de lignes qu'il y a de points dans ce groupe. Sur chacune de ces lignes, vous devez afficher les coordonnées dans la deuxième image d'un point de ce groupe, en écrivant le numéro de la ligne, un espace, puis le numéro de la colonne. Ces numéros de ligne et de colonne doivent être comptés à partir de 1, les coordonnées de la case en haut à gauche sont ainsi affichées comme "1 1". Vous pouvez choisir n'importe quel ordre, mais chaque point du groupe doit être présent exactement une fois
Limites de temps et de mémoire (C++)
Temps : 1 s sur une machine à 1 GHz.
Mémoire : 64 000 ko.
Contraintes
1 <= L, C <= 500 et 0 <= U <= 1000, où U est le nombre de cases à 1 dans une image.
Exemple
Sur l'image ci-dessus, on a mis en évidence deux groupes qui se déplacent : l'un est représenté en rouge, l'autre est représenté en vert. Le groupe rouge est le plus gros dont tous les points se déplacent de la même manière. Outre ces deux groupes, il y a d'autres groupes, plus petits, comme de nombreux « groupes » de taille 1, en blanc.
Mon analyse du sujet est la suivante : Au vu des contraintes de temps, je devrais trouver un algorithme de complexité maximum O(L*C*U).
Cependant je n'ai aucune idée de comment aborder ce sujet simplement avec une telle contrainte sur la complexité en temps, parce que boucler sur tous les sous-ensembles possibles n'est pas efficace. Peut-être que partir de l'ensemble entier puis retirer les éléments incompatibles au fur et à mesure est une piste intéressante, mais je ne sais pas comment faire...
Si vous avez des conseils je suis preneur !
Je suis tout nouveau sur le forum donc soyez indulgents s'il vous plaît
C'est pas super claire comme définition, et on n'a pas accès aux pages du cite sans avoir à se connecter, tout ça tout ça.
Si, par déplacement on entent une translation dans le plan, c'est plus jouable que l'application d'une matrice de transformation totalement arbitraire.
Si c'est une translation, bin moi, je commencerai par la méthode "naïve", qui n'est déjà pas si simple à faire que cela.
Déjà calculer l'ensemble des groupes possibles, c'est pas si trivial que ça.
- Edité par bacelar 4 mai 2020 à 17:41:49
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
Oui, c'est bien une translation (toutes les cases d'un même groupe ont leurs abscisses qui augmentent (ou diminuent) de x, et leurs ordonnées qui augmentent (ou diminuent) de y.
Justement, je ne sais pas comment calculer l'ensemble des groupes possibles, aurais-tu une idée ?
Si je me souviens bien de mes cours (ça fait vraiment longtemps ...), une détection de forme (et donc de déplacement entre deux images) ça se faisait avec une convolution (à deux dimension pour une image).
Si tu arrives à te dire que ce que tu cherches à suivre, c'est la "flèche rouge" (un carré de 5 pixels sur 5 pixels), il te 'suffit' de faire une convolution de ces 5 X 5 pixels sur l'ensemble de ton images (dans les 3 couleurs ? en Noir et blanc ? commençant par faire de la détection de contour, ...), et là où il y a le maximum pour ton produit de convolution, tu as la localisation de ton mobile.
S'il n'y a que peu de pixels qui change en dehors du mobile, la convolution entre l'ensemble des deux l'image doit être encore une méthode valide, en trouvant un second maximum ... Faudrait trouver un cours sur le traitement numérique de l'image.
Pour aller plus vite, Tu devais commencer ta convolution sur les 2 images sans décalage, puis ensuite une convolution entre les images à +/- 1 pixel (8 intégrales/sommes), +/- 2 pixel (16 intégrales/sommes), +/- 3 pixel (20 intégrales/sommes), ...
Dans l'industrie, c'est réalisé par un écartomètre. Quand tu est dans l'optique, il faut le faire 24 fois par seconde, au rythme de la caméra, donc généralement c'est hard codé (FPGA ou GPU) : Ça vaut la peau du cul quand on veux que ce soit précis et robuste, ... et généralement, c'est pas gentil !
Connaissant les zozos de France IOI, des matheux plus que des informaticiens, je ne pense pas qu'ils ont fait leur exercice pour qu'on sorte la grosse Bertha de calcul de convolution et autres traitements du signal.
Faire les appariements de point, c'est plutôt simple, tu fais toutes les combinaisons de points de même valeur, en commençant par les plus grosses et tu les recherches dans l'image cible, etc...
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
>Donc pour faire les appariements il faut faire toutes les combinaisons des points valant 1 ?
Potentiellement, comme on veut que le plus gros, on commence par les plus plus gros/déséquilibrés.
On commence par l’appariement qui contient tous le 1, donc de taille U.
Puis ceux qui découpent l'ensemble des "1" en 2 groupes, en commençant pour ceux qui découpent en un groupe de "U-1" éléments et l'autre de juste l'élément restant. etc...
Vous pouvez assez facilement construire des structures annexes, comme des index, des sommes partielles, etc... pour accélérer les comparaisons entre les lignes des 2 images, etc...
Avec quelques structures annexes, il y a peut-être assez de gain pour passer sous le temps maximum.
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
Je voudrais pas être trop lourd, mais en adaptant l'algo de convolution ça doit marcher! Si j'ai bien compris,
* la scène est en N&B (2 valeurs par pixel: 0 ou 1),de X pixel sur Y pixel.
* La forme à détecter fait 5 pixel sur 5 pixel,donc 25 pixel
* la multiplication dans ce cas, ça peut être "est égale" (retourne 1 si sur le pixel de la scène et le pixel de la forme est identique, si non il vaut 0)
* L'intégrale, c'est la somation des 25 comparaisons
Donc il ne te reste plus qu'a faire "voyager" ta forme sur ta scène, et à chaque fois faire le calcule, la somation sur les 25 comparaison de pixels.
La forme se trouvera la où le résultat est le plus grand.
Donc tu fais:
pour tous les x et les y de la scène
pour les i et j de 0 a 5
cumul += (pixelCène[x+i,y+j] == pixelForme[i,j];
fin boucle
resultat [x, y] = cumul;
fin boucle
Chercher le maximum dans résultat, c'est là que se trouve le mobile.
Enfin, si tu sais ce que tu cherches c'est le plus simple.
Bonjour, en réalité la forme peut être quelconque et au maximum elle peut comporter 1000 pixels (de valeur 1). Le but est de trouver quels pixels blancs se retrouvent dans l'image 2, ayant subi une translation entre les deux.Il faut déterminer le plus grand groupe de pixels vérifiant cette propriété (indiquer le nombre de pixels du groupe et leurs coordonnées).
Donc pour l'instant j'essaye toutes les combinaisons de groupe de l'image 1, et je fais un peu ce que tu dis de faire pour voir s'il se retrouve sur l'image 2. Mais je galère pour l'instant
Bon j'ai réfléchi, et les combinaisons c'est un peu compromis parce qu'il y a 2^1000 sous-groupes au maximum, ce qui est assez important...
J'ai pensé à un truc (pas encore testé) : Je prends un pixel blanc (= de valeur 1) de l'image 2 comme référence (j'essaie sur tous les points), et pour chaque pixel blanc de l'image 1, je les translate en prenant la référence comme vecteur de translation, et je regarde combien de pixels correspondent sur l'image 2 en sommant (technique de @Dedeun) les pixels blancs de l'image 2 dont la position est déduite de la référence.
Concrètement mon idée ne demande "que" 3 boucles imbriquées et le pseudo-code est de ce type :
Pour chaque pixel blanc reference de l'image 2 : // O(U)
Pour chaque pixel blanc corres de l'image 1 pris comme correspondant à la référence : // O(U)
dx = reference.x - corres.x
dy = reference.y - corres.y
Pour chaque pixel blanc pix de l'image 1 : // O(U)
Si le pixel de l'image 2 de coordonnées (pix.x + dx, pix.y + dy) est blanc :
Incrémenter le compteur et stocker les coordonnées // Faire ce que demande le sujet
Je pense qu'il est inutile de tester toutes les combinaisons, car une simple somme sur tous les pixels suffit.
Dites-moi ce que vous en pensez
PS : Je pense qu'il est possible de réduire les boucles lorsque la translation dépasse les bords de l'image (pour ça il faut utiliser le fait que nos pixels blancs sont lus de haut en bas et de gauche à droite, donc sont déjà un peu triés).
PPS : Écrire ce pavé m'a aidé à mettre des mots sur mon idée, j'ai amélioré l'idée au fur et à mesure de l'écriture du message, et donc même si ça fait un peu monologue ça serait bête de ne pas vous en faire profiter
****************
EDIT :
J'ai testé l'algorithme, il réussit 25% des tests, a 35% d'erreurs de résultat et 35% de dépassement de temps d'exécution.
Je n'ai pas du tout essayé d'optimiser le programme, mais j'ai quelques idées.
Mon programme :
#include <cstdio>
// Constantes
const int MAX_TAILLE = 500, MAX_POINTS = 1000;
// Variables globales et structures de données
int nbLig, nbCol;
short nbMiniDrones = 0;
bool image1[MAX_TAILLE][MAX_TAILLE], image2[MAX_TAILLE][MAX_TAILLE];
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
struct Point
{
short x, y;
Point(short l=0, short c=0) : x(l), y(c) {}
};
Point points1[MAX_POINTS], points2[MAX_POINTS], correspondances[MAX_POINTS];
// Fonctions
// Main
int main()
{
scanf("%d%d", &nbLig, &nbCol);
short nbDrones1 = 0;
for (int i=0; i < nbLig; ++i)
{
for (int j=0; j < nbCol; ++j)
{
short a;
scanf("%hd", &a);
image1[i][j] = a;
if (a)
{
points1[nbDrones1] = Point(i, j);
++nbDrones1;
}
}
}
nbMiniDrones = nbDrones1;
short nbDrones2 = 0;
for (int i=0; i < nbLig; ++i)
{
for (int j=0; j < nbCol; ++j)
{
short a;
scanf("%hd", &a);
image2[i][j] = a;
if (a)
{
points2[nbDrones2] = Point(i, j);
++nbDrones2;
}
}
}
nbMiniDrones = min(nbMiniDrones, nbDrones2);
short maxiCorrespondances = 0;
// Boucles principales
for (int ref=0; ref < nbDrones2; ++ref) // Pour chaque pixel blanc de l'image 2 pris comme référence
{
for (int corres=0; corres < nbDrones1; ++corres) // Pour chaque pixel blanc de l'image 1 pris comme correspondant à la référence
{
short dx = points2[ref].x - points2[corres].x; // Translation courante selon x
short dy = points2[ref].y - points2[corres].y; // Translation courante selon y
short nbCorrespondances = 0;
Point temp[nbDrones1];
for (int curPixel=0; curPixel < nbDrones1; ++curPixel) // Pour chaque pixel blanc de l'image 1
{
// Si le pixel de l'image 2 de coordonnées (curPixel.x + dx, curPixel.y + dy) est blanc
short coordX = points1[curPixel].x + dx, coordY = points1[curPixel].y + dy;
if (coordX >= 0 && coordX < nbLig && coordY >= 0 && coordY < nbCol && image2[coordX][coordY])
{
temp[nbCorrespondances++] = Point(coordX + 1, coordY + 1);
}
}
if (nbCorrespondances > maxiCorrespondances)
{
for (int i=0; i < nbCorrespondances; ++i)
{
correspondances[i] = temp[i];
}
maxiCorrespondances = nbCorrespondances;
}
}
}
// Affichage des résultats
printf("%hd\n", maxiCorrespondances);
for (int i=0; i < maxiCorrespondances; ++i)
{
printf("%hd %hd\n", correspondances[i].x, correspondances[i].y);
}
return 0;
}
Votre tableau global, c'est pas super élégant, et il y a des chances que L>500 connaissant les zozos de France IOI.
Utilisez un std::vector à la place de cette horreur.(std::vector et non std::array pour avoir une taille de tableau connue à l'exécution et pas à la compilation).
Votre code c'est du C, pas du C++. (sauf la ligne 1, LOL)
Ligne 72, il y a déjà une correspondance, non ?
Ligne 73, un VLA, interdit en C++ et bientôt même en C.
Je ne vois pas de trou de logique dans votre algo mais comme vous tronques potentiellement les entrées, cela peut expliquer les erreurs de résultats.
Pour ce qui est des dépassements de temps d'exécution, votre temps d'exécution est toujours dans le pire des cas, car vous testez toutes les combinaisons possibles, car vous ne savez pas si vous avez trouvé la meilleure solution si vous n'avez pas tout calculé.
Avec l'approche de trouver les plus gros éléments possibles en premiers, on peut aussi calculer l'ensemble des translations possibles entre l'image de départ et l'image d'arrivé, comme vous le faites, mais dès qu'on en a trouvé un, on sait que c'est le plus grand (ou l'un des plus grand à égalité).
Avec une liste "d'ensemble" avec priorité (la priorité étant la taille de l'ensemble) et une routine de création de toutes les paires de 2 "sous-ensembles" d'un ensemble, que l'on peut appeler répétitivement, l'algo me parait assez simple.
On commence par créer un ensemble qui contient tous les points allumés de l'image de départ. On n'a calculé l'ensemble des translations possibles entre l'image de départ et l'image d'arrivé. On l'empile dans la liste à priorité.
Tant qu'il y a des éléments dans la liste à priorité, on prend le premier ensemble (en le supprimant de la liste).
Si l'ensemble n'est pas translatable par l'une des translations possibles, on applique la routine de découpage en sous-ensemble qui va ajouter tous ces sous-groupes à la liste des ensembles.
Sinon, on n'a trouvez LE PLUS GRAND, on sort.
Et on boucle tant que la liste n'est pas vide.
- Edité par bacelar 21 mai 2020 à 20:24:52
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
Tout d'abord merci de ta grande réponse, mais comme je suis pas très à l'aise avec les fonctionnalités du langage et ses spécificités, je vais 'essaier de me justifier ou de demander des éclaircissements pour chaque paragraphe de ton message.
"Pourquoi L<500 ???"
-> Ce sont les contraintes de l'énoncé. Et comme mon code ne sert qu'à résoudre l'exercice, je me permets de déclarer ces tableaux globaux, connaissant les contraintes de taille.
"std::vector et non std::array pour avoir une taille de tableau connue à l'exécution et pas à la compilation"
-> Quel est l'intérêt ? (Je suis juste curieux pas agressif )
"Votre code c'est du C, pas du C++"
-> En effet, j'en ai conscience, mais le C est beaucoup plus rapide pour les entrées-sorties il me semble, et comme l'exercice se joue beaucoup sur le temps d'exécution...
"Ligne 72, il y a déjà une correspondance, non ?"
-> En effet il y a un souci de ce côté-là.
"Ligne 73, un VLA, interdit en C++ et bientôt même en C."
-> Je n'ai pas trop compris ce que c'était, et surtout pourquoi c'est interdit.
"on peut aussi calculer l'ensemble des translations possibles entre l'image de départ et l'image d'arrivé"
-> Cette phrase m'a sauvé et m'a permis de résoudre l'exercice, MERCI !
Mon code (pour les curieux), qui passe tous les tests, de complexité O(nbLignes * nbCols + nbObjets²) :
#include <iostream>
#include <algorithm>
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
struct Point
{
short x, y;
Point(short l=0, short c=0) : x(l), y(c) {}
bool operator<(Point const &autre) const
{
return (x < autre.x || (x == autre.x && y < autre.y));
}
};
bool operator==(Point const &pt1, Point const &pt2)
{
return pt1.x == pt2.x && pt1.y == pt2.y;
}
int main()
{
// Initialisation
int nbLig, nbCol;
std::cin >> nbLig >> nbCol;
std::vector<Point> points1;
std::vector<Point> points2;
for (int i=0; i < nbLig; ++i)
{
for (int j=0; j < nbCol; ++j)
{
short a;
std::cin >> a;
if (a)
{
points1.push_back(Point(i, j));
}
}
}
for (int i=0; i < nbLig; ++i)
{
for (int j=0; j < nbCol; ++j)
{
short a;
std::cin >> a;
if (a)
{
points2.push_back(Point(i, j));
}
}
}
int nbDrones1(points1.size()), nbDrones2(points2.size());
// Tableaux de tous les vecteurs translations entre tous les points des images. Une dimension pour trier plus facilement.
int multiplication = nbDrones1 * nbDrones2;
Point translations[multiplication];
Point translationsTriees[multiplication];
// Boucles principales
for (int i=0; i < nbDrones1; ++i)
{
for (int j=0; j < nbDrones2; ++j)
{
short dx = points2[j].x - points1[i].x; // Translation courante selon x
short dy = points2[j].y - points1[i].y; // Translation courante selon y
translations[i*nbDrones2 + j] = Point(dx, dy); // Vecteur translation
translationsTriees[i*nbDrones2 + j] = Point(dx, dy);
}
}
std::sort(translationsTriees, translationsTriees + multiplication);
short maxiCorrespondances(0), curCorrespondances(0);
Point vecteurMax(translationsTriees[0]);
Point vecteurCourant(translationsTriees[0]);
for (int i=0; i < multiplication; ++i)
{
if (translationsTriees[i] == vecteurCourant)
{
++curCorrespondances;
if (curCorrespondances > maxiCorrespondances)
{
maxiCorrespondances = curCorrespondances;
vecteurMax = vecteurCourant;
}
}
else
{
curCorrespondances = 1;
vecteurCourant = translationsTriees[i];
}
}
// Affichage des résultats
std::cout << maxiCorrespondances << '\n';
for (int i=0; i < nbDrones1; ++i)
{
for (int j=0; j < nbDrones2; ++j)
{
if (translations[i*nbDrones2 + j] == vecteurMax)
{
std::cout << points2[j].x + 1 << ' ' << points2[j].y + 1 << '\n';
}
}
}
return 0;
}
Ce n'est pas dans l'énoncé que tu nous donnes, c'est C<500, pas L. La seule contrainte sur L, c'est L>=1.
2) "std::vector et non std::array..."
Pouvoir s'adapter à la taille variable des images et pas utiliser les valeurs maximales, et comme on ne connait pas la taille maximales de L (cf. 1) ), vous n'avez pas trop le choix, à moins de faire de l'allocation dynamique (et donc se compliquer la vie pour rien).
3) "En effet, j'en ai conscience, mais le C est beaucoup plus rapide pour les entrées-sorties..."
Oulà, vous avez fait des benchmark avant de faire cette assertion complètement gratuite ? En plus c'est tout votre code qui est en C, pas juste les entrées-sorties. Mais c'est aussi là qu'un code C et un code C++ (le code source, pas le résultat après compilation) diverge le plus.
Mais c'est clairement pas sur les entrées-sorties que le temps va s'écouler, à moins d'avoir un OS tout pourri et d'utiliser un HD tout rayé qui tourne à 5Hz.
Ne jamais faire d'optimisation sans mesurer les performances, que cela soit en C ou en C++.
Donc, bon, c'est un argument tout moisi, no offence .
4) "VLA" et surtout pourquoi c'est interdit.
Parce que ça planque tout un mécanisme ultra casse-gueule, que le développeur ne peut pas "finement" contrôler, que cela ne présente aucun intérêt à part pourvoir programme de manière "non safe" (i.e. cracra). C'est une fausse bonne idée, comme l'a été les "auto_ptr" du C++ en son temps.
C'est pas que cela sera interdit, c'est que cela ne sera plus supporté (cf. les sales bidouilles dans le compilateur pour "supporter" cette cochonnerie, juste pour permettre de travailler comme un sagouin).
Le code est bien plus "C++ compliante".
Les inline min et max, pourquoi ? La STL a bien plus flexible (en plus, t'as déjà l'include qu'il faut):
L'utilisation de "short" doit te valoir quelques warnings, et les warning, c'est mal.
Je ne suis pas sûr que l'utilisation de short à la place de int dans la classe Point te donne un boost en performance, bien au contraire (possibilité de désalignement de la mémoire, ou le compilateur "paddera" en sous-marin pour revenir à une taille de int).
Il faut donc faire des mesures avant de faire des optimisations.
Ou bien, c'est sémantique (cf. contrainte de l'énoncé) et là, faut être cohérent et lire des shorts dans le fichier et pas des int (cf. ligne 27).
Ligne 11, ne pas utiliser de valeurs par défaut qui n'ont aucun sens.
Ligne 11 toujours, préférez la nouvelle syntaxe d'initialisation avec des accolades que l'ancienne avec des parenthèses, dans la liste d'initialisation
Point(short l, short c) : x{l}, y{c} {}
Idem Ligne 57 sur la syntaxe d'initialisation.
Ligne 61 et 62, utilisation de VLA, c'est pas bien. Il est encore gentil avec toi le compilateur, mais ça ne durera pas.
Il suffit de remplacer ces cochonneries par de simple std::vector
GG pour l'utilisation de "translationsTriees" qui doit grandement aider à la localité des accès mémoire pour la lecture des données.
(mais son initialisation, beurk, un clonage aurait été plus simple et plus performant => std::vector est ton ami (et un constructeur de copie pour la classe Point avec noexcept))
Ligne 78 à 80, comme ligne 57 sur la syntaxe d'initialisation, les accolades sont nos amies et les parenthèses des faux-culs.
Votre algorithme est très élégant mais je ne suis pas sûr qu'il soit exact. (favorise les déplacements en x plutôt quand y, etc...).
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
> Ce n'est pas dans l'énoncé que tu nous donnes, c'est C<500, pas L. La seule contrainte sur L, c'est L>=1.
Euh... si.Je lis
OP> 1 <= L, C <= 500
i.e. L et C sont compris entre 1 et 500. Tous les exos que france-ioi que j'ai pour voir étaient bornés de la sorte. Résultat, de magnifiques corrections avec des tableaux statiques dont la taille est en codée en dur avec 500, 10000, etc.
----
OP> 3) "En effet, j'en ai conscience, mais le C est beaucoup plus rapide pour les entrées-sorties..."
Cela ne fera aucune différence sur les exos donnés. De la même façon, remplacer des tableaux statiques par des dynamiques rentre toujours dans les clous. Les temps donnés sont faits pour intercepter les algos qui n'ont pas une complexité algorithmique aussi optimale que celle qu'ils visent à faire implémenter.
----
> [VLA] ne présente aucun intérêt à part pourvoir programme de manière "non safe"
Entièrement d'accord sur le fait que c'est non safe de base. Cela n'empêche pas l'utilisateur de pouvoir faire un contrôle que la taille sera bien inférieure à un max qui aurait pu être employé à la place pour définir un tableau statique. Mais bon, c'est le principe de vérification des entrées qui ... passe 90% du temps à la trappe. Comme souvent. C'est là que c'est non safe.
Maintenant, il y a un avantage énorme: pour un tableau local au scope courant, ça coûte que dalle à allouer. Et ce n'est pas si négligeable. Ce n'est pas pour rien qu'il y a eu plusieurs tentatives (avortées à ce jour) pour disposer d'un équivalent en C++.
----
> Les inline min et max, pourquoi ? La STL a bien plus flexible (en plus, t'as déjà l'include qu'il faut):
Je dirais même avoir vu un std::max_element écrit à la main
----
> Je ne suis pas sûr que l'utilisation de short à la place de int dans la classe Point te donne un boost en performance, bien au contraire (possibilité de désalignement de la mémoire, ou le compilateur "paddera" en sous-marin pour revenir à une taille de int).
Vu que tous les calculs entiers sont toujours faits sur des ints avant d'être re-tronqués, intuitivement, j'abonderai dans le même sens.
De nouveau, ce qui est mesuré sur france-ioi c'est la complexité algorithmique et pas les optims qui relèvent du HPC & cie. Sur un coup de bol ça pourrait peut-être passer quelques quelque algos, mais je n'y crois pas trop.
----
> [unicorn initialization syntax] les accolades sont nos amies et les parenthèses des faux-culs.
J'aurai dit le contraire: cf. std::vector(10, 20) VS std::vector{10,20}
----
> Votre algorithme est très élégant mais je ne suis pas sûr qu'il soit exact.
S'il passe les tests de france-ioi, il y a de fortes chances qu'il soit correct par rapport aux énoncés.
----
Parenthèse: Pour ma part, d'un point de vu purement sémantique que je retraduis en typage C++, j'aime bien distinguer position et delta. C'est certainement bien plus complexe que ce que l'on peut se permettre de faire, mais je trouve que c'est plus safe et plus lisible.
struct Point {
int x;
int y;
};
struct Delta {
int x;
int y;
};
Point operator+(Point, Delta const&) noexcept;
Point operator+(Delta const&, Point) noexcept;
Delta operator-(Point const&, Point const&) noexcept;
...
----
En tout cas, bravo pour avoir trouvé une solution.
>S'il passe les tests de france-ioi, il y a de fortes chances qu'il soit correct
Oui, effectivement. J'avais interprété le tri comme juste une optimisation d'accès, mais il fait bien partie intégrante de l'algorithme, ce qui très élégant, GG.
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
C'est une erreur de ma part d'avoir retaper max et min, en revanche je ne connaissais pas std::max_element et c'est cool !
J'ai fait en sorte de ne plus avoir de warning, mais c'est vrai que l'utilisation de short ici est inutile
Si je ne mets pas de valeur par défaut, je crois que j'ai une erreur lors de la déclaration du tableau de Point lignes 61/62 : Dois-je faire deux constructeurs, un sans paramètre qui ne fait rien et l'autre sans valeur par défaut ?
Je ne connaissais pas l'initialisation avec des accolades, c'est la façon générique d'affecter des variables ? (Fonctionne toujours quelque soit le type de cette dernière ?)
J'ai compris l'histoire des VLA, la STL c'est le bien
"de magnifiques corrections avec des tableaux statiques dont la taille est en codée en dur" : c'est de là que viennent mes mauvaises habitudes
Le fait de faire deux structures de données m'a effleuré l'esprit, mais je me suis dit que j'avais peu d'opérations à faire, donc un simple commentaire sur le fait que ça soit un vecteur était suffisant pour cet exercice particulier
Je ne connais pas "noexcept", je me renseigne
Eh bien merci à vous, j'apprends plein de choses c'est fou !
PS : y'a un moyen de recevoir des notifications quand il y a un nouveau message sur les sujets de forum qu'on suit ?
Ce n'est pas un déterrage, récemment, cette discussion a été pointée sur le forum Python par Pierrot le fou, d'abord ICI puis ICI.
Dans ce genre de problème sur France-IOI, quand Python ne passe pas tous les tests ce qui était le cas avec mon code, c'est que
soit, Python, trop lent, ne permet d'y parvenir
soit c'est l'algo qu'il faut optimiser voire changer.
ce qui m'a conduire à récrire l'algo en C++, voir ci-dessous.
Pour ceux qui n'ont pas envie de relire tout le descriptif sur fioi, on donne deux tableaux de 0 et de 1 (en couleur autre que noire ci-dessous):
et on demande de
trouver un sous-ensemble de taille maximale formé de pixels du 1er tableau (en rouge sur le dessin) tel que ce sous-ensemble puisse être translaté par un même vecteur en des pixels du 2e tableau
de donner les coordonnées de tous les translatés
Ça paraît compliqué mais en fait, c'est l'algorithme bestial qui est demandé (mais ça on le sait pas au départ) :
vous cherchez tous les vecteurs de translation possibles (en joignant n'importe quel pixel du 1er à n'importe quel pixel du 2nd)
vous cherchez le vecteur qui apparaît le plus et le mémorisez
vous parcourez les pixels du tableau 1, vous translatez et si ça donne un pixel du tableau 2, vous affichez.
La façon la plus simple de traiter la 2e étape est d'utiliser un mapping (le code c++ donné plus haut dans ce fil s'en sort autrement, il trie mais c'est ça l'oblige à faire 2 parcours et c'est de moins bonne complexité, en théorie du moins)
En Python, ça donne
from sys import stdin
from collections import Counter
def solve():
input=stdin.readline
n, p=map(int, input().split())
im1=[input().split() for _ in range(n)]
im2=[input().split() for _ in range(n)]
P1=[(i,j) for i in range(n) for j in range(p) if im1[i][j]=='1']
P2=[(i,j) for i in range(n) for j in range(p) if im2[i][j]=='1']
C=Counter((x2-x1, y2-y1) for x1,y1 in P1 for x2,y2 in P2)
u,m= C.most_common(1)[0]
print(m)
a,b=u
S1=set(P1)
for (i,j) in P2:
if (i-a, j-b) in S1:
print(i+1, j+1)
solve()
qui ne passe que 13 tests sur 20. Counter est un dictionnaire Python et donc une table de hachage. Comme la STL a des table de hachage et des ensembles, je récris le code en C++ (notez que je ne suis pas spécialiste de ce langage) :
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef pair<int, int> Point;
struct hash_pair
{
template <class T1, class T2>
size_t
operator() (const pair<T1, T2> &p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
// boost::hash_combine
hash1 ^= hash2 + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2);
return hash1;
}
};
int
main ()
{
int n, p;
vector<Point> P1, P2;
unordered_map<Point, int, hash_pair> C;
unordered_set<Point, hash_pair> S1;
int maxi = 0;
Point maxi_pair;
scanf ("%d%d", &n, &p);
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
{
int q;
scanf ("%d", &q);
if (q)
{
Point pt = make_pair (i, j);
P1.push_back (pt);
S1.insert (pt);
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
{
int q;
scanf ("%d", &q);
if (q)
P2.push_back (make_pair (i, j));
}
for (auto p1 : P1)
for (auto p2 : P2)
{
int x1{ p1.first }, x2{ p2.first }, y1{ p1.second }, y2{ p2.second };
Point p = make_pair (x2 - x1, y2 - y1);
if (C.find (p) != C.end ())
{
C[p]++;
if (C[p] > maxi)
{
maxi = C[p];
maxi_pair = p;
}
}
else
C[p] = 1;
}
if (maxi == 0)
{
maxi = 1;
maxi_pair.first = P2[0].first - P1[0].first;
maxi_pair.second = P2[0].second - P1[0].second;
}
printf ("%d\n", maxi);
int xmax = maxi_pair.first, ymax = maxi_pair.second;
for (auto p2 : P2)
{
int x2 = p2.first, y2 = p2.second;
Point p1 = make_pair (x2 - xmax, y2 - ymax);
if (S1.count (p1))
printf ("%d %d\n", x2 + 1, y2 + 1);
}
return 0;
}
Et quelle n'est pas ma surprise de voir que ce code ne passe que 17 tests sur 20 !
L'explication vient en fait de l'inefficacité des tables de hachage de la STL (unordered_map). C'est de notoriété mais je ne l'avais jamais expérimenté, d'où une certaine désillusion.
Et si je teste avec un gros fichier, le code C++ est plus lent (48 s) que le code Python (17 s). Et c'est bien la table de hachage qui pose problème, 98% du temps est passé lignes 58-74. Et si on remplace unordered_map par map, le temps est meilleur (21s) !! alors que map a une complexite de recherche en log(n) contre O(1) amorti pour une table de hachage.
Ce modèle de table de hachage par chaînage est imposé par le standard paraît-il et je ne comprends pas pourquoi alors qu'on sait parfaitement qu'il est bien plus lent que l'adressage ouvert, modèle utilisé par la table de Python. Et je ne vois rien dans C++23 qui aille changer cela. Pour moi, c'est vraiment une très grosse anomalie de la STL alors que cette lib est orientée performances.
- Edité par PascalOrtiz 25 décembre 2022 à 2:14:07
France ioi est assez typique: si ça ne passe pas, c'est que la complexité algorithme de ta solution ne scale pas avec ce qui est attendu.
En général je ne m'embête pas, c'est directement `++count[key];` car chaque `c[p]`que tu fais réalise aussi un find => `if (auto val = ++C[p] ; val > seuil)`. Mais je l'aurai tout simplement fais en 2 passes au lieu de checker le nouveau max pour chaque clé, ce qui implique un test tout tous les p insérés au lieu d'un test par p gardé. D'abord l'insertion simple, puis le std::max_element sur les valeurs. Probablement de la microoptimisation: on ne gagne qu'un facteur linéaire. Ca ne justifie pas un échec sur les tests passés sur france-ioi.
PS: quand tu parles de test avec un gros fichier... C'est sur ta machine? Tu compiles au moins en `-O2` ?
France ioi est assez typique: si ça ne passe pas, c'est que la complexité algorithme de ta solution ne scale pas avec ce qui est attendu.
Il ne me semble pas ici, en tout cas pour la complexité théorique qui est du n² s'il y a n pixels dans chaque images en supposant que l'accès à la table de hachage est un O(1) avec une petite constante ce qui est le cas avec une bonne table et en n²log(n) avec un map (arbre rouge et noir en général).
lmghs a écrit:
En général je ne m'embête pas, c'est directement `++count[key];` car chaque `c[p]`que tu fais réalise aussi un find => `if (auto val = ++C[p] ; val > seuil)`.
Ah, oui, excellente remarque, comment ne l'ai-je vu ?! Mise-à-jour : désolé lmghs, contrairement à ce que j'ai annoncé initialement (*), ça ne change hélas presque rien et d'ailleurs, ça ne changeait rien sur France-ioi. A posteriori, c'est assez logique car le compilateur doit être capable d'optimiser quelque chose d'aussi simple tout seul. Enfin, merci quand même de ta suggestion.
(* annonce initiale) Effectivement ça améliore les performances, ça divise par 2 le temps sur le gros fichier (21 s). Mais pour france-ioi, cette amélioration ne change rien (17 tests) encore. Curieusement, je devrais aussi pouvoir optimiser le C.find() en récupérant le pointeur mais ça ne donne quasiment rien.
lmghs a écrit:
Mais je l'aurai tout simplement fais en 2 passes au lieu de checker le nouveau max pour chaque clé, ce qui implique un test tout tous les p insérés au lieu d'un test par p gardé. D'abord l'insertion simple, puis le std::max_element sur les valeurs. Probablement de la microoptimisation: on ne gagne qu'un facteur linéaire.
max_element, je ne connaissais pas mais effectivement c'est bien possible que ça accélère, j'essayerai.
lmghs a écrit:
PS: quand tu parles de test avec un gros fichier... C'est sur ta machine? Tu compiles au moins en `-O2` ?
Je comprends que tu puisses douter vu l'écart entre C++ et Python, mais oui, bien sûr, j'ai même mis -O3.
Pour info, sur le forum Python, josmiley a trouvé un moyen pour remplacer les couples de coordonnées par un unique entier. Mine de rien, cette astuce semble simplifier le hachage et cette fois tous les tests passent. Le code est ICI.
EDIT : voir ci-dessus, en fait,la modif proposée ne change rien. Le gros fichier de test est ici (zippé, 60 Ko)
- Edité par PascalOrtiz 22 décembre 2022 à 21:48:02
Pour moi le find n'a aucun intérêt. Cette partie, avec ton approche, devrait s'écrire:
Point p{x2 - x1, y2 - y1};
auto const count = ++C[p]; // on passe de 4 finds (si nouveau max; 3 tout le temps) à un seul
if (count > maxi)
{
maxi = count;
maxi_pair = p;
}
Car je ne suis pas sûr que le compilo soit capable d'identifier qu'il y a 4 recherches identiques (ce n'est pas si simple le code du find AMA, mais je peux me tromper) -- j'ai la flemme de comparer les ASM sur godbolt, et de lancer le test dans VTune, là tout de suite.
Après au lieu de tester size(C) fois pour la MAJ du max, tu testes size(P1) * size(P2). C'est dommage.
D'où l'idée de remplir C une première fois de façon simple avec juste `++C[p]` (besoin de rien de plus), puis le max_element ensuite. Par contre, je ne suis pas sûr que france-ioi supporte le C++14 (car il faudrait une lambda, idéalement, un foncteur façon 98 au pire) pour indiquer que la comparaison, c'est sur le second de la paire key-value pointée par l'itérateur.
PS: autre micro optim: utiliser reserve sur les vecteurs. Et pas sûr que scanf change grand chose.
Chez clang++, on voit 2 fois plus d'asm pour la version avec 4 C[p], avec un seul appel à _M_insert_unique_node avec la version factorisée au lieu de 3 avec la non factorisée. Chez g++, juste 60 lignes (sur 200 en plus), et op[] apparaît 2 fois derrière `call` dans la version non factorisée contre 0.
=> le compilo profitera de l'optim qu'on lui rajoutera à la main. Mais d'après tes observations, ce ne serait donc pas ça qui fait la différence.
Pour moi le find n'a aucun intérêt. Cette partie, avec ton approche, devrait s'écrire:
Point p{x2 - x1, y2 - y1};
auto const count = ++C[p]; // on passe de 4 finds (si nouveau max; 3 tout le temps) à un seul
if (count > maxi)
{
maxi = count;
maxi_pair = p;
}
Effectivement, ça peut bien se simplifier ainsi (je ne savais pas qu'en C++ si la clé n'existe pas alors une valeur par défaut était fournie).
lmghs a écrit:
Après au lieu de tester size(C) fois pour la MAJ du max, tu testes size(P1) * size(P2). C'est dommage.
J'ai modifié.
Ces deux changements ne modifient que marginalement le temps d'exécution. Le premier code mettait 46 s, le nouveau en met 41 s, donc 10% d'amélioration. Dans le code ci-dessous, la répartition est grosso modo la suivante :
0,4 s pour construire les vecteurs
40 s pour construire la table de hachage
0,6 s pour le max, reconstruire les vecteurs et afficher.
Voici le nouveau code :
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef pair<int, int> Point;
struct hash_pair
{
template <class T1, class T2>
size_t
operator() (const pair<T1, T2> &p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
// boost::hash_combine
hash1 ^= hash2 + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2);
return hash1;
}
};
int
main ()
{
int n, p;
vector<Point> P1, P2;
unordered_map<Point, int, hash_pair> C;
unordered_set<Point, hash_pair> S1;
scanf ("%d%d", &n, &p);
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
{
int q;
scanf ("%d", &q);
if (q)
{
Point pt = make_pair (i, j);
P1.push_back (pt);
S1.insert (pt);
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
{
int q;
scanf ("%d", &q);
if (q)
P2.push_back (make_pair (i, j));
}
for (auto p1 : P1)
for (auto p2 : P2)
{
int x1{ p1.first }, x2{ p2.first }, y1{ p1.second }, y2{ p2.second };
Point p{ x2 - x1, y2 - y1 };
++C[p];
}
int maxi = 0;
Point maxi_pair;
for (auto kv : C)
if (kv.second > maxi)
{
maxi = kv.second;
maxi_pair = kv.first;
}
int xmax = maxi_pair.first, ymax = maxi_pair.second;
printf ("%d\n", maxi);
for (auto p2 : P2)
{
int x2 = p2.first, y2 = p2.second;
Point p1 = make_pair (x2 - xmax, y2 - ymax);
if (S1.count (p1))
printf ("%d %d\n", x2 + 1, y2 + 1);
}
return 0;
}
Pour donner une idée, si j'émule la table de hachage avec un tableau statique, le temps est de 0,8 s.
lmghs a écrit:
D'où l'idée de remplir C une première fois de façon simple avec juste `++C[p]` (besoin de rien de plus), puis le max_element ensuite.
C'est ce que j'ai fait ci-dessus (même sans max_element le calcul du max ne coûte rien).
Finalement, le problème venait de la fonction de hachage qui générait sans doute trop de collisions. En en prenant une autre (trouvée sur codeforces), et testée sur le gros fichier en lien ci-dessus, le temps est maintenant de 11 s contre 40 s initialement. Et tous les tests passent sur France-IOI. On passe même à 5 s si on impose une taille minimale à la table avec reserve. Le code :
#include <algorithm>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cmath>
using namespace std;
typedef pair<int, int> Point;
struct hash_pair
{
template <class T1, class T2>
size_t
operator() (const pair<T1, T2> &x) const
{
return ((long long)x.first)^(((long long)x.second)<<32);
}
};
int
main ()
{
int n, p;
vector<Point> P1, P2;
unordered_map<Point, int, hash_pair> C;
unordered_set<Point, hash_pair> S1;
scanf ("%d%d", &n, &p);
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
{
int q;
scanf ("%d", &q);
if (q)
{
Point pt = make_pair (i, j);
P1.push_back (pt);
S1.insert (pt);
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
{
int q;
scanf ("%d", &q);
if (q)
P2.push_back (make_pair (i, j));
}
C.reserve(P1.size()* P2.size());
for (auto p1 : P1)
for (auto p2 : P2)
{
int x1{ p1.first }, x2{ p2.first }, y1{ p1.second }, y2{ p2.second };
Point p{ x2 - x1, y2 - y1 };
++C[p];
}
int maxi = 0;
Point maxi_pair;
for (auto kv : C)
if (kv.second > maxi)
{
maxi = kv.second;
maxi_pair = kv.first;
}
int xmax = maxi_pair.first, ymax = maxi_pair.second;
printf ("%d\n", maxi);
for (auto p2 : P2)
{
int x2 = p2.first, y2 = p2.second;
Point p1 = make_pair (x2 - xmax, y2 - ymax);
if (S1.count (p1))
printf ("%d %d\n", x2 + 1, y2 + 1);
}
return 0;
}
Ça marche aussi en reprenant la fonction de boost::combine mais en appliquant les remarques exprimées ICI.
Remarquez qu'il est même possible d'écrire une table de hachage ad hoc où le chaînage est réalisé par des vectors au lieu d'une liste chaînée, ça se fait en 40 lignes. Avec une fonction de hachage qui distribue bien, on obtient même un meilleur temps.
- Edité par PascalOrtiz 24 décembre 2022 à 11:52:20
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères