Tuesday, December 10, 2019

#1 2010-07-19 08:09:21 pm

timwilson
Member
Registered: 2010-07-19
Posts: 14

How to sort a list of records by a specific property

Hi all,

I've got a list of records, and I'd like to sort the list by one of the properties of each record. Consider a list like the following:

myList = {{age:23, name:"Bob"}, {age:14, name:"Susie"}, {age:37, name:"Jim"}}

After a sort by age, I'd like to have it in the form:

myList = {{age:14, name:"Susie"}, {age:23, name:"Bob"}, {age:37, name:"Jim"}}

What's the best approach to do this?

Thanks.

-Tim

Offline

 

#2 2010-07-19 10:16:48 pm

mikerickson
Member
Registered: 2008-10-26
Posts: 437

Re: How to sort a list of records by a specific property

This is a bubble sort method

Applescript:

set myList to {{age:23, name:"Bob"}, {age:14, name:"Susie"}, {age:37, name:"Jim"}}

repeat with i from 1 to (count of myList) - 1
   repeat with j from i + 1 to count of myList
       if age of item j of myList < age of item i of myList then
           set temp to item i of myList
           set item i of myList to item j of myList
           set item j of myList to temp
       end if
       log myList
   end repeat
end repeat

return myList

Offline

 

#3 2010-07-19 10:45:30 pm

timwilson
Member
Registered: 2010-07-19
Posts: 14

Re: How to sort a list of records by a specific property

Ah, the dreaded bubble sort. Thanks for the help, Mike. I'll give this a go.

-Tim

Offline

 

#4 2010-07-20 02:53:58 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5118

Re: How to sort a list of records by a specific property

Bubble sort is one of the least efficient sort algorithms ever invented and most AppleScript implementations I've seen are themselves sub-optimal, but it does the job and is fine for short lists.

Here, for the sake of it, is a customisable bubble sort. It does the actual sorting, but delegates the comparison of the items to a handler you pass to it in a script object. So instead of having to write separate sorts to arrange Tim's records by age or by name, you just have one sort to which you pass the appropriate comparison method:

Applescript:

