Possibilité d'un Tri 'bizarre' sur fichier txt

Bonjour et bonne année (et tout ce qui va avec :),

J'ai un fichier texte contenant des valeurs sous cette forme (2 'identificateurs' positionné selon un troisieme champs 'opérande'):

Code:

---

1 2 3 4 5 6 7

x1 x2 < x1 x3 < x3 x3 = x1 x9 > x2 x3 > etc...

---

En gros on dit que x1 < x2, x1 < x3 mais vu que x2 > x3 on obtient une liste du style (ordre décroissant) : x1, x3, x2 etc...

J'ai comme ça un fichier de plus de 9000 lignes de ce type.
Y aurait-il possibilité d'automatiser tout ça (sachant que c'est un pré-traitement nécessaire temporairement vu qu'on est en train d'essayer de mettre en place le fichier 'déjà trié' avec le fournisseur mais faut bien traité les anciens fichiers...) ?

Si oui, est ce que Perl peut faire ce truc (j'ai juste entendu parler du langage, j'ai pas eu encore l'occasion ni le temps d'experimenter pour le moment mais je vais mettre ça en résolution n°530 pour 2009 ;) ) ?

Merci par avance de vos lumières :)

Oui ,Perl pourrait le faire. Je pense (Jedaï pourrait confirmer ?) que Haskell ou Ocaml ferait bien l'affaire avec une fonction de type qsort:

Code:

---

1 2 3 4 5 6

qsort [] = [] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x where elts_lt_x = [y | y <- xs, y < x] elts_greq_x = [y | y <- xs, y >= x]

---

Code:

---

1 2 3 4 5 6

let rec quicksort = function | [] -> [] | pivot :: rest -> let is_less x = x < pivot in let left, right = List.partition is_less rest in quicksort left @ [pivot] @ quicksort right

---

Citation:

---

Envoyé par kuzco

Oui ,Perl pourrait le faire. Je pense (Jedaï pourrait confirmer ?) que Haskell ou Ocaml ferait bien l'affaire avec une fonction de type qsort:

Code:

---

1 2 3 4 5 6

qsort [] = [] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x where elts_lt_x = [y | y <- xs, y < x] elts_greq_x = [y | y <- xs, y >= x]

---

Code:

---

1 2 3 4 5 6

let rec quicksort = function | [] -> [] | pivot :: rest -> let is_less x = x < pivot in let left, right = List.partition is_less rest in quicksort left @ [pivot] @ quicksort right

---

---

Merci Kuzco mais je suis sur mac donc pour Haskell et Ocaml ... faut macport ou fink obligatoire d'après ce que j'ai vu (et j'ai pas compris ton code :( )

Je vais tenter de voir sous perl : je suis tombé sur des articles sur les tris mais je m'y perds un peu.

C'est censé être une sorte de tri 'pyramidale' en fait basé sur un fichier de ce type en entrée :

Code:

---

1 2 3 4 5 6 7 8 9 10

x0 x0 = x0 x1 > x0 x2 > x1 x0 < x1 x1 = x1 x2 < x2 x0 < x2 x1 > x2 x2 =

---

qui donnerait en sortie ça : x0 > x1 > x2.

Je creuse je creuse :)

J'ai fais un script 'cognio' rien de complexe mais noob inside so ;)
Le fichier res_10.txt est un echantillonage du style "x0 x1 >" sur une 100aine de lignes (x0 à x10).

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#!/usr/bin/env perl use strict; use warnings;   open(FILE,"<res_10.txt")||die "Erreur - $! : ouverture de fichier\n"; my ($i,,@tabfile,@tabtri); $i=0; while(<FILE>) { $i ++; print "$_"; push (@tabfile,$_); } print "\n Nbre de ligne : $i\n"; close FILE||die "Erreur - $! : fermeture de fichier\n";   @tabtri=sort(@tabfile); print "@tabtri\n"; __END__

---

Par contre, j'ai maintenant un pb pour le tri (qui est simplement un sort, pas bon mais c'était pour le placer, dans le code ci-dessus)... en fait je n'arrive pas à passer du yahourt suivant à Perl :

Code:

---

1 2 3 4 5 6

Pour chaque ligne, si element3="<" alors element1 avant element2 si element3=">" alors element1 apres element2 si element3="=" alors ne pas traiter la ligne fin pour chaque

