ca existe, des listes dont le type n’est pas constant ?? B)
Sinon moi je testerais d’abord le type de chaque champs, s’il est identique le contenu de chaque champs (donc ca sent le switch avec une fonction de comparaison pour chaque type de donnees) mais comme je n’y connais rien en perl, je sais meme pas si c’est possible
Quelqu’un à une idée d’algo simple pour résoudre ce problème ?[/quote]
Ha y a un truc il me semble. Tu parcours une fois ta liste 1 et pour chaque element tu initialises un tableau ou une hash ( genre clef ton element, value un boolean true ou n’importe quoi l’essentiel etant que ca existe).
Ensuite tu parcours ta liste 2 et pour chaque element tu cherches dans ta map ou ton tableau s’il une correspondance. S’il n’y en pas, les 2 listes ne sont pas identiques.
C’est pas très formel, mais l’idée est là.
ça dépend de la taille de tes listes, et de si tu as besoin d’un truc bien optimisé ou pas, mais une solution serait, pour chaque élément de la liste A, de parcourir la liste B pour voir s’il existe dans celle-ci. dès qu’un élément de A n’existe pas dans B, tu retournes faux, et si tu as fini de parcourir A et que tu as trouvé tous ses éléments dans B tu retournes vrai. (bien sur, je suppose qu’avant tout ça tu as commencé par comparer la longueur des deux listes, et retourné faux si elle n’est pas identique)
Alors je connais pas du tout perl, mais voilà quand même ce que je ferais :
Je créerait une fonction de hash (au hasard, md5 ou un de ses amis) sur chacun de tes types, qui va te retourner une chaine de caractères ou un entier (un truc que tu puisses trier facilement), et au fur et à mesure, je met ça dans une structure triée (au hasard, arbre coloré, probablement deja implémenté en perl, probablement sous un nom du style map ou set).
Quand j’ai fait ca avec mes n listes non triées, je me retrouve avec n listes triées qui ont toutes un type bien défini et sur lesquels tu peux faire des comparaisons d’objets…
En espérant que ca aide
Drealmer : rhaa, ca donne envie de discuter optim, là… ne pas pourrir le thread, ne pas pourrir le thread…
Sinon, la “Patate” d’allocation devient de moins en moins problématique, hein… Surtout que si on connait par avance la taille de notre arbre, on peut l’éviter assez facilement B) sans parler du fait que j’ai horreur de faire en 2 fois ce que je pourrais faire en une B)
Attention à l’abus de structures triées B) Les arbres c’est bien quand on a besoin d’un truc qui soit tout le temps trié, à chaque insertion. Quand on veut dans un premier temps insérer un grand nombre d’éléments, et ensuite faire des recherches dessus, c’est plus efficace d’utiliser un « bête » vecteur. On met tout dedans, on trie, et ensuite on cherche de façon dichotomique. L’avantage c’est que les data sont en un seul bloc, y’a pas la patate d’allocations dynamiques, et pas d’indirections de pointeurs à faire dans tous les sens.
[quote=« LoneWolf, post:2, topic: 45891 »]ca existe, des listes dont le type n’est pas constant ?? B)
LoneWolf
C’est zarbi le perl B)[/quote]
Je développe un objet qui implémente l’interface java.util.Map de Java (un équivalent au java.util.HashMap donc), hors en Perl tout comme en Java avant l’arrivé des types génériques, on peut mettre tout et n’importe quoi dans les valeurs du table de hashage voir même plus, car on a le droit de mettre aussi des types scalaires (équivalent au type primitif Java).
Donc dans mes tests unitaires, si je veux tester la méthode elements qui retournera dans mon cas une liste non triée, il faut que je prévoie le plus large possible
[quote=« doumdoum, post:3, topic: 45891 »]Ha y a un truc il me semble. Tu parcours une fois ta liste 1 et pour chaque element tu initialises un tableau ou une hash ( genre clef ton element, value un boolean true ou n’importe quoi l’essentiel etant que ca existe).
Ensuite tu parcours ta liste 2 et pour chaque element tu cherches dans ta map ou ton tableau s’il une correspondance. S’il n’y en pas, les 2 listes ne sont pas identiques.
C’est pas très formel, mais l’idée est là.[/quote]
Bonne idée, mais le problème avec les hashs en perl, c’est que les clés (contrairement au valeur) ne peuvent être que des scalaires (chaines et nombre) on ne peut pas mettre de valeur nulle ou d’objet.
Je pense que je vais adopté cette solution, ce n’est surement pas la plus optimisée, mais si je prévoie la suppression de chaque élément trouvé, les performances devraient être acceptable et ça me permettra de gérer le cas où plusieurs valeurs identiques se trouvent dans mes listes.
Sinon comparer tous les elements d’une liste a l’autre c’est une complexite quadratique bonjour la cata, en revanche c’est du O(1) pour la memoire.
Tu dois pouvoir tout hasher en perl il faut juste fournir la fonction de hashage a chaque fois. Es-tu vraiment sur que ta liste peut contenir n’importe quoi ? Ca peut valoir le coup de se casser la tete car tu passerais alors en complexite lineaire pour une occupation lineaire de la memoire.
Concretement ca veut dire que pour une liste d’un million d’element dans la solution un tu fais au mieux 1000 milliards d’operations contre un million dans la seconde.
Si tes listes sont petites c’est pas grave (mais bon hein si on peut faire un ch’tit algo qui tue). B)
Sinon, un peu crade et un peu stochastique, et bien optimisé, surtout si tu as plein d’éléments :
Bon ,tu commence par comparer le nombre d’elements.
Tu XORise tout les MD5 de chacun des elements de la premiere liste.
Tu fais pareil pour la seconde.
Si tes deux listes sont identiques, t’auras le même résultat.
Si t’as pas le même résultat, c’est que tes listes sont différentes.
Bon, ok, t’as une toute petite chance sur beaucoup pour avoir un faux positif, a toi de voir…
[quote=“Moloch, post:8, topic: 45891”]Est-ce que ceci resoud ton probleme ?
Sinon comparer tous les elements d’une liste a l’autre c’est une complexite quadratique bonjour la cata, en revanche c’est du O(1) pour la memoire.
Tu dois pouvoir tout hasher en perl il faut juste fournir la fonction de hashage a chaque fois. Es-tu vraiment sur que ta liste peut contenir n’importe quoi ? Ca peut valoir le coup de se casser la tete car tu passerais alors en complexite lineaire pour une occupation lineaire de la memoire.
Concretement ca veut dire que pour une liste d’un million d’element dans la solution un tu fais au mieux 1000 milliards d’operations contre un million dans la seconde.
Si tes listes sont petites c’est pas grave (mais bon hein si on peut faire un ch’tit algo qui tue). B)[/quote]
Ton module ne correspond pas à mes besoins car il utilise la fonction sort, ça tombe à l’eau.
Pour la comparaison des éléments un par un, je suis bien consient de la complexité de l’algorithme, cependant, il va être utiliser dans mon cas uniquement dans le cadre des tests unitaires, j’ai donc besoin d’un code sur à 110% qui prévoit tous les cas à la con (car effectivment, comparer des nombres, des chaines, des objets et des valeurs nulles s’est vraiment débile) et qui va n’être utilisé que sur des listes assez petites (on ne dépassera jamais les 100 éléménts). Je vais finalement utiliser cette méthode.
Pour une comparaison dans une utilisation réelle, je ne stockerai jamais différents types dans mes listes et je pourrait donc utiliser un algoritme bien plus optimisé.
En tout cas, merci pour vos différentes propositions qui m’ont permis de comparer toutes les solutions et de choisir la mieux adapter à mon problème.