SORT sur blocs enchassés
Philippe11-Jun-2006/1:18:17+2:00
Salut,
J'ai un petit problème : je récupére deux blocs du genre :

blk1: [ [4 num1] [10 num3] [4 num4] ]
blk2: [ [1 num1] [3 num7] [2 num4] ]
soit des blocs de blocs à 2 éléments : un ranking et un id .

et je veux obtenir une seule liste, ordonnée, avec un tri par ranking, sachant que si un id se retrouve dans les deux listes on ajoute ses valeurs de ranking, comme :

blk: [ [10 num3] [6 num4] [5 num1] [3 num7]]

Vous vous en doutez, c'est pour afficher des résultats de recherche. Quelqu'un a une idée ?

===Philippe
reboltof11-Jun-2006/10:02:57+2:00
La difficulté, c'est que la valeur sur laquelle la recherche doit être effectuée est à l'intérieur d'un block!, donc protégée...

Moi, je procéderais en étapes successives, de la manière suivante:

blk1: [ [4 num1] [10 num3] [4 num4] ]
blk2: [ [1 num1] [3 num7] [2 num4] ]

insert blk1 blk2

target: copy []

foreach data blk1 [
either find target id: data/2 [
change value: back find target :id value/1 + data/1
] [
append target data
]
]

sort/skip/reverse target 2

>> TARGET is a block of value: [10 num3 6 num4 5 num1 3 num7]

Le résultat peut alors être remis en "blocs" si nécessaire...
DocKimbel11-Jun-2006/11:36:29+2:00
blk: join blk1 blk2
sort/compare blk func [A B][A/1 > B/1]

== [[10 num3][4 num4][4 num1][3 num7][2 num4][1 num1]]

KISS! (Keep It Simple and Stupid)
--
DocKimbel
DocKimbel11-Jun-2006/11:56:49+2:00
Oops, j'ai lu un peu trop vite la demande initiale !

--
DocKimbel

PS: retaper son login/pass à chaque envoi, c'est pas tip-top...
DocKimbel11-Jun-2006/12:32:17+2:00
Bon vu que j'ai répondu à coté, je me penche plus sérieusement sur la question. Voici ma proposition de solution :


blk1: [ [4 num1] [10 num3] [4 num4] ]
blk2: [ [1 num1] [3 num7] [2 num4] ]

blk: join blk1 blk2
sort/compare blk func [A B][A/2 < B/2]
base: none
rank: 1
id: 2
forall blk [
new: first blk
either all [
base
new/:id = base/:id
][
poke base 1 base/:rank + new/:rank
change blk [()]
][
base: new
]
]
sort/compare compose head blk func [A B][A/1 > B/1]

== [[10 num3] [6 num4] [5 num1] [3 num7]]


Commentaires:
------------

1) on réunit les 2 blocs en un seul.

2) on les classe par 'id. (les 'id identiques se suivent alors)

3) on parcourt un à un tous les éléments afin d'effectuer :
- le cumul des ranking par 'id.
- l'élimination des blocs cumulés pour ne garder que le 1er exemplaire.
(on utilise le fait que les blocs ayant les memes 'id, soient consécutifs)

4) on supprime effectivement les blocs en trop avec 'compose. (astuce: compose [()] == [])

5) on tri les 'id uniques et cumulés par rank.

6) Fin.


