[quote]Sérieux, je trouve que l’on devrait voir plus de thread comme celui-ci sur ce forum. Toutes les semaines on devrait présenter un problème en C/C++/Java et voir les différentes solutions possibles.[/quote]moi aussi je trouve que c’est une bonne idee, et ca me plait, donc on va le faire
Si on pouvait faire ca le vendredi et eviter d’envoyer 5 problemes dans la meme journee ca serait mieux.
Et si on pouvait eviter une solution complete et plutot des indices plus ou moins fins avant que le problem soit resolut ca serait cool aussi.
Et puis si y en a qui peuvent pas etre connecter toute la journee pour monitorer les progres des gens, je veux bien faire le boulot, mais pas le ouik end.
Un peu d’espace pour ce p**@$$ de bloc
Les templates :
Quelle horreur ! lorqu’on regarde la qualité des services rendus on pleure (si on compare ça à une vrai couche objet et en plus, chose non négligeable, le debugging est une vraie punition du type marcher sur les genoux pendant 10 bornes et ce, en traversant des chemins remplis de cailloux … Rhhaaalll… Dernière précision, les debuggers de type GDB se viandent grave dès que le code est volumineux et un peu compliqué. Putain de STL, oui.
[quote][quote][quote]struct element {
void* element_contenu
struct element* le_suivant
}[/quote]
Moi j’appelle pas ça du pseudo code, j’appele ça du C :-p
Bon, faudrait virer le 2ème struct pour être nickel et que ça passe sur un compilo, mais bon[/quote]
Non non, si pour toi ce bout de code est du C, alors la seule erreur de syntaxe qui me saute aux yeux, ce sont les ‹ ; › qui manquent à la fin de la 2è, 3è et 4è ligne, sinon le struct est absolument nécessaire ici. Après, en C++, je ne sais pas si le mot clef struct est nécessaire, autant que je me souvienne : je ne pense pas, mais un spécialiste du C++ nous dira ce qui est bon ou pas.
Voilà c’était juste pour mettre certaines choses au point à propos du langage C et pour rappeler que le C et le C++ sont deux langages certes ressemblant syntaxiquement mais bel et bien différent. (Je dit ça essentiellement pour ZGoblin, mais ça vaut pour tous les autres) [/quote]Oui exact, c’est en C++ que le struct n’est pas nécessaire. J’ai trop fait de C++ moi…
(d’ailleurs, soit dis en passant, je préfère le C++ au C, pour deux raisons : les templates et la couche objet)
[quote][quote]struct element {
void* element_contenu
struct element* le_suivant
}[/quote]
Moi j’appelle pas ça du pseudo code, j’appele ça du C :-p
Bon, faudrait virer le 2ème struct pour être nickel et que ça passe sur un compilo, mais bon[/quote]
Non non, si pour toi ce bout de code est du C, alors la seule erreur de syntaxe qui me saute aux yeux, ce sont les ‹ ; › qui manquent à la fin de la 2è, 3è et 4è ligne, sinon le struct est absolument nécessaire ici. Après, en C++, je ne sais pas si le mot clef struct est nécessaire, autant que je me souvienne : je ne pense pas, mais un spécialiste du C++ nous dira ce qui est bon ou pas.
Voilà c’était juste pour mettre certaines choses au point à propos du langage C et pour rappeler que le C et le C++ sont deux langages certes ressemblant syntaxiquement mais bel et bien différent. (Je dit ça essentiellement pour ZGoblin, mais ça vaut pour tous les autres)
Pour ceux qui douteraient de son application au niveau professionnel, cette liste double-chaînée à la sauce XOR peut très bien servir entre autres, en algorithmique parallèle (météo, crypto,…), quand on n’utilise pas de mémoire partagée, car là l’espace-mémoire compte : les temps de communication entre noeuds étant assez coûteux, il s’agit de diminuer au possible la taille de ce qui est transmis entre chaque « ordinateur ». Je vais d’ailleurs l’implanter dès la semaine prochaine pour mon TP. Je vois d’ici le gain d’espace, et donc de vitesse globale du programme. Car avoir une double chainée pour le même prix qu’une chaînée, ça se refuse pas
Ouff, j’ai eu peur d’être déçu. On est d’accord Glop . Pour préciser les protections qu’ils faut mettre en place lorsqu’il y a risque de concurrence d’accès, attention d’utiliser celle qui est la plus adaptée. Par exemple s’il y a risque inter-thread on préférera une section critique qui est faite pour, en revanche pour une concurrence inter-process on choisira le mutex.
Attention, je dis ça de mémoire et je n’ai rien sous la main pour vérifier, mais peut importe, le principe c’est de vérifier, le jour où on utilise cette techno, qu’on a choisi le « verrouillage » adéquat.
Heu la solution est tout aussi thread safe qu’une liste chainee a double sens normale. C’est a dire qu’elle ne l’est pas par defaut et qu’il faut rajouter un mutex pour faire une mise a jour, ou sur tt la liste ou juste sur les 2 elements entre lesquels on insere.
Tout ca parceque quel que soit la methode pour implementer la liste doublement chainee, l’operation qui consiste a rajouter une element ou a en suprimer un n’est pas atomique (il faut mettre a jour deux pointeurs).
Donc c’est strictement equivalent a une liste doublement chainee “classique”, mais c’est super facile a rendre thread safe.
Je ne pense pas que ta liste soit « mutlithreadable » Glop. Si lors de ton parcours de liste un autre thread vient modifier cette même liste WALOU ! t’es aux fraises .
Pour garantir du « multithread », y’a pas à chier, il faut protéger les accès via une section critique/mutex ou autres.
Ou alors tu ne parles pas d’OS utilisant le « time slicing ».
Ca veut dire que tu est tout seul a parcourir ta liste a un instant donne. Un seul process/thread peut lire ta liste a la fois. Pour des raisons de performances il est souvent tres utile d’avoir deux ou plusieurs thread/process qui peuvent lire une meme zone de memoire et faire des operations dessus.
Oui, la on est d’accord :calin:
C’est sur, c’est moins elegant que la solution avec le xor. N’empeche, ca respectait quand meme les conditions imposees
Heu… ca veut dire quoi multithreadable ? Je rappelle que je suis pas du tout informaticien, les structures les plus compliquees que j’utilise ca doit etre while et for
[quote]T’as vraiment regarde l’algorithme ? J’ai l’impression que non.
Imaginons que tu es rendu a l’element i. Alors tous les champs « le_suivant » des elements i a la fin de la liste pointent effectivement vers le suivant, mais ceux des elements 0 a i-1 pointent en fait vers l’element predecent (le changement a ete fait lors du parcours de la liste dans le sens direct). Ca marche. L’unique probleme par rapport a ton alogrithme c’est qu’on est oblige de parcourir la liste a partir de l’element en cours, meme si on a conserve l’adresse du premier element par exemple.[/quote]
ha ok j’ai compri, et effectivement c’est pas mal malin :calin: Y a un enorme probleme quand meme avec ta solution tu detruit la liste au fur et a mesure que tu la parcourt. Si t’as A B C, t’es en A, precendent est null et a.le_suivant est B.
Quand tu fais :
buffer=precedent; // donne buffer = null
precedent=en_cours; // donne precedent = A
en_cours=(*en_cours).le_suivant; // donne encours=B
(*precedent).le_suivant=buffer; // donne A.le_suivant = null
Apres etre passe sur un element le pointeur « le_suivant » ne pointe plus vers le suivant mais vers le precedent (tu parles d’intuitif comme nomage, mais bon…). C’est donc non multithreadable et tu dois rederouler la liste une fois parcourue pour tout remttre comme c’etait au debut… pas tres efficace. De plus si tu veux melanger des operation de parcourt de la liste avec des insertion et/ou des suppression ca devient un cauchemard a gerer tes variables globales car les fonctions doivent les mettre a jour…
La solution avec le XOR si elle est contre intuitive par contre est multithreadable et permet d’economiser un octet par element strocke. Sur une liste chainee de couple d’entiers par exemple on gagne 25% de place. On passe de 100 megs a 75 Bien isole dans une classe ou on n’expose pas qu’il y a un XOR c’est meme limite maintenable et utilisable en entreprise La beaute de l’encapsulation. Tout depend bien sur des besoins, il y a des hacks inutilisables et des hacks elegants qui peuvent avoir une application. Compresser du code a la volee c’est deja plus dur a justifier que ca
Sinon pour urdle la definition d’une liste chainee n’a jamais dit qu’avec un element il fallait pouvoir aller au suivant. Un liste chainee c’est juste une liste dont les elements ne sont pas contigus en memoire. Point barre.
C’est la question type pour voir « think outside the box » comme on dit ici, je vous rassure j’avais pas trouve en entretien (c’est pas un prof). Si tu connais pas c’est quasi introuvable, ce qui interesse les gars en entretien c’est la maniere d’aborder le probleme et de voir que ta solution elle marche pas et/ou que tu deplace la pb. Le tout rapidement…
T’as vraiment regarde l’algorithme ? J’ai l’impression que non.
Imaginons que tu es rendu a l’element i. Alors tous les champs « le_suivant » des elements i a la fin de la liste pointent effectivement vers le suivant, mais ceux des elements 0 a i-1 pointent en fait vers l’element predecent (le changement a ete fait lors du parcours de la liste dans le sens direct). Ca marche. L’unique probleme par rapport a ton alogrithme c’est qu’on est oblige de parcourir la liste a partir de l’element en cours, meme si on a conserve l’adresse du premier element par exemple.
tu diras à ton prof qu’il a joué avec les définitions…
techniquement, il ne s’agit pas d’une liste chainée… une liste chainée permet, à partir de n’importe quel élément de la liste, de retrouver son suivant. HORS un element pris seul de la liste NE PERMET PAS DE RETROUVER LE SUIVANT ! On a un pseudo pointeur qui pointe dans le néant quelquepart (très utile).
Pour finir, ce bout de code est astucieux, mais inutilisable et dangereux; et il ne supporte pas le multi-threading [ on ne peut pas le modifier pour avoir la fonction e* suivant(e*) ]
nah…
et j’suis pas borné, parceque j’ai toujours raison, c’est comme ca, c’est inné…
(on m’la fait pas à moi !)
Bon, autant dire tout de suite que si un développeur code comme ça dans mon équipe, c’est mise au point tout de suite et poubelle du code.
Mais cet exercice a le mérite de rappeler les règles du XOR. Je suis un peu frustré de ne pas y avoir pensé, je dois bien le reconnaître , surtout que le XOR était utilisé classiquement pour encoder/crypter un mot de passe par exemple, sur le même principe :
« Mot de passe en clair » XOR « CLE connue par vous seulement » = « Mot de passe crypté ».
Pour le retrouver ? bah comme l’a dit Glop, le contraire.
Je me souviens d’un gros projet pour une boîte française (opérateur télécom historique ). L’une des équipes de développement avait mis en place un compresseur/décompresseur temps réel de … code :casstet: . En clair le code n’était pas déroulé tel que, mais chaque groupe d’instructions était décompressé puis exécuté par le CPU et ainsi de suite… je ne vous dit pas la gueule du chef de projet lorsqu’il a appris ça Le prétexte était le gain de place en mémoire (oui, sur de l’embarqué on a ce genre de contraintes, surtout si le produit doit être déployé en très grand nombre). Mauvaise orientation ! très mauvaise. Les développeurs ce sont fait plaisir quoi, mais d’un point de vue mise au point, maintenance, évolutivité… c’est la misère. En plus, comme chacun sait, la place du code est classiquement négligeable par rapport aux données.
Aller zou, il en faut d’autre des échanges comme cela. Ce qu’il faut faire ET ce qu’il ne faut pas faire est toujours intéressant.
Heu elle marche pas ta solution. Tu veux revenir deux crans en arriere tu peux pas. Si t’appelle precedent deux fois d’affile tu reviens sur le meme… pas tres utile pour parcourir la liste.
… Rhhaaalll… Dernière précision, les debuggers de type GDB se viandent grave dès que le code est volumineux et un peu compliqué. Putain de STL, oui.
Bien isole dans une classe ou on n’expose pas qu’il y a un XOR c’est meme limite maintenable et utilisable en entreprise