Sort multidimensional array

[Thierry]

The main speed problem was caused by passing a copy
of the complete data variable to a function that was being called over a million times.

Hi Simon,

I'm on the same board as you, and I often use this little @ gremlin,
but not always as, like everything, it has its pros and cons.

However, in this thread context,
stam function() will not be called million of times
and
the passing array will not be copied
as it is not edited/updated inside the calling function.
- See bob's link to a more verbose explanation...

Hope that clarify a bit

Regards,

[Thierry]

...there was an issue with using the "do" command....
...somehow related to Apple not liking programs that have potentially self-altering code in their App Store....

I must say, that seems unlikely.... I’d be surprised if Apple did a code-level review of apps (but really have no idea).
....

I do believe the same as Stam.

Regards,

[Simon Knight]

@Thierry,

My fault as I raised the speed bumps as an aside.

Simon

[Thierry]

Hi Stam,

Here is a variant which is slightly faster and using less memory,
but of course this has to be proved

Code: Select all

function sortArray @pArray, pDirection, pSortType, pKey
   local tNextIndex, tSortText, tSortedIndex 
   get the keys of pArray
   put "sort lines of IT [[pDirection]] [[pSortType]] by pArray[each]" into tSortText //1-dimensional array
   if pKey is not empty then put "[pKey]" after tSortText //multidimensional array
   do merge(tSortText)
   repeat for each line tKey in IT
      add 1 to tNextIndex
      -- put pArray[tKey] into tSortedArray[tNextIndex]
      put tKey into tSortedIndex[tNextIndex] -- !!!! NEW WAY !!!!!!
   end repeat
   return tSortedIndex
end sortArray

Code: Select all

on test_sorting_array
   local X = "ccc,eee,ddd,xxx,bbb,ppp,aaa"
   split X by comma
   put X[1] && X[2] &cr into fld 1 --> ccc eee
   
   put sortArray(  X, "ascending", "text") into I
   
   put X[ I[ 1]] && X[ I[ 2]] &cr after fld 1 --> aaa bbb

end test_sorting_array

Happy coding

[stam]

Here is a variant which I guess
is slightly faster and using less memory,
but of course this has to be proved

Thanks as always Thierry!
However that won't sort multidimensional arrays i don't think? you don't make use of [pKey] and the code looks fairly identical to the previous one you posted:)

With your help i had posted my 'final' code here, catering for both 1-dimensional and multidimensional arrays.

If i remove the error checking code for simplicity this was the final code based on your help:

Code: Select all

function sortArray @pArray, pDirection, pSortType, pKey
   local tNextIndex, tSortedArray, tSortText
   
   get the keys of pArray
   put "sort lines of IT [[pDirection]] [[pSortType]] by pArray[each]" into tSortText //1-dimensional array
   if pKey is not empty then put "[pKey]" after tSortText //multidimensional array
   do merge(tSortText)
   repeat for each line tKey in IT
      add 1 to tNextIndex
      put pArray[tKey] into tSortedArray[tNextIndex]
   end repeat
   return tSortedArray
end sortArray

I had included error-checking code to help with my debugging and in way of some documentation, but it isn't actually needed. I did check it with your testing example by setting pKey to empty to sort that 1-dimensional array; setting pDirection and pSortType empty will default to ascending & text respectively.

One handler to rule them all! I think that's better?

[Thierry]

Here is a variant which is slightly faster and using less memory,....

However that won't sort multidimensional arrays i don't think?
you don't make use of [pKey] and the code looks fairly identical to the previous one you posted:)

Ok, some misunderstanding....

I've edited my previous post, using your latest nice handler with some little changes!

Hope seeing the difference is more obvious by now?

Thierry

[stam]

Thanks Thierry - but that confuses me more (easily done mind you...)

Your handler returns a sorted index, not a sorted array, when i test this with a multidimensional array.
As an example, when running my handler to sort a multidimensional array by the key ["identifier"] in descending order, i get this:

Running your new handler to sort my multidimensional array, i get this back:

instead of a sorted multidimensional array.

I guess i could use this to build a new array or modify the existing one, but not sure how that's better?
Or maybe i'm doing something wrong?

Stam

[Thierry]

Thanks Thierry - but that confuses me more
(easily done mind you...)

Welcome to the club

Or maybe i'm doing something wrong?

Sure

From my previous post, how to use it:

Code: Select all

on test_sorting_array
   ...
   put sortArray(  X, "ascending", "text") into I
   
   put X[ I[ 1]] && X[ I[ 2]] &cr after fld 1 --> aaa bbb
   ...

