Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Diviseurs en C++ et bonnes pratiques

41 réponses
Avatar
Olivier Miakinen
Bonjour,

Ma principale expérience de C++ consiste en la maintenance de programmes
sous Windows avec Visual C++, sans aucune utilisation
de bibliothèque standard. Je voudrais remédier à cela en m'entraînant
sur Linux (avec gcc je suppose). Or il se trouve que j'ai un petit
problème à résoudre, et je pense que ça pourrait être l'occasion, mais
j'aurais besoin d'un peu d'aide au début pour le faire « à la C++ » et
pas avec les méthodes C que j'ai toujours utilisées jusqu'à présent.

Le « début » en question consiste à partir de la suite des nombres de 1
à 200 (dans un vector, je suppose), pour chaque nombre de déterminer la
liste ordonnée de ses diviseurs (dans d'autres vector sans doute), puis
d'écrire sur stdout toutes les décompositions des nombres en produits de
deux facteurs.

Par exemple, cela pourrait donner ceci :
1 : 1×1
2 : 1×2
3 : 1×3
4 : 1×4 2×2
...
8 : 1×8 2×4
9 : 1×9 3×3
10 : 1×10 2×5
...
36 : 1×36 2×18 3×12 4×9 6×6
...
199 : 1×199
200 : 1×200 2×100 4×50 5×40 8×25 10×20

Je ne cherche pas nécessairement à ce qu'on me mâche tout le boulot,
mais déjà, si quelqu'un pouvait m'indiquer où trouver d'une part les
bonnes pratiques C++ et d'autre part s'il existe une bibliothèque de
maths qui gère les décompositions en nombres premiers et les diviseurs,
ça me serait très utile.

Cordialement,
--
Olivier Miakinen

10 réponses

1 2 3 4 5
Avatar
Fabien LE LEZ
On Tue, 5 Oct 2010 09:44:03 -0700 (PDT), James Kanze
:

Il faut bien recopier un peu, non ? Si le fichier ne tient pas
en mémoire, tu ne peux pas le mmapper d'un coup non plus.



La question ici, c'est la définition de "mémoire".

La mémoire telle que vue par une application, c'est l'ensemble
RAM physique + une partie du disque dur.
L'OS décide des pages gardées en RAM et des pages mises en swap.

L'intérêt de mmap(), c'est d'utiliser le fichier de données comme
fichier swap.

Évidemment, si tu es en 32 bits, tu as le problème de l'espace
d'adressage réduit, qui va te forcer à jongler, et à mmap()er des
petits morceaux.
En revanche, si tu travailles en 64 bits, ton espace d'adressage est
bien plus grand que le fichier, et tu peux donc le charger entièrement
en mémoire (virtuelle).

S'il n'y a pas trop de lignes, on peut stocker en mémoire l'offset de
chaque ligne et ses premiers octets.



Avec un seek et une lecture chaque fois que tu veux faire une
comparaison ?



Avec les premiers octets, tu peux déjà effectuer un premier tri.

Ensuite, il y aura probablement des aller-retour des têtes de lecture
(même s'il n'y a pas d'appel explicite à "seek()"), mais l'OS est
censé optimiser tout ça.

Cf aussi la suite de mon message :

Après, évidemment, il faudra concevoir un algorithme pour tirer le
meilleur parti des pages récemment chargées en RAM physique.





Tu peux accéder à n'importe quelle partie de n'importe quelle page
chargée en RAM physique à la même vitesse.
Il faut bien sûr essayer de travailler sur un petit nombre de pages
(mais pas forcément contiguës) à la fois.
Avatar
Fabien LE LEZ
On Tue, 05 Oct 2010 18:19:43 +0200, Olivier Miakinen :

Bien, voici ma méthode de résolution.



J'ai bricolé un vague truc : http://fabien.li/temp/fclc.cpp

Le code est assez moche (beaucoup de redites, tout dans une seule
fonction, et des boucles au lieu des "algorithmes" de la bibliothèque
standard), et inefficace (on stocke beaucoup trop de trucs AHMA).

Généralement, quand je résouds un problème de ce style, je me contente
d'un premier jet momoche comme ça, car il s'agit de la résolution
ponctuelle d'un problème unique, et je n'aurai sans doute jamais à
revenir sur ce code, ni même à le réutiliser.

Dans ce cas précis, j'ai l'impression qu'utiliser des closures
améliorerait le code. Faut vraiment que je me penche sur C++-0x.
(Ou que j'implémente ton algo en Javascript...)


Note les typedef au début :

- Une somme et un produit sont tous les deux des entiers, mais
considérés comme différents ici. C'est pourquoi j'ai créé deux noms
différents pour le type "int".
Malheureusement, il n'y a pas de moyen simple de déclarer deux types
effectivement différents, donc le compilateur ne pourra pas vérifier
que je n'ai pas interverti les deux.

- Il faut, par deux fois, compter le nombre d'occurences de chaque
produit. (En fait, il faut juste savoir si c'est 1 ou plus, mais c'est
plus simple de compter carrément.)
En d'autres termes, associer un NbOccurences à un Produit. On utilise
donc un tableau associatif. En C++, c'est std::map<>.

- Chaque ligne contient un paquet de produits. On pourrait utiliser
aussi bien vector<>, deque<>, list<> ou même set<>. Par conséquent, on
choisit le conteneur par défaut, std::vector<>. D'une manière
générale, choisis toujours vector quand tu n'as pas de raison de
choisir autre chose.

- À chaque somme, on associe un paquet de produits.
Tableau associatif -> std::map<>.


Le reste est l'implémentation directe de ton algo, sans fioritures ni
raccourcis.
Avatar
Fabien LE LEZ
On Wed, 6 Oct 2010 10:42:40 -0700 (PDT), James Kanze
:

nous exigeons une bonne connaissance de la bibliothèque standard
très bonne connaissances des techniques numériques.
écrire du code correct et facile à lire et à modifier par la suite.
Et de pouvoir s'exprimer en anglais,



En gros, quatre compétences. Trois si tu es déjà dans un pays
anglophone.
Effectivement, trouver des gens compétents et disponibles risque
d'être difficile.
Avatar
Olivier Miakinen
Le 06/10/2010 21:05, Fabien LE LEZ a écrit :

J'ai bricolé un vague truc : http://fabien.li/temp/fclc.cpp



C'est vraiment super sympa.

Le code est assez moche (beaucoup de redites, tout dans une seule
fonction, et des boucles au lieu des "algorithmes" de la bibliothèque
standard), et inefficace (on stocke beaucoup trop de trucs AHMA).



En tout cas c'est déjà un point de départ pour moi. J'ai déjà commencé à
décortiquer le code (vector<>, map<>, const_iterator, oush_back(), etc.)
et par exemple je découvre les map<> que j'utilisais massivement dans
les langages de script tels que awk, PHP ou JavaScript,

Et en effet je vais tâcher de ne pas laisser tout dans une seule
fonction, à commencer par écrire une fonction d'impression d'un Lignes.

Généralement, quand je résouds un problème de ce style, je me contente
d'un premier jet momoche comme ça, car il s'agit de la résolution
ponctuelle d'un problème unique, et je n'aurai sans doute jamais à
revenir sur ce code, ni même à le réutiliser.

Dans ce cas précis, j'ai l'impression qu'utiliser des closures
améliorerait le code. Faut vraiment que je me penche sur C++-0x.
(Ou que j'implémente ton algo en Javascript...)



Il y a quelques mois j'avais lu un article expliquant les closures en
JavaScript, et il me semblait l'avoir compris, mais j'ai tout oublié. On
a donc l'équivalent en C++ ?

Note les typedef au début :

- Une somme et un produit sont tous les deux des entiers, mais
considérés comme différents ici. C'est pourquoi j'ai créé deux noms
différents pour le type "int".
Malheureusement, il n'y a pas de moyen simple de déclarer deux types
effectivement différents, donc le compilateur ne pourra pas vérifier
que je n'ai pas interverti les deux.



Oui. On gagne en lisibilité, mais effectivement c'est dommage que le
compilateur n'ait pas de moyen de les distinguer pour aider à traquer
les erreurs.

[...]

- Chaque ligne contient un paquet de produits. On pourrait utiliser
aussi bien vector<>, deque<>, list<> ou même set<>. Par conséquent, on
choisit le conteneur par défaut, std::vector<>. D'une manière
générale, choisis toujours vector quand tu n'as pas de raison de
choisir autre chose.



Ok. C'est vrai qu'il semble plus simple.

[...]

Le reste est l'implémentation directe de ton algo, sans fioritures ni
raccourcis.



Encore merci, je vais partir de cet exemple tout en lisant la doc pour
m'habituer, le modifier un peu, puis je m'attaquerai à l'autre énigme.

Cordialement,
--
Olivier Miakinen
Avatar
Fabien LE LEZ
On Thu, 07 Oct 2010 01:40:17 +0200, Olivier Miakinen
<om+:

[closures]
On a donc l'équivalent en C++ ?



Apparemment. Du moins, si j'ai tout bien compris, ce qui est loin
d'être sûr. Cf http://en.wikipedia.org/wiki/C%2B%2B0x
Par ailleurs, si tu as un compilateur un peu vieux (plus de quelques
mois), n'y compte pas trop.
Avatar
Gabriel Dos Reis
Fabien LE LEZ writes:

| On Thu, 07 Oct 2010 01:40:17 +0200, Olivier Miakinen
| <om+:
|
| >[closures]
| > On a donc l'équivalent en C++ ?
|
| Apparemment. Du moins, si j'ai tout bien compris, ce qui est loin
| d'être sûr. Cf http://en.wikipedia.org/wiki/C%2B%2B0x
| Par ailleurs, si tu as un compilateur un peu vieux (plus de quelques
| mois), n'y compte pas trop.

En C++03, il faur bien sûr utiliser les traditionnels
objects fonctionnels. En C++0x, il y aura des lambdas,
mais le support dans les compilateurs actuels est au
plus expérimental.

-- Gaby
Avatar
Marc Boyer
Le 06-10-2010, Gabriel Dos Reis a écrit :
Marc Boyer writes:

| Le 06-10-2010, Gabriel Dos Reis a écrit :
| > Marc Boyer writes:
| >
| >| Le 06-10-2010, Gabriel Dos Reis a écrit :
| >| > Marc Boyer writes:
| >| >| Mais souvent, on fait commencer par un truc genre
| >| >| "algorithmique et structures de données".
| >| >
| >| > Tu fais un cours d'algorithmique et de structures de données
| >| > en C++ à des gens qui ne savent pas programmer en C++ ?
| >|
| >| En quoi faire le cours d'algorithmique et de structures
| >| de données ?
| >
| > Alors c'est « oui » ou c'est « non » ?
|
| Ca dépend du contexte global.
| Si ça ne dépendait que de moi, si on a assez d'heures pour faire
| 4-5 langages dans la formation, je dirais non. Mais je pourrais
| me laisser convaincre de dire oui.
|
| Je me tate.

Je vois bien que tu te tates, mais je ne comprends pas pourquoi
une question aussi simple et totale donne lieu à une réponse qui
n'en est pas une.



Il y a peut-être un souci de grammaire implicite.
Si la question est "est-ce marc boyer fait ces années ci un cours
d'algorithmique et de structures de données en C++", la réponse
est non.
Si la question est "faut-il faire un cours d'algo en C++", ma réponse
est "ça dépend du contexte".

Marc Boyer
--
En prenant aux 10% des francais les plus riches 12% de leurs revenus,
on pourrait doubler les revenus des 10% les plus pauvres.
http://www.inegalites.fr/spip.php?article1&id_mot0
Avatar
Gabriel Dos Reis
Marc Boyer writes:

| Le 06-10-2010, Gabriel Dos Reis a écrit :
| > Marc Boyer writes:
| >
| >| Le 06-10-2010, Gabriel Dos Reis a écrit :
| >| > Marc Boyer writes:
| >| >
| >| >| Le 06-10-2010, Gabriel Dos Reis a écrit  :
| >| >| > Marc Boyer writes:
| >| >| >| Mais souvent, on fait commencer par un truc genre
| >| >| >| "algorithmique et structures de données".
| >| >| >
| >| >| > Tu fais un cours d'algorithmique et de structures de données
| >| >| > en C++ à des gens qui ne savent pas programmer en C++ ?
| >| >|
| >| >| En quoi faire le cours d'algorithmique et de structures
| >| >| de données ?
| >| >
| >| > Alors c'est « oui » ou c'est « non » ?
| >|
| >| Ca dépend du contexte global.
| >| Si ça ne dépendait que de moi, si on a assez d'heures pour faire
| >| 4-5 langages dans la formation, je dirais non. Mais je pourrais
| >| me laisser convaincre de dire oui.
| >|
| >| Je me tate.
| >
| > Je vois bien que tu te tates, mais je ne comprends pas pourquoi
| > une question aussi simple et totale donne lieu à une réponse qui
| > n'en est pas une.
|
| Il y a peut-être un souci de grammaire implicite.
| Si la question est "est-ce marc boyer fait ces années ci un cours
| d'algorithmique et de structures de données en C++", la réponse
| est non.
| Si la question est "faut-il faire un cours d'algo en C++", ma répo nse
| est "ça dépend du contexte".

None of the above.

La qustion est et était :

# Tu fais un cours d'algorithmique et de structures de données
# en C++ à des gens qui ne savent pas programmer en C++ ?

-- Gaby
Avatar
Marc Boyer
Le 07-10-2010, Gabriel Dos Reis a écrit :
La qustion est et était :

# Tu fais un cours d'algorithmique et de structures de données
# en C++ à des gens qui ne savent pas programmer en C++ ?



Non.

Marc Boyer
--
En prenant aux 10% des francais les plus riches 12% de leurs revenus,
on pourrait doubler les revenus des 10% les plus pauvres.
http://www.inegalites.fr/spip.php?article1&id_mot0
Avatar
Gabriel Dos Reis
Marc Boyer writes:

| Le 07-10-2010, Gabriel Dos Reis a écrit :
| > La qustion est et était :
| >
| > # Tu fais un cours d'algorithmique et de structures de données
| > # en C++ à des gens qui ne savent pas programmer en C++ ?
|
| Non.

Donc, tu ne te tatais pas vraiment.
Merci.

-- Gaby
1 2 3 4 5