on customBubbleSort(thelist, compObj)
   script o
       property lst : thelist
   end script
   
   repeat with i from (count thelist) to 2 by -1
       set a to beginning of o's lst
       repeat with j from 2 to i
           set b to item j of o's lst
           if (compObj's isGreater(a, b)) then
               set item (j - 1) of o's lst to b
               set item j of o's lst to a
           else
               set a to b
           end if
       end repeat
   end repeat
end customBubbleSort

script byAge
   on isGreater(a, b)
       (a's age > b's age)
   end isGreater
end script

script byName
   on isGreater(a, b)
       (a's name > b's name)
   end isGreater
end script

set myList to {{age:23, name:"Bob"}, {age:14, name:"Susie"}, {age:37, name:"Jim"}}

customBubbleSort(myList, byAge)
myList --> {{age:14, name:"Susie"}, {age:23, name:"Bob"}, {age:37, name:"Jim"}}

customBubbleSort(myList, byName)
myList --> {{age:23, name:"Bob"}, {age:37, name:"Jim"}, {age:14, name:"Susie"}}

By the way, name is a reserved word and shouldn't really be used for user record labels. Something like |name| would be "better AppleScript".

13th September 2010: I've uploaded an improved version of this sort, as part of a collection, to ScriptBuilders.

Last edited by Nigel Garvey (2010-11-13 08:15:34 am)


NG

Offline

 

#5 2010-07-20 03:07:42 am

McUsr
Member
From:: Southern Norway
Registered: 2010-04-07
Posts: 1776

Re: How to sort a list of records by a specific property

Applescript:


tell application "Quicksilver" to show large type "Thank You!"


Mercurial vcs is a joy to use for scripting.


Filed under: bubble sort

Offline

 

#6 2010-08-20 08:25:16 pm

cits
Member
Registered: 2008-06-05
Posts: 123

Re: How to sort a list of records by a specific property

mikerickson wrote:

This is a bubble sort method

Applescript:

set myList to {{age:23, name:"Bob"}, {age:14, name:"Susie"}, {age:37, name:"Jim"}}

repeat with i from 1 to (count of myList) - 1
   repeat with j from i + 1 to count of myList
       if age of item j of myList < age of item i of myList then
           set temp to item i of myList
           set item i of myList to item j of myList
           set item j of myList to temp
       end if
       log myList
   end repeat
end repeat

return myList


Hi Mikerickson, this is a short and sweet method which I am looking for. Thanks a lot!

However, I am stuck in creating the list with property: {{abc:value1, xyz:value2}, {abc:value3, xyz:value4}, ...}, instead, I got {"abc:value1, xyz:value2", "abc:value3, xyz:value4", ...} and not be able to sort as yours.

Please advise! TIA!

Last edited by cits (2010-08-20 08:26:22 pm)

Offline

 

#7 2010-08-21 01:04:13 am

mikerickson
Member
Registered: 2008-10-26
Posts: 437

Re: How to sort a list of records by a specific property

The property in the test needs to match the list

Applescript:

set myList to {{abc:"value44", xyz:"value2"}, {abc:"value3", xyz:"value4"}}

repeat with i from 1 to (count of myList) - 1
   repeat with j from i + 1 to count of myList
       if abc of item j of myList < abc of item i of myList then
           set temp to item i of myList
           set item i of myList to item j of myList
           set item j of myList to temp
       end if
       log myList
   end repeat
end repeat

return myList

Offline

 

#8 2010-08-21 01:10:09 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5118

Re: How to sort a list of records by a specific property

cits wrote:

However, I am stuck in creating the list with property: {{abc:value1, xyz:value2}, {abc:value3, xyz:value4}, ...}, instead, I got {"abc:value1, xyz:value2", "abc:value3, xyz:value4", ...} and not be able to sort as yours.

Please advise! TIA!


It's quite difficult to turn records into text by accident, so presumably you're starting with text anyway. Is that the case? And what do you want when you've finished? Text or records?

Last edited by Nigel Garvey (2010-08-21 01:10:35 am)


NG

Offline

 

#9 2017-01-24 08:51:07 pm

jean.o.matic
Member
From:: Montréal, Québec, Canada
Registered: 2009-10-05
Posts: 13

Re: How to sort a list of records by a specific property

A Quicksort handler with labeled property on which sort is done passed as a parameter (Thanks to Nigel Garvey for inspiration). Highly reusable code! Works more efficiently than BubbleSort, even more on long lists (less than 1/4 second for a list of 1000 records on a 2008 MacBook Pro, about 4.5 seconds for 10,000).Can also sort on descending order (reverse sort). Need Yosemite or later to compile the GetTick script.

Applescript:

on QuickSortLR(aList, Le, Ri, compObj) --> QuickSort for a list of records, based on original Tony Hoare quicksort 1959
   script Sal --> script object aList
       property Liszt : aList
   end script
   set {I, J} to {Le, Ri}
   set Piv to item ((Le + Ri) div 2) of Sal's Liszt --> pivot is choosen in the middle
   repeat while J > I
       repeat while compObj's isSmaller(item I of Sal's Liszt, Piv)
           set I to I + 1
       end repeat
       repeat while compObj's isLarger(item J of Sal's Liszt, Piv)
           set J to J - 1
       end repeat
       if not I > J then
           tell (a reference to Sal's Liszt) to set {item I, item J} to {item J, item I} --> let's swap (waltz for 2!)
           set {I, J} to {I + 1, J - 1}
       end if
   end repeat
   if Le < J then QuickSortLR(Sal's Liszt, Le, J, compObj)
   if Ri > I then QuickSortLR(Sal's Liszt, I, Ri, compObj)
end QuickSortLR

script byNickName --> one script needed for every labeled property on which sort is required
   on isLarger(x, y)
       (x's NickName > y's NickName)
   end isLarger
   on isSmaller(x, y)
       (x's NickName < y's NickName)
   end isSmaller
end script

script byAge --> one script needed for every labeled property on which sort is required
   on isLarger(x, y)
       x's Age > y's Age
   end isLarger
   on isSmaller(x, y)
       x's Age < y's Age
   end isSmaller
end script

set HowMany to 1000
set StartTick to GetTick's Now()
set MyList to MakeList(HowMany)
set MakeTime to (GetTick's Now()) - StartTick

set StartTick to GetTick's Now()
QuickSortLR(MyList, 1, HowMany, byNickName)
set QsTime to (GetTick's Now()) - StartTick

{MyList, MakeTime, QsTime} --> results

on MakeList(HowMany)
   set MyList to {}
   set UpCaseConsons to {"B", "C", "D", "F", "G", "H", "J", "K", "L", "M", "N", "P", "Q", "R", "S", "T", "V", "W", "X", "Y", "Z"}
   set LoCaseVoyels to {"a", "e", "i", "o", "u"}
   set LoCaseLetters to {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"}
   repeat with I from 1 to HowMany
       set the end of MyList to {NickName:item (random number from 1 to 21) of UpCaseConsons & ¬
           item (random number from 1 to 5) of LoCaseVoyels & ¬
           item (random number from 1 to 26) of LoCaseLetters, Age:random number from 1 to 100}
   end repeat
   return MyList
end MakeList

script GetTick --> for more precise timer calculations
   use framework "Foundation"
   on Now()
       return (current application's NSDate's timeIntervalSinceReferenceDate) as real
   end Now
end script

--> results

--> few records shown here (byByAge)
--> {{{NickName:"Yew", Age:1}, {NickName:"Nas", Age:1}, …{NickName:"Dap", Age:39}, {NickName:"Hut", Age:39},…{NickName:"Yik", Age:100}, {NickName:"Zan", Age:100}, {NickName:"Ruk", Age:100}, {NickName:"Ded", Age:100}}, 1.586159050465, 0.225466012955}

--> few records shown here (by NickName)
--> {{{NickName:"Bac", Age:22}, {NickName:"Bai", Age:54}, {NickName:"Bap", Age:79}, {NickName:"Baq", Age:37}, …{NickName:"Hur", Age:9}, {NickName:"Hur", Age:72}, {NickName:"Hus", Age:10}, {NickName:"Hut", Age:39}, {NickName:"Huw", Age:7}, {NickName:"Huy", Age:69},, …{NickName:"Zur", Age:66}, {NickName:"Zut", Age:1}, {NickName:"Zut", Age:66}}, 1.64743500948, 0.213027954102}

Doing a reverse can be done by an extra compObj in this manner:

Applescript:

script byNickNameReverse --> one script needed for every label on which sort is required
   on isLarger(x, y)
       (x's NickName < y's NickName)
   end isLarger
   on isSmaller(x, y)
       (x's NickName > y's NickName)
   end isSmaller
end script

or by simply reversing the list after sort, AppleScript is very efficient at doing this (0.069 second for 10,000 items):

Applescript:

set MyList to every item of reverse of MyList

Last edited by jean.o.matic (2017-01-25 07:03:21 am)


______________________
Jean.O.matiC
Montréal, Québec, Canada

Offline

 

#10 2017-01-25 04:31:52 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5118

Re: How to sort a list of records by a specific property

Hi.

Since isSmaller(x, y) is directly equivalent to isLarger(y, x), you don't need both handlers in the script objects. Every sort algorithm I've encountered can be written to rely solely on isLarger() comparisons (or isGreater() in my own versions), which greatly simplifies the writing of customising script objects, which in turn can be used with any kind of sort algorithm. I found the hardest thing to be deciding whether to standardise on isGreater() or isLess()!  wink  I finally went for isGreater().

Applescript:

-- …

repeat while compObj's isLarger(Piv, item I of Sal's Liszt) -- instead of compObj's isSmaller(item I of Sal's Liszt, Piv)
   set I to I + 1
end repeat
repeat while compObj's isLarger(item J of Sal's Liszt, Piv)
   set J to J - 1
end repeat

-- …

script byNickName --> one script needed for every label on which sort is required

   on isLarger(x, y)
       (x's NickName > y's NickName)
   end isLarger
end script

script byAge --> one script needed for every label on which sort is required

    on isLarger(x, y)
       x's Age > y's Age
   end isLarger
end script

There are of course a few ways to optimise the Quicksort itself, both in the AppleScript implementation and as an algorithm, but the resulting code is pretty long!

Edit: By the way, to sort on age, subsorting on nickname:

Applescript:

script byAgeThenByNickName
   on isLarger(x, y)
       set ageX to x's Age
       set ageY to y's Age
       (ageX > ageY) or ((ageX = ageY) and (x's NickName > y's NickName))
   end isLarger
end script

Last edited by Nigel Garvey (2017-01-25 05:23:06 am)


NG

Offline

 

#11 2017-01-25 04:52:16 am

Yvan Koenig
Member
Registered: 2006-09-14
Posts: 3673

Re: How to sort a list of records by a specific property

In my archives I retrieved two interesting sort codes.

Applescript:

(* Tri par interclassement
--> renvoie une copie triée de la liste originale.
Implémentation: L. Sebilleau & D. Varlet
*)


on intersort(laListe, fcmp)
   -- le deuxième paramètre est un pointeur sur la fonction de comparaison à employer
   
   script lstock -- l'intérêt de ce script est d'accélérer le traitement des listes
       property listeorg : laListe
       property liste1 : {}
       property liste2 : {}
       property listea : {}
       property listeb : {}
       property lister : {}
       property Compare : fcmp -- ce pointeur de fonction est stocké là
   end script
   
   -- répartition des éléments à trier en sous-listes de longueur deux
   
   tell lstock
       set ct to (its listeorg)'s length
       set flag to false
       if (ct mod 2) = 1 then
           set ct to ct - 1
           set flag to true
       end if
       repeat with i from 1 to ct by 2
           set x to item i of its listeorg
           set y to item (i + 1) of its listeorg
           if Compare(x, y) then -- la fonction de comparaison est employée ici
               {x, y}
           else
               {y, x}
           end if
           set the end of its liste1 to result
       end repeat
       if flag then set the end of its liste1 to {item -1 of its listeorg}
       
       -- interclassement des listes    contenues dans liste1
       repeat
           set ct to (its liste1)'s length
           if ct = 1 then exit repeat -- tant qu'il me reste plusieurs listes, c'est pas fini
           set flag to false
           if (ct mod 2) = 1 then
               set ct to ct - 1
               set flag to true
           end if
           set its liste2 to {}
           repeat with i from 1 to ct by 2 -- on prend les listes 2 par 2    
               set its listea to item i of its liste1
               set its listeb to item (i + 1) of its liste1
               set its lister to {} -- pour n'en faire qu'une seule dans celle-là
               set cta to (its listea)'s length
               set ctb to (its listeb)'s length
               set ya to 1
               set yb to 1
               repeat
                   
                   -- la fonction de comparaison est aussi employée ici:
                   if Compare(item yb of its listeb, item ya of its listea) then -- comparaison des premiers éléments
                       set the end of its lister to (item yb of its listeb) -- "extraction" du premier
                       set yb to yb + 1
                       if yb > ctb then -- si cette liste est maintenant vide, on arrête là.
                           if ya ≤ cta then -- il peut rester des éléments dans l'une des listes
                               set its lister to (its lister) & (items ya thru -1 of its listea)
                           end if
                           exit repeat
                       end if
                   else -- symétrique dans le cas inverse
                       set the end of its lister to (item ya of its listea)
                       set ya to ya + 1
                       if ya > cta then
                           if yb ≤ ctb then -- il peut rester des éléments dans l'une des listes
                               set its lister to (its lister) & (items yb thru -1 of its listeb)
                           end if
                           exit repeat
                       end if
                   end if
               end repeat
               -- la nouvelle liste produite par la fusion est ajoutée en tant que liste au résultat
               set the end of its liste2 to its lister
           end repeat -- et on recommence tant qu'il reste des paires de listes
           -- sans oublier l'orpheline si le nombre de listes est impair: on l'ajoute simplement à la fin
           if flag then set the end of its liste2 to {} & item -1 of its liste1
           set its liste1 to its liste2 -- et c'est reparti pour un tour
       end repeat
       return first item of its liste1 -- parce que c'est une liste de listes, même si elle n'en contient plus qu'une seule
   end tell
end intersort

----------- les fonctions de comparaison ------------
on cmpasc(n1, n2) -- pour le tri ascendant des nombres et des chaînes
   return n1 < n2
end cmpasc

on cmpdesc(n1, n2) -- tri descendant des nombres et des chaînes
   return n1 > n2
end cmpdesc

on recmp(n1, n2) -- tri par noms
   return (nom of n1 < nom of n2)
end recmp

on agecmp(n1, n2) -- tri par âges
   return (Age of n1 < Age of n2)
end agecmp

---------------- Pour tester ----------------

set maListe to {1, 5, 15, 2, 7, 3, 23, 125, 4, 89, 15, 8, 7, 6, 5, 27, 35, 12, 22, 160}


repeat 7 times -- 2 560 éléments
   set maListe to maListe & maListe
end repeat

set aTime0 to current date
set maListe to intersort(maListe, my cmpasc)
set aTime1 to current date
set laps to aTime1 - aTime0

log maListe
log "Durée: " & laps & " secondes"

return

set maListe to {¬
   {id:1, nom:"totor", Age:20, sexe:"M", list_IDconjoint:{}, IDPlanete:1}, ¬
   {id:2, nom:"Zézette", Age:100, sexe:"F", list_IDconjoint:{}, IDPlanete:1}, ¬
   {id:3, nom:"Lulu", Age:256, sexe:"M", list_IDconjoint:{}, IDPlanete:2}, ¬
   {id:4, nom:"Minouchet", Age:201, sexe:"F", list_IDconjoint:{}, IDPlanete:2}, ¬
   {id:5, nom:"Grmblwz", Age:12, sexe:"N", list_IDconjoint:{}, IDPlanete:2} ¬
       }

log intersort(maListe, my recmp)
log maListe
log intersort(maListe, my agecmp)

Applescript:

(* tri par tas (arbre binaire complet ordonné)
Ce tri figure parmi les plus efficaces et n'exige aucune mémoire supplémentaire.
Implémentation: L. Sebilleau
*)


on heapsort(laListe, fcmp)
   set n to the count of laListe
   if n ≤ 1 then return laListe
   
   script lstock -- l'intérêt de ce script est d'accélérer le traitement des listes
       property liste : laListe
       property Compare : fcmp -- pointeur de fonction de comparaison
   end script
   
   -- création du tas par insertion fictive des éléments présents dans la liste: ils sont
   --"phagocytés" un à un par la croissance du tas dont la dimension est i.
   
   repeat with i from 2 to n
       set j to i div 2 -- le premier parent du nouvel inséré
       set k to i
       set elem to item k of lstock's liste
       repeat while k > 1
           if lstock's Compare(item j of lstock's liste, elem) then
               set item k of lstock's liste to item j of lstock's liste
               set k to j
               set j to j div 2
           else
               exit repeat
           end if
       end repeat
       set item k of lstock's liste to elem -- installé dans sa position finale
   end repeat
   
   (* destruction du tas: l'extraction répétée donne la liste triée à l'envers:
comme le tas diminue par la fin de la liste, on peut réinsérer les éléments extraits à rebours
dans les emplacements libérés. Ce retournement explique pourquoi un utilise un tas max pour
trier en ordre croissant et vice-versa. *)

   
   repeat with i from n to 2 by -1
       set elem to item i of lstock's liste -- diminution du tas
       set item i of lstock's liste to item 1 of lstock's liste -- extraction de la racine qui est
       -- recopiée dans la position libérée
       
       -- réorganisation du tas en réinsérant l'élément de queue à la racine
       set j to 1
       set k to j * 2
       repeat while k < i
           if (k + 1) < i then
               if lstock's Compare(item k of lstock's liste, item (k + 1) of lstock's liste) then
                   set k to k + 1
               end if
           end if
           if lstock's Compare(elem, item k of lstock's liste) then
               set item j of lstock's liste to item k of lstock's liste
               set j to k
               set k to k * 2
           else
               exit repeat
           end if
       end repeat
       set item j of lstock's liste to elem
   end repeat
   --return lstock's liste -- c'est facultatif
end heapsort

----------- les fonctions de comparaison ------------
on cmpasc(n1, n2) -- pour le tri ascendant des nombres et des chaînes
   return n1 < n2
end cmpasc

on cmpdesc(n1, n2) -- tri descendant des nombres et des chaînes
   return n1 > n2
end cmpdesc

on recmp(n1, n2) -- tri par noms
   return (nom of n1 < nom of n2)
end recmp

on agecmp(n1, n2) -- tri par âges
   return (Age of n1 < Age of n2)
end agecmp

---------------- Pour tester ----------------

set maListe to {1, 5, 15, 2, 7, 3, 23, 125, 4, 89, 15, 8, 7, 6, 5, 27, 35, 12, 22, 160}


repeat 7 times -- 2 560 éléments
   set maListe to maListe & maListe
end repeat

set aTime0 to current date
heapsort(maListe, my cmpasc)
set aTime1 to current date
set laps to aTime1 - aTime0

log maListe
log "Durée: " & laps & " secondes"

return

set maListe to {¬
   {id:1, nom:"totor", Age:20, sexe:"M", list_IDconjoint:{}, IDPlanete:1}, ¬
   {id:2, nom:"Zézette", Age:100, sexe:"F", list_IDconjoint:{}, IDPlanete:1}, ¬
   {id:3, nom:"Lulu", Age:256, sexe:"M", list_IDconjoint:{}, IDPlanete:2}, ¬
   {id:4, nom:"Minouchet", Age:201, sexe:"F", list_IDconjoint:{}, IDPlanete:2}, ¬
   {id:5, nom:"Grmblwz", Age:12, sexe:"N", list_IDconjoint:{}, IDPlanete:2} ¬
       }

heapsort(maListe, my recmp)
log maListe
heapsort(maListe, my agecmp)
log maListe

Yvan KOENIG running Sierra 10.12.3 in French (VALLAURIS, France) mercredi 25 janvier 2017 11:52:09

Offline

 

#12 2017-01-25 05:51:57 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5118

Re: How to sort a list of records by a specific property

Yvan Koenig wrote:

Applescript:

set maListe to {¬
   {id:1, nom:"totor", Age:20, sexe:"M", list_IDconjoint:{}, IDPlanete:1}, ¬
   {id:2, nom:"Zézette", Age:100, sexe:"F", list_IDconjoint:{}, IDPlanete:1}, ¬
   {id:3, nom:"Lulu", Age:256, sexe:"M", list_IDconjoint:{}, IDPlanete:2}, ¬
   {id:4, nom:"Minouchet", Age:201, sexe:"F", list_IDconjoint:{}, IDPlanete:2}, ¬
   {id:5, nom:"Grmblwz", Age:12, sexe:"N", list_IDconjoint:{}, IDPlanete:2} ¬
       }


Wow! Does planet 2 have a very healthy climate or a very short year?  smile


NG

Offline

 

#13 2017-01-25 08:12:09 am

jean.o.matic
Member
From:: Montréal, Québec, Canada
Registered: 2009-10-05
Posts: 13

Re: How to sort a list of records by a specific property

Nigel Garvey wrote:

Hi.

Since isSmaller(x, y) is directly equivalent to isLarger(y, x), you don't need both handlers in the script objects. Every sort algorithm I've encountered can be written to rely solely on isLarger() comparisons (or isGreater() in my own versions), which greatly simplifies the writing of customising script objects, which in turn can be used with any kind of sort algorithm. I found the hardest thing to be deciding whether to standardise on isGreater() or isLess()!  wink  I finally went for isGreater().

Applescript:

-- …

repeat while compObj's isLarger(Piv, item I of Sal's Liszt) -- instead of compObj's isSmaller(item I of Sal's Liszt, Piv)
   set I to I + 1
