As-tu bien surchargé << pour les std::vector<std::size_t> ?
Je ne vois pas la surcharge d'opérateur.
Ou alors utilise deux boucles.
Oui, je peux faire un std::cout de tout std::vector<int || string || std::size_t || etc> (templates). Le probleme est que dans ma fonction si j'affiche les combinaisons avant le return j'ai bien mes combinaisons. Mais quand je les affiche en dehors j'ai rien, comme si la valeur retournée par ma fonction etait vide.
Merci pour ton programme mais j'aimerais bien savoir pourquoi le mien marche plus.
Il fonctionnait bien et j'ai décidé de remplacer std::span par std::vector, puis en paramètre par défaut j'ai mis un std::vector "vide" pour que je sois pas toujours obligé de l'appeler avec un vecteur en paramètre.
Dans le code tout le résultat est dans une variable combinaisons (ligne 7), lorsque j'affiche combinaisons (ligne 20 - 23) avant mon return (ligne 25) je vois mes combinaisons. Mais quand je reçois le résultat de la fonction dans le main et que je fais un affichage, rien n'est affiché, voir mon précédent post.
Dans le code suivant, je passe le vecteur vide par référence et je ne fais pas de return. Si tu ne passe pas le vecteur par référence, la fonction prendra une copie du vecteur et c'est cette copie que tu modifies.
Si tu ne fais pas dans le main: combinaisons = combinaisons_possibles(...);
Le vecteur du main ne sera pas changé. - #include <iostream> #include <string> #include <vector> typedef std::vector<int> Vecteur; typedef std::vector<Vecteur> Grille; void listeCombinaisons(int N, int K, Grille&combinaisons) { Vecteur passe (K); int i = 0; int v = 0; while(i >= 0) { while(i < K && v+K-i <= N) { passe[i++] = v++; } if(i==K) combinaisons.push_back(passe); i--; if(i>=0) v = passe[i] + 1; } } int main(void) { int K, N; std::cin >> K >> N; Grille combinaisons; listeCombinaisons(N, K, combinaisons); // Affichage. for(auto passe: combinaisons) { std::string s { "" }; for(auto item: passe) { std::cout << s << item; s = ", "; } std::cout << std::endl; } return 0; }
- Edité par PierrotLeFou 30 avril 2022 à 7:40:09
Le Tout est souvent plus grand que la somme de ses parties.
Oui, sauf que je ne le transporte pas de la fonction appelante vers la fonction de génération. Et il était passé par valeur si je ne me trompe pas. Je rappelle que le PO veut quelque chose de général.
On pourrait générer dans la fonction appelante un std::vector<std::vector<int>> et le resizer aux valeurs désirées (ça se calcule)
et on ne ferait que remplir dans la fonction.
Mais si on ne tient pas compte du vecteur précédent de la séquence, c'est encore plus long.
- Edité par PierrotLeFou 1 mai 2022 à 19:16:52
Le Tout est souvent plus grand que la somme de ses parties.
Tu peux limiter la copie de vecteur en le passant aussi en référence et en restaurant la valeur de vecteur[pos] en fin de boucle.
Dans la signature de la fonction (voir message) "vecteur" peut être vide(sa valeur par défaut), et on peut pas faire de reference sur une valeur nulle donc je trouves préférable de faire des copies.
PierrotLeFou a écrit:
Pour être franc, je préfère mon code car je n'ai pas besoin de vecteur intermédiaire sauf dans la fonction.
La fonction fait tout le job.
- Edité par PierrotLeFou il y a environ 5 heures
Tu veux dire quoi par fonction intermediaire ? Moi j'en vois pas.
PierrotLeFou a écrit:
Oui, sauf que je ne le transporte pas de la fonction appelante vers la fonction de génération. Et il était passé par valeur si je ne me trompe pas. Je rappelle que le PO veut quelque chose de général.
On pourrait générer dans la fonction appelante un std::vector<std::vector<int>> et le resizer aux valeurs désirées (ça se calcule)
et on ne ferait que remplir dans la fonction.
Mais si on ne tient pas compte du vecteur précédent de la séquence, c'est encore plus long.
- Edité par PierrotLeFou il y a environ 5 heures
Malheureusement je comprends rien... "sauf que je ne le transporte pas de la fonction appelante vers la fonction de génération", l'ai - je fait ?
Ce n'est pas toi qui a écrit ceci? void combinaisons_possibles(std::vector<std::vector<std::size_t>> &combinaisons, std::size_t const v_max, std::size_t const taille, std::vector<std::size_t> vecteur, std::size_t pos) vecteur n'est pas transmis à la fonction? Et tu le passes par valeur.
Le Tout est souvent plus grand que la somme de ses parties.
Oui mais c'est la fonction qui va y mettre un vecteur en se réappelant, par défaut c'est un vecteur vide donc je l'appelle sans le mettre a la base, ca compte ?
Ce n'est pas toi qui me parlais de performance? Tu appelles de façon récursive une fonction avec 5 paramètres. Je n'ai que 3 paramètres dans ma fonction et je génère de façon itérative. Mon "compteur circulaire" est en fait du backtracking itératif.
Si je me rend au bout, j'enregistre la solution et je recommence avec une autre alternative.
- Edité par PierrotLeFou 2 mai 2022 à 1:06:33
Le Tout est souvent plus grand que la somme de ses parties.
Quand on parle de performances, on fait des benchmarks. Des arguments comme le nombre de paramètres d'une fonction ne sont pas pertinents. (Je n'ai pas lu les codes, c'est une réponse générale).
C'est évident si on passe une heure dans la fonction ... Si le compilateur ne peut optimiser la fonction récursive pour une quelconque raison, il faut bien empiler les paramètres quelque part. Je suis d'accord que les benchmarks sont nécessaires pour vraiment savoir.
Toutefois, Asmitta ne génère qu'une combinaison par appel, alors que je les génère toutes dans un seul appel.
gbdivers: Tu es volontaire pour faire des benchmarks? Tu saurais mieux comment faire. et pourqoi ne pas essayer avec C(20, 10) ? Petit test en Python: >>> C=lambda n, k: 1 if k <= 0 else (n*C(n-1, k-1)//k) >>> C(20, 10) 184756
- Edité par PierrotLeFou 2 mai 2022 à 1:50:29
Le Tout est souvent plus grand que la somme de ses parties.
Surtout que les codes de tests ne sont pas précisés.
Si je balance vos 2 fonctions dans quick-bench, j'ai un truc comme ca (sans être sur d'utiliser correctement vos fonctions).
(Le graph est étrange, mais peu importe. C'est pas à moi de prouver quelle implémentation est la plus rapide, c'est à celui qui présente une implémentation de le faire).
Le point sur lequel je veux insister surtout Asmitta, c'est que ta démarche de base est incorrecte. On ne fait pas de l'optimisation dans le vide. On le fait avec un vrai code, des vrais tests (pour vérifier que les algos donnent le bon résultat, c'est le minimum), des vrais tests de performances, on analyse sur des vraies données qui ont un sens, etc. Des questions comme le coût de if versus for ou d'une assignation n'a aucun sens, parce que tu ne sais pas ce que le compilateur génère au final et parce qu'il y a une hiérarchie dans les coûts en performances (par exemple, le coût d'une instruction particulière -- de l'ordre de 1-3 cycles CPU -- est moins important que par exemple la mémoire cache -- plusieurs milliers de cycles CPU).
La question que tu vas poser (probablement) est donc comment se former à l'optimisation en C++. A mon sens, comme tu l'as vu, optimiser du code implique de faire de tester encore et encore différentes solutions, pour comprendre ce qu'il se passe. Donc avoir du code robuste, que tu vas pouvoir changer souvent sans que ça bug dans tous les sens est primordial. C'est à dire il faut savoir coder proprement. De ce que j'ai vu dans cette discussion, tu ne maîtrises pas encore assez le C++. Il te manque des notions de base.
Mon conseil : apprend dans un premier temps à coder correctement en C++ et oublie les performances. Par exemple avoir lu Professional C++ et avoir suffisamment écrit de code. Tu verras ensuite que la question des performances arrivent naturellement.
× 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.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Discord NaN. Mon site.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Discord NaN. Mon site.
Le Tout est souvent plus grand que la somme de ses parties.
Discord NaN. Mon site.