Outil de tri de liste

Le
josephb
Salut à tous.

En effet collatéral de la discussion sur les introductions modifiées de MacSoup,
si vous établissez des listes (en /list/ et non pas en suite de lignes) de
"maximes", vous serez sans doute intéressés par ce script de tri très puissant
et très "velu", s'inspirant du célèbre algorithme "Quicksort" et ici transposé
pour Applescript par deux pointures es-programmation et scriptage,
Kevin Bradley & Nigel Garvey.

Ce script, par nature s'utilise depuis l'Editeur de script, alors NE PAS TOUCHER
AU CODE, SVP, mais simplement :

mettez votre liste à trier en vrac dans la variable / A_list / et executez le
script, puis récupérez le résultat trié dans la fenêtre de réponse en bas.

Si vraiment vous êtes NULS au point de ne pas savoir vous en servir, je
l'envelopperai dans une applet passant par le presse-papier, mais franchement je
n'ai pas que ça à faire, sans dec !

J'ai mis un FU2 vers r.comp.sys.mac.programmation
mais j'imagine que personne n'en voudra…

HTH, et bien cordialement,

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞
set A_list to {"eeeeee", "wwwwwww", "hhhhhhh", "rrrrrrr", "bbbbbbb"}
-- votre liste entre les accolades ci-dessus, ne pas toucher au reste !

set SL to quickSort(A_list, "a") -- "a" = tri ascendant, "d" = tri descendant

on quickSort(theList, theDirection) --by Kevin Bradley & Nigel Garvey
--public routine, called from your script
script bs
property alist : theList

on Qsort(leftIndex, rightIndex)
--private routine called by quickSort.
--do not call from your script!
if rightIndex > leftIndex then
set thePivot to ((rightIndex - leftIndex) div 2) + leftIndex
set newPivot to Qpartition(leftIndex, rightIndex, thePivot)
set theList to Qsort(leftIndex, newPivot - 1)
set theList to Qsort(newPivot + 1, rightIndex)
end if
end Qsort

on Qpartition(leftIndex, rightIndex, thePivot)
--private routine called by quickSort.
--do not call from your script!
set pivotValue to item thePivot of bs's alist
set item thePivot of bs's alist to item rightIndex of bs's alist
set tempIndex to leftIndex
repeat with pointer from leftIndex to (rightIndex - 1)
set temp to item pointer of bs's alist
-- temp is set here to save getting the item twice.
if not (temp > pivotValue) then
set item pointer of bs's alist to item tempIndex of bs's alist
set item tempIndex of bs's alist to temp
set tempIndex to tempIndex + 1
end if
end repeat
set item rightIndex of bs's alist to item tempIndex of bs's alist
set item tempIndex of bs's alist to pivotValue --temp
return tempIndex
end Qpartition
end script

if length of bs's alist > 1 then bs's Qsort(1, length of bs's alist)

if theDirection is "d" then return the reverse of bs's alist
return bs's alist
end quickSort
∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

--
J. B.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
michel.vauquois
Le #26398081
Parlons peu, parlons bien : bonjour !

Le sublime Joseph-B, abandonnant sa badelaire pour quelques instants,
par ces mots choisis nous distille :

J'ai mis un FU2 vers r.comp.sys.mac.programmation
mais j'imagine que personne n'en voudra…



Tu aurais dû le diapublier sur les deux forums...
À part ça, le script est très efficace ! ;-)
--
Michel Vauquois
Que Dieu vous garde... Moi j'ai pas le temps (RD)
MàJ 2015 : Matière à voir :
pdorange
Le #26398088
M.V.
arlons peu, parlons bien : bonjour !

Le sublime Joseph-B, abandonnant sa badelaire pour quelques instants,
par ces mots choisis nous distille :

> J'ai mis un FU2 vers r.comp.sys.mac.programmation
> mais j'imagine que personne n'en voudra…

Tu aurais dû le diapublier sur les deux forums...
À part ça, le script est très efficace ! ;-)