end repeat
repeat while compObj's isLarger(item J of Sal's Liszt, Piv)
   set J to J - 1
end repeat

-- …

script byNickName --> one script needed for every label on which sort is required

   on isLarger(x, y)
       (x's NickName > y's NickName)
   end isLarger
end script

script byAge --> one script needed for every label on which sort is required

    on isLarger(x, y)
       x's Age > y's Age
   end isLarger
end script

There are of course a few ways to optimise the Quicksort itself, both in the AppleScript implementation and as an algorithm, but the resulting code is pretty long!


Hi!
Thanks for improving compactness of code. My script was a direct transcript of an older quicksort AppleScript for lists. Wanted to make it more readable, but dit not need to.
(From older script:)
   repeat while Piv > item i of Sal's Liszt   is in fact equivalent to  repeat while item i of Sal's Liszt < Piv
and thus only "IsLarger" is required.
Of course "Greater" feels even bigger than "Larger". I chose "isLarger" for legibility. Thanks for the subsort trick!

I read about improving Quicksort by choosing different pivot, number of pivots, etc. But this is already an overkill to sort 500 records. It is very efficient and quite small, I will keep it in my script library. Sorting 100,000 real numbers in 23 seconds is already amazingly fast for me. No surprise Quicksort has been a favorite alrounder for so long.