---

Parce que bien entendu il faudra traiter toutes les lignes du fichier...

Haskell est disponible sous Mac OS X sans macport ou fink semble-t-il.
Mais de toute façon la question n'est pas là. Les fonctions présentées par kuzco n'apportent rien par rapport à sort() en Perl (ou le sortBy de Haskell).

D'une part est-ce que toutes les paires d'éléments sont représentés dans ton fichier ? Si non as-tu une garantie que les contraintes sont cohérentes ? L'ordre est-il partiel ? Si oui sais-tu ce qu'est un tri topologique ? Parce que c'est ce que tu vas devoir utiliser dans ce cas.

--
Jedaï

Merci pour le lien concernant Haskell (je viens de voir qu'il y avait aussi un .dmg pour Ocaml) -> je m'en occuperais plus tard :)

Concernant les paires d'éléments elles sont bien toutes représentées : si je prends l'intervalle x0 à x50 j'ai bien x0-x0, x0-x1....x49-x48,x49-x50,....x50-x47,x50-x48,x50-x49,x50-x50.

Concernant les données, voilà les élements que j'ai :
chaque x représente un ensemble et le signe représente le plus petit élément de la différence symétrique de ces ensembles.
par exemple si x5 = {2325,23,0} et que x2 ={43290, 2325,23,5}, la diff.symétrique sera {43290,5,0}. Etant donné que 0 appartient à x5, on aura donc la ligne " x5 x2 < " (car x5<x2).
La difficulté étant ici d'organiser ces 'ensembles'.

Après, de là à dire que l'ordre est partiel... je pense vu qu'on ne peut pas comparer un ensemble à lui même (ce qui explique la présence du signe = dont il ne faut pas s'occuper : par ex. x5 = x5).

Concernant le tri topologique, je viens de faire une recherche mais... ça parler de truc issu d'un autre univers :( :marteau:

Après quelques petits errements, il me semble qu'en fait il doit bien s'agir d'un ordre total. Tout les éléments sont comparables deux à deux.

Et en fait, pour en revenir au fichier, il me semble qu'on peut se simplifier la vie en faisant une inversion des < pour qu'ils deviennent des >.
Par exemple

Code:

---

1 2

x2 x1 <

---

est transformé en

Code:

---

x1 x2 >

---

Quand on a plus que ça dans le fichier( ou en mémoire, c'est pareil) il suffira de compter le nombre de fois où x1 est en colonne 1 pour savoir à combien d'éléments il est supérieur.
Cet algorithme ne doit pas être trop compliqué à écrire, il me semble.

Ca pourrait donner (en pseudo perl)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

while(<F>) { ($col1,$col2,$signe)=split("\s+",$_); next if ($signe eq "="); if ($signe eq "<"){ ($col2,$col1)=($col1,$col2); # je ne suis pas sur qu'on puisse inverser ainsi, mais bon }   if (not exists $nboccurences{$col1}){ $nboccurences{$col1}=1 ; }else{ $nboccurences{$col1}++; } if (not exists $nboccurences{$col2}){ $nboccurences{$col2}=0; } }

---

Une fois qu'on a ça, il doit suffire de trier le hash sur les valeurs, et roule.

Sans rentrer dans le codage pur, on doit pouvoir s'en sortir de la façon suivante :

1. On construit en lisant le fichier origine un hash de hash %mapOrdre tq
$mapOrdre{x}{y} = 0,1 ou -1 selon ce qu'il y a dans le fichier
si on a
x y < : -1
x y = : 0
x y > : 1

Pas dur à faire.

2. On récupère dans un tableau @ta toutes les valeurs x et y du fichier. Pas dur à faire non plus. Faut juste dédoublonner. Le plus simple étant d'ajouter les x y dans un hash puis de récupérer les valeurs de clefs dans un tableau.

3. Reste à trier le tableau en utilisant une fonction ad-hoc

Code:

---

1 2	my @taTrie = sort adhoc @ta.

---

Avec la fonction de tri adhoc qui travaille sur les paramètres 'implicites' $a et $b, représentant les éléments à comparer :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

sub adhoc { my $iRetVal = $mapOrdre{$a}{b};   die "Paire $a $b inconnue" if not defined $iRetVal;   return $iRetVal;     }

---