En même temps je suis pas bien sur l'intérêt de faire ça en AppleScript,
en même je suis pas objectif j'ai toujours détesté ce langage.

Juste pour info on fait la même chose (tri rapide d'un liste) avec un
Script python de 2 lignes :

list=["eeeeee", "wwwwwww", "hhhhhhh", "rrrrrrr", "bbbbbbb"]
print list.sort()

Ce sera probablement bien plus rapide que AppleScript.
Certes par défaut Python n'utilise pas l'algorithme QuickSort mais
TimSort (1) très efficace (TimSort vs QuickSort provoque de longue
discussion (stérile) sur les forums dev) ; mais on trouve aussi
facilement une implémentation QuickSort en Python (2).

(1) https://en.wikipedia.org/wiki/Timsort
(2)
http://danishmujeeb.com/blog/2014/01/basic-sorting-algorithms-implemented-in-python
--
Pierre-Alain Dorange Moof
Ce message est sous licence Creative Commons "by-nc-sa-2.0"
josephb
Le #26398122
Pierre-Alain Dorange estime devoir nous faire part de ceci :

En même temps je suis pas bien sur l'intérêt de faire ça en AppleScript,
en même je suis pas objectif j'ai toujours détesté ce langage.



L'intérêt est que justement un langage évolué comme AppleScript n'a
jamais nativement comprté de fonction de tri, ce que je trouve un peu
fort de café.
Donc j'ai mis ce script à disposition.

Il y a des "additions" qui pallient ce manque, dont l'excellent
"Satimage" (qui fait des milliards de trucs autres), mais tout le monde
ne l'a pas sur son Mac.


Juste pour info on fait la même chose (tri rapide d'un liste) avec un
Script python de 2 lignes :

list=["eeeeee", "wwwwwww", "hhhhhhh", "rrrrrrr", "bbbbbbb"]
print list.sort()



Tout comme la commande "sortlist" de Satimage écrite en C est
hyper-rapide.

Ce sera probablement bien plus rapide que AppleScript.


Alors là, pas l'ombre d'un doute !

Certes par défaut Python n'utilise pas l'algorithme QuickSort mais
TimSort (1) très efficace (TimSort vs QuickSort provoque de longue
discussion (stérile) sur les forums dev) ; mais on trouve aussi
facilement une implémentation QuickSort en Python (2).



De toute façon il y a toujours un moment où un algorithme de tri est
"mauvais" en terme de performance et Quicksort plus la liste est
pré-triée, moins il est efficace, mais dans la vie de tous les jours,
qui s'en soucie… Comme tu dis ce sont des débats d'enfileurs de mouche.
TimSort, je ne connais pas.

Quand la rumeur est venue qu'Aple allait ouvrir son Editeur de Script à
un autre langage, j'ai espéré un moment que ce puisse être Python ou
Ruby, mais non c'est javascript…


--
J. B.
josephb
Le #26398121
M.V. a prestement tapoté de ses doigts agiles :

Tu aurais dû le diapublier sur les deux forums...
À part ça, le script est très efficace ! ;-)



Oui, j'ai molé la diapublication.

--
J. B.
pdorange
Le #26398150
Joseph-B
> Juste pour info on fait la même chose (tri rapide d'un liste) avec un
> Script python de 2 lignes :
>
> list=["eeeeee", "wwwwwww", "hhhhhhh", "rrrrrrr", "bbbbbbb"]
> print list.sort()

Tout comme la commande "sortlist" de Satimage écrite en C est
hyper-rapide.

> Ce sera probablement bien plus rapide que AppleScript.
Alors là, pas l'ombre d'un doute !



Faut pas, dans beaucoup de cas TimSort est plus rapide que QuickSort.
De python l'overhead de python est très faible par rapport a celui
d'AppleScript.
Moi je doute pas je suis même certain.




--
Pierre-Alain Dorange Moof
Ce message est sous licence Creative Commons "by-nc-sa-2.0"
Publicité
Poster une réponse
Anonyme