______________________
Jean.O.matiC
Montréal, Québec, Canada

Offline

 

#14 2017-01-25 05:04:15 pm

Shane Stanley
Member
From:: Australia
Registered: 2002-12-07
Posts: 6065

Re: How to sort a list of records by a specific property

jean.o.matic wrote:

Sorting 100,000 real numbers in 23 seconds is already amazingly fast for me.


If you're sorting large lists and speed matters, you'll do better with AppleScriptObjC where possible. For example:

Applescript:

use AppleScript version "2.4" -- Yosemite (10.10) or later
use framework "Foundation"
use scripting additions

-- build list of 100,000 reals
set theList to {}
repeat 10000 times
   set end of theList to random number from 0.0 to 100.0
end repeat
set newList to {}
repeat 10 times
   set newList to newList & theList
end repeat

-- sort them
set theStart to current application's NSDate's |date|()
set anArray to current application's NSArray's arrayWithArray:newList
set newList to (anArray's sortedArrayUsingSelector:"compare:") as list
set timeTaken to -(theStart's timeIntervalSinceNow())

That takes <0.4 seconds, and most of that time is spent converting to and from arrays/lists.


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#15 2017-01-26 04:44:23 am

Yvan Koenig
Member
Registered: 2006-09-14
Posts: 3673

Re: How to sort a list of records by a specific property

Hello Shane

Would be useful to explain how we may apply ASObjC to sort a list of records upon one of the properties included in the records.
After all it's the original question of this thread.

Yvan KOENIG running SIerra 10.12.3 in French (VALLAURIS, France) jeudi 26 janvier 2017 11:44:17

Offline

 

#16 2017-01-26 05:30:04 am

Shane Stanley
Member
From:: Australia
Registered: 2002-12-07
Posts: 6065

Re: How to sort a list of records by a specific property

Yvan Koenig wrote:

Would be useful to explain how we may apply ASObjC to sort a list of records upon one of the properties included in the records.
After all it's the original question of this thread.


ASObjC didn't exist when the original question was asked wink

It's pretty simple, but there are some provisos:

* The record labels can't be reserved words;

* The values must be strings, numbers, or booleans, or dates in 10.11 and above.

Then it's just a matter of making an array and thing called a sort descriptor, which describes what key/label you want to sort on, and how to sort them. So for the NickName/Age sample posted here yesterday, you would replace the call to QuickSortLR() with:

Applescript:

set anArray to current application's NSArray's arrayWithArray:MyList
set theDesc to current application's NSSortDescriptor's sortDescriptorWithKey:"NickName" ascending:true selector:"caseInsensitiveCompare:"
set newList to (anArray's sortedArrayUsingDescriptors:{theDesc}) as list

You can also sort by multiple keys. For example, if you were sorting by Age, you could have the entries where theAge matches be sorted by NickName:

Applescript:

set anArray to current application's NSArray's arrayWithArray:MyList
set theDesc to current application's NSSortDescriptor's sortDescriptorWithKey:"Age" ascending:true selector:"compare:"
set theDesc2 to current application's NSSortDescriptor's sortDescriptorWithKey:"NickName" ascending:true selector:"caseInsensitiveCompare:"
set newList to (anArray's sortedArrayUsingDescriptors:{theDesc, theDesc2}) as list

For all but very long lists, it's probably going to be a bit slower. The reason is because converting between records and dictionaries is time-consuming, which in turn is because AS records are very inefficient. The actual sorting is lightning fast.

My feeling is that, although records/dictionaries are a good way to work with data, large numbers of them tend to be so slow in AS that it's often better to stick to lists of lists in such cases, and so I'm not sure the need to sort large numbers of them happens much in the real world. But that's probably generalizing.


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#17 2017-01-26 07:01:07 am

Yvan Koenig
Member
Registered: 2006-09-14
Posts: 3673

Re: How to sort a list of records by a specific property

Thanks Shane.

I missed that the thread was a really old one.

Reading your message refreshed my memory.
It seems that I already read such pieces of code.
I will search in my archives some of these days.

Yvan KOENIG running Sierra 10.12.3 in French (VALLAURIS, France) jeudi 26 janvier 2017 14:01:02

Offline

 

#18 2017-01-26 08:41:02 am

DJ Bazzie Wazzie
Member
From:: the Netherlands
Registered: 2004-10-20
Posts: 2809
Website

Re: How to sort a list of records by a specific property

Shane Stanley wrote:

The reason is because converting between records and dictionaries is time-consuming, which in turn is because AS records are very inefficient. The actual sorting is lightning fast.


That's the reason why list sorting in the first versions of AST was done without using an list but building an array of descriptors to make use of quick sort which can be found in stdlib.h. The overhead of building an array and re-create an AEList was way smaller to keep the performance up.

Version 2.0 and up uses CoreFoundation where sorting is actually a bit slower for large lists than earlier versions of AST. But sorting 40k fields with an average string length of 50 characters still takes 0.2 seconds (2.3mb large CSV file) or sorting 100k real numbers costs the same in execution time.

Offline

 

#19 2017-01-26 05:02:20 pm

Shane Stanley
Member
From:: Australia
Registered: 2002-12-07
Posts: 6065

Re: How to sort a list of records by a specific property

DJ Bazzie Wazzie wrote:

That's the reason why list sorting in the first versions of AST was done without using an list but building an array of descriptors to make use of quick sort which can be found in stdlib.h. The overhead of building an array and re-create an AEList was way smaller to keep the performance up.


Yes, I tried various optimizations in ASObjC Runner early on, avoiding unpacking descriptors where possible. In the end, the complexity made it harder to maintain, and there didn't seem enough benefit.

With ASObjC, though, you often avoid a lot of the overhead. Sure, converting a list of records, sorting them, and converting back takes time. But in real situations it's often not like that -- you might convert once, then perform several operations before converting back. The transaction overhead often comes right down.


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#20 2019-11-06 07:56:28 pm

chrisndeca
Member
From:: Oakland, CA
Registered: 2005-06-28
Posts: 30

Re: How to sort a list of records by a specific property

Shane Stanley wrote:


* The values must be strings, numbers, or booleans, or dates in 10.11 and above.



So I am trying this with dates on 10.13 using SD and I get the following error:

[<__NSCFString 0x600000e9dbf0> valueForUndefinedKey:]: this class is not key value coding-compliant for the key aDate.

Here is a sample of my list (myList), which are selected messages in Mail:
{{"aDate:Wednesday, November 6, 2019 at 6:03:24 AM", "Subject:Take control of your life"}, {"aDate:Wednesday, November 6, 2019 at 5:18:49 AM", "Subject:Spam!!!!"}, {"aDate:Wednesday, November 6, 2019 at 9:58:21 AM", "Subject:NEW Savings Unwrapped for the Holidays!"}, {"aDate:Wednesday, November 6, 2019 at 7:23:20 AM", "Subject:Fall Savings Going On NOW"}, {"aDate:Wednesday, November 6, 2019 at 5:45:05 AM", "Subject:Check out these special offers"}, {"aDate:Tuesday, November 5, 2019 at 5:06:56 AM", "Subject:Thanks for your recent purchases!"}, {"aDate:Wednesday, November 6, 2019 at 3:30:12 PM", "Subject:Apple TV+ Review: ‘Dickinson’"}, {"aDate:Wednesday, November 6, 2019 at 9:00:28 AM", "Subject:RFML Digest, Vol 6, Issue 106"}}

And here is the code:

set anArray to (current application's NSArray's arrayWithArray:myList)
set theDesc to (current application's NSSortDescriptor's sortDescriptorWithKey:"aDate" ascending:true selector:"compare:")
set newList to (anArray's sortedArrayUsingDescriptors:{theDesc}) as list

Does anyone have any idea what is going wrong? I did a google search with the error text but that pointed me at a bunch of ObjectiveC errors and fixes.

Model: 2018 Macbook Pro
AppleScript: 2.6
Browser: Safari 605.1.15
Operating System: macOS 10.13

Last edited by chrisndeca (2019-11-06 08:00:43 pm)


Filed under: AppleScriptObjC

Offline

 

#21 2019-11-06 08:05:22 pm

Shane Stanley
Member
From:: Australia
Registered: 2002-12-07
Posts: 6065

Re: How to sort a list of records by a specific property

chrisndeca wrote:

Does anyone have any idea what is going wrong?



Your data is a list of lists, not records.


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#22 2019-11-06 08:26:51 pm

chrisndeca
Member
From:: Oakland, CA
Registered: 2005-06-28
Posts: 30

Re: How to sort a list of records by a specific property

Yep, records worked.

Thanks Shane!

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)