I rewrite it again in a more verbose way:

Code: Select all

on test_sorting_array
   ...
   put sortArray(  X, "ascending", "text") into textAscendingIndex
   put sortArray(  X, "descending", "text") into textDescendingIndex
   
   put textAscendingIndex[ 1] into firstIndex
   put textAscendingIndex[ 2] into secondIndex
   
   put X[ firstIndex]  && X[ secondIndex]  --> aaa bbb
   ...

The idea is there is no copy of the original array, which can be hudge
and the data returned by the sortArray() function is smaller.
This will certainly optimize the speed and the footprint of the function,
and, as a bonus you can generate different index with the same data...

probably the name of the function should be changed then:

sortArray() --> buildSortedIndexFromArray()

So, better or worse

May be go for a lunch and a coffee before reading this

Kind regards,

[stam]

Thanks Thierry - i think i get it now -- it's not so much a array.sort method but rather a way to refer to the elements of the array with a different index.
I get how it this will be more lightweight especially when dealing with large arrays shifting binaries about etc.

Using it is just slightly more complex and maybe less helpful for my specific use case (the example i showed was from data that will populate the dgData of a data grid - for that i'd need to pass an array so don't think i could use this, but happy to stand corrected ).

A complimentary approach and a useful tool rather than a replacement?
i'll do some speed tests on a large array when i'm back from my actual day job, curious to see what the performance difference will be...

Thanks for taking time to explain this!
Stam

[jacque]

Also, I seem to recall that there was an issue with using the "do" command.
If I remember correctly, it has somehow related to Apple not liking programs that have potentially self-altering code in their App Store.
Anyone familiar with that issue?
Sorry, it is only a vague recollection.

Apple forbids self-modifying code, but I don't think they review the app that deeply. But if you get caught you'll lose your developer account. On the other hand, "do" isn't self-modifying in this case.

The main objection to "do" (and "value") is that they need to load the compiler which introduces overhead. In the case of the merge command you should get the same result using "get" instead, which has no extra overhead.

Code: Select all

get merge(tSortText)

In this case "do" is only used once so the overhead will be minimal but I try to avoid it whenever possible anyway.

[stam]

The main objection to "do" (and "value") is that they need to load the compiler which introduces overhead. In the case of the merge command you should get the same result using "get" instead, which has no extra overhead.

Code: Select all

get merge(tSortText)

In this case "do" is only used once so the overhead will be minimal but I try to avoid it whenever possible anyway.

On testing get merge() fails; do merge() works.
i tried changing this to get merge(tSortText) and it failed: Instead of evaluating the statement, 'it' just contains the text that was in tSortText and the handler returns a single integer. Changing it back to do merge(tSortText) returned the sorted indices of the array and returns the sorted array (that was the only word changed in my handler sortArray above).

Is this expected behaviour?

[jacque]

Sorry, was working from memory and goofed. Try

Code: Select all

put merge(tSortText) into it

And since I'm still working from memory, if that doesn't work use "do".

Edit: I think I see now why this won't work. Merge requires a string, and tSortText isn't one. Using "do" forces evaluation. You could use "get" by creating a quoted string that includes the bracketed variables instead.

[bogs]

You could use "get" by creating a quoted string that includes the bracketed variables instead.

So, this sounds like another one of those selectedLine things, eh? Tell me, would 'the value of' or 'the text of' work in front of the merge for this, like it does with selectedLine?

I'm beginning to think that Craig is right, "DO" is the answer to everything

[Thierry]

Sorry, was working from memory and goofed...
I think I see now why this won't work. Merge requires a string, and tSortText isn't one.

Mmm, sorry but
- tSortText IS a string
- the result of merge() IS a string too.
- the sort command IS NOT expecting a string as a parameter

Checking sort in the dictionary we can see that direction and sortType are enum type,
which is why the merge() alone won't help.

The DO command will compile and execute the returned string of merge().

That said , the merge() isn't mandatory; you can use format() or
the classic: put x && y ... into tSortText

So either code a list of if .. else ...
OR use the do merge() trick for a one line coding,
and accept the pros and cons of each solution.

About the DO and its speed:
if you do this:

repeat with i=1 to 10000000
DO "...."
end repeat
put "Are you still there?"

not too good, but:

on mouseUp
DO "...."
end mouseUp

you''ll hardly notice a speed problem...

Have a nice day,

Thierry

[Thierry]

I'm beginning to think that Craig is right, "DO" is the answer to everything

DO NOTHING is the answer to everything