L'approche de Reboltof est plus simple et plus claire que la mienne. La différence se fait sur la complexité de l'algo utilisé:
- celui de Reboltof est en O(n^2)
- le mien est (à vue de nez) en O(n*log(n))
(c'est simplement le coût du tri par 'sort, la boucle 'forall étant en O(n))

Voilà tout.
--
DocKimbel
reboltof11-Jun-2006/12:58:31+2:00
En tout cas, cela me fait découvrir le 'sort/compare couplé à une fonction, que je n'avais encore jamais utilisé...

Thanks !
Philippe12-Jun-2006/12:11:25+2:00
Salut,

Merci des réponses très instructives.
Par contre, à la fin, un sort/reverse simple donne le bon ordre, non ?

sort/reverse [ [1 num1] [3 num7] [3 num2] [2 num4] [10 num3]]
== [[10 num3] [3 num7] [3 num2] [2 num4] [1 num1]]

PS. Pour le login/pass, on y travaille .
DocKimbel12-Jun-2006/21:25:35+2:00
Oui, celà marche aussi!

Le tri est bien effectué par rapport au 1er élément de chaque block. Encore une comportement de REBOL non-documenté...mais bienvenu!

--
DocKimbel
coccinelle16-Jun-2006/7:56:59+2:00
Cela va plus loin car l'on peut facilement préciser sur quel(s) élément(s) du block on veut faire le tri. Par exemple, si l'on veut trier sur le 2ème élément des blocs, il suffit de faire ainsi (notez que j'ai inversé lordre des éléments dans les blocs):

sort/reverse/compare [[num1 1] [num7 3] [num2 3] [num4 2] [num3 10]] 2
== [[num3 10] [num7 3] [num2 3] [num4 2] [num1 1]]

On peut aussi trier sur plusieurs éléments sans problème :

sort/reverse/compare [[num1 1 5] [num7 3 2] [num2 3 3] [num4 2 2] [num3 10]] [2 3]
== [[num3 10] [num2 3 3] [num7 3 2] [num4 2 2] [num1 1 5]]

Il faut relever que les performances sont meilleures qu'avec une fonction si le nombre d'occurrence est élevé.

Finalement, j'arriverais à quelque chose comme ça :

blk1: [ [4 num1] [10 num3] [4 num4] ]
blk2: [ [1 num1] [3 num7] [2 num4] ]

blk: sort/compare join blk1 blk2 2
forall blk [
if all [
blk/2
blk/1/1 = blk/2/1
][
change blk blk/1/1 + blk/2/2
remove next blk
]
]
blk: sort/reverse/compare head blk 1
== [[10 num3] [4 num1] [4 num4] [3 num7] [2 num4] [1 num1]]

J'ai aussi remplacé l'astuce change blk [()] a été remplacée par remove qui va tout aussi bien (et est un peu plus lisible).

Voilà voilà, Marco.
coccinelle16-Jun-2006/8:37:04+2:00
Cela va plus loin car l'on peut facilement préciser sur quel(s) élément(s) du block on veut faire le tri. Par exemple, si l'on veut trier sur le 2ème élément des blocs, il suffit de faire ainsi (notez que j'ai inversé lordre des éléments dans les blocs):

sort/reverse/compare [[num1 1] [num7 3] [num2 3] [num4 2] [num3 10]] 2
== [[num3 10] [num7 3] [num2 3] [num4 2] [num1 1]]

On peut aussi trier sur plusieurs éléments sans problème :

sort/reverse/compare [[num1 1 5] [num7 3 2] [num2 3 3] [num4 2 2] [num3 10]] [2 3]
== [[num3 10] [num2 3 3] [num7 3 2] [num4 2 2] [num1 1 5]]

Il faut relever que les performances sont meilleures qu'avec une fonction si le nombre d'occurrence est élevé.

Finalement, j'arriverais à quelque chose comme ça :

blk1: [ [4 num1] [10 num3] [4 num4] ]
blk2: [ [1 num1] [3 num7] [2 num4] ]

blk: sort/compare join blk1 blk2 2
forall blk [
if all [
blk/2
blk/1/1 = blk/2/1
][
change blk blk/1/1 + blk/2/2
remove next blk
]
]
blk: sort/reverse/compare head blk 1
== [[10 num3] [4 num1] [4 num4] [3 num7] [2 num4] [1 num1]]

J'ai aussi remplacé l'astuce change blk [()] a été remplacée par remove qui va tout aussi bien (et est un peu plus lisible).

Voilà voilà, Marco.
coccinelle16-Jun-2006/8:48:40+2:00
Après quelques vérification, je me suis apperçu que le code que j'avais donnée ne fonctionnait pas. Voici quelque chose de mieux :

blk1: [ [4 num1] [5 num7] [10 num3] [4 num4]]
blk2: [ [1 num1] [1 num1] [3 num7] [2 num4] [5 num4]]
rank: 1
id: 2

blk: sort/compare join blk1 blk2 id
while [not tail? next blk] [
   either all [
      blk/1/:id = blk/2/:id
   ][
      poke blk/1 rank blk/1/:rank + blk/2/:rank
      change/part/only blk blk/1 2
   ][
      blk: next blk
   ]
]
blk: sort/reverse/compare head blk rank
== [[11 num4] [10 num3] [8 num7] [6 num1]]

Avec le while, je contrôle mieux la boucle et ainsi, un même Id peut se retrouver autant de fois que l'on veut, et en plus aussi bien en début qu'en fin de séries (et même au milieu).

J'ai aussi opté pour un change/part au lieu du remove, simplement pour illustrer l'astuce.

Voili voilà, Marco
reboltof16-Jun-2006/9:38:48+2:00
Petite illustration de la puisance de 'sort/compare...

blk1: [ [4 num1] [10 num3] [4 num4] [6 num8] ]
blk2: [ [1 num1] [3 num7] [2 num4] [10 num7] [3 num1]]

blk: join blk1 blk2

loop 2 [sort/compare blk func [a b] [either a/2 = b/2 [b/2: 'num0 a/1: a/1 + b/1] [a/2 < b/2]]]
remove-each bl blk [bl/2 = 'num0]

>> BLK is a block of value: [[8 num1] [10 num3] [6 num4] [13 num7] [6 num8]]

Remarquez que, comme le bloc est modifié dynamiquement, cela semble avoir une influence sur l'algorithme de comparaison de la fonction. Il est nécessaire d'exécuter 2x la fonction afin d'être sûr de ne rater aucune occurence. Mais ça fonctionne ...
Philippe16-Jun-2006/13:16:44+2:00
Remarquable !

Puisque vous êtes chaud, question subsidiaire :

blk1: [ [4 num1] [10 num3] [4 num4] [6 num8] ]
blk2: [ [1 num1] [3 num7] [2 num4] [10 num7] [3 num1]]

blk: join blk1 blk2

et je veux obtenir :

resultat: [ num1 [1 4 3] num3 [10] num 4 [4 2 ] num7 [3 10] ...]

(j'abuse, n'est-ce pas ?)
reboltof16-Jun-2006/13:31:40+2:00
Maaaaais non

Là l'emploi de 'sort/compare n'a plus trop de sens puisque l'on doit changer la structure initiale...
Retour à une programmation moins ésotérique:

blk1: [ [4 num9] [10 num3] [4 num4] [6 num8] ]
blk2: [ [1 num1] [3 num7] [2 num4] [10 num7] [3 num1]]

blk: join blk1 blk2

result: copy []

foreach bl blk [
either find result bl/2 [append select result bl/2 bl/1][append result compose/deep [(bl/2) [(bl/1)]]]
]

sort/skip result 2

>> RESULT is a block of value: [num1 [1 3] num3 [10] num4 [4 2] num7 [3 10] num8 [6] num9 [4]]
DideC16-Jun-2006/13:35:30+2:00
J'avais ça en tête (modif dans la fonction de comparaison) et j'avais fait des tests.

CA NE MARCHE PAS !

Si les données sont plus nombreuses, il y a des ID qui ne sont pas comparés et donc pas regroupés.
reboltof16-Jun-2006/14:26:17+2:00
Maaaaais non

Là l'emploi de 'sort/compare n'a plus trop de sens puisque l'on doit changer la structure initiale...
Retour à une programmation moins ésotérique:

blk1: [ [4 num9] [10 num3] [4 num4] [6 num8] ]
blk2: [ [1 num1] [3 num7] [2 num4] [10 num7] [3 num1]]

blk: join blk1 blk2

result: copy []

foreach bl blk [
either find result bl/2 [append select result bl/2 bl/1][append result compose/deep [(bl/2) [(bl/1)]]]
]

sort/skip result 2

>> RESULT is a block of value: [num1 [1 3] num3 [10] num4 [4 2] num7 [3 10] num8 [6] num9 [4]]
reboltof16-Jun-2006/14:27:51+2:00
Oups un refresh involontaire... Ignorez le post précédent !
reboltof16-Jun-2006/14:30+2:00
Didec > CA NE MARCHE PAS !

C'est la raison d'être du 'loop. Celui-ci est sans doute à effectuer un nombre de fois proportionnel au nombre d'éléments du bloc à classer....

Login required to Post.


Powered by RebelBB and REBOL 2.7.8.4.2