Sorting Sparse Arrays (Again)

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Sorting Sparse Arrays (Again)

Martin Marris
I'm finding the instructions for using SortSparseArrays a little terse.

I have an "array of arrays" whose first field in each element contains a
single, long index number. I want to sort on that index number.

The instructions say:

// strMethodCompare is the name of a routine that takes 2 strings, strA and
strB, and returns 1
// or 0 based on the comparison. See StringLess or NumberLess for models.
// strPluginName is the file name (no extension) of the plugin that contains
strMethodCompare

Does that mean I have to write a separate plugin called strPluginName, that
will contain the parameters of the custom search? How is that plugin code
structured?

Sorry, I know I'm a bit slow on the uptake....

Thanks.

Martin


_______________________________________________
Plugin-dev mailing list
[hidden email]
http://avid-listsrv1.avid.com/mailman/listinfo/plugin-dev
Reply | Threaded
Open this post in threaded view
|

FW: Sorting Sparse Arrays (Again)

Bob Zawalich

Thought this might be useful for the list

 

From: Bob Zawalich [mailto:[hidden email]]
Sent: Tuesday, October 13, 2015 3:55 PM
To: 'Martin Marris'
Subject: RE: [Plugin-dev] Sorting Sparse Arrays (Again)

 

Hi Martin,

 

First of all, if I had to sort arrays I would use dictionaries in the first place, and in fact I do that all the time.

 

If I were starting from scratch, I would put the objects I was putting into a sparse array into a dictionary, after building a string key that would be suitable for sorting. SO if the contents of the array were strings, I would use the string as the dictionary key, and almost anything else for the value. Then I could say “for each Name name in dict” and get out the strings in sorted order. I might put them into an array at that point if I wanted it in a dialog.

 

If the sparse array contained objects, I would still create a string suitable for sorting in the dictionary, and store the object itself as the dictionary value. I suspect I would live totally fine if there were only dictionaries and no sparse arrays. In fact, in Lua, arrays are implemented as dictionaries optimized to use numeric keys.

 

My only annoyance with dictionaries is that you don’t know how many entries are in the dictionary. You can return the count when you fill it, or you can add the count as a user property (but then that will show up and a Name:Value pair when you enumerate the Names), or you could probably just walk the dictionary and count the entries. It goes fast enough to not be noticeable.

 

The value of sorting with the dictionary is speed – it is all done in QT not in ManuScript.

 

Even if I already had a sparse array, I would consider loading the contents into a dictionary and the reading out from the dictionary into the same or another sparse array.

 

If you really want to use utils.SortSparseArray, you do not need a separate plugin, just a separate method to do comparisons. It really works the same way that SortArray works at the level of its calls to QuickSort.

 

SortArray does a string comparison, calling

 

    QuickSort(array, 0, array.NumChildren, fShowProgress, '', 'StringLess');

 

SortArrayNumeric calls

 

    QuickSort( array, 0, array.NumChildren, fShowProgress, '', 'NumberLess' );

 

Where Stringless and Numberless are callback routines, present in utils.plg (though this is not required), which do string or numeric comparisons.

 

SortSparseArrayCustom just puts the callback name in its parameter list so there does not need to be multiple versions of the method. This is particularly important when you consider that a sparse array can contain objects, so there may be a lot more comparison routines needed to compare non-string or numeric variables. So there is just the one method. If you want to sort strings or numbers, you can  pass in utils.StringLess, or utils.Numberless as strMethodCompare.

 

For more complex comparisons, use a local method. For example, in the plugin Open Selected Parts, there is a call

 

                        utils.SortSparseArrayCustom(arsPartsForInst, False, 'OpenSelectedParts', 'PartMore');

 

and PartMore is a variant of StringLess.

 

            PartMore "(partB, partA) {

// Written by Hans-Christoph Wirth;

 

// Modified by Bobz

// Reverse order of parameters to sort in descenting order and use StringLess Code

 

score = Sibelius.ActiveScore;

partOrig = score.CurrentDynamicPart;

 

score.CurrentDynamicPart = partA;

strA = score.PartName;

score.CurrentDynamicPart = partB;

strB = score.PartName;

 

score.CurrentDynamicPart = partOrig; // restore

 

lengthA = Length(strA);

lengthB = Length(strB);

if (lengthA > lengthB)

{

            length = lengthB;

}

else

{

            length = lengthA;

}

 

pos = 0;

while (pos < length)

{

            a = Asc(Substring(strA, pos, 1));

            if ((a > 64) and (a <= 90))

            {

                        a = a + 32;

            }

            b = Asc(Substring(strB, pos, 1));

            if ((b > 64) and (b <= 90))

            {

                        b = b + 32;

            }

            if (a < b)

            {

                        return 1;

            }

            if (a > b)

            {

                        return 0;

            }

            pos = pos + 1;

}

 

if (lengthA < lengthB)

{

            return 1;

}

return 0;}"

 

 

I added SortSparseArrayCustom to utils.plg before I really understood the joys of dictionary sorting. So I haven’t used it for a long time, but I would expect it to work.

 

Hope that helps. Holler if not.

 

Bob

 

 

******************************

 

I'm finding the instructions for using SortSparseArrays a little terse.

I have an "array of arrays" whose first field in each element contains a
single, long index number. I want to sort on that index number.

The instructions say:

// strMethodCompare is the name of a routine that takes 2 strings, strA and
strB, and returns 1
// or 0 based on the comparison. See StringLess or NumberLess for models.
// strPluginName is the file name (no extension) of the plugin that contains
strMethodCompare

Does that mean I have to write a separate plugin called strPluginName, that
will contain the parameters of the custom search? How is that plugin code
structured?

Sorry, I know I'm a bit slow on the uptake....

Thanks.

Martin


_______________________________________________
Plugin-dev mailing list
[hidden email]
http://avid-listsrv1.avid.com/mailman/listinfo/plugin-dev


_______________________________________________
Plugin-dev mailing list
[hidden email]
http://avid-listsrv1.avid.com/mailman/listinfo/plugin-dev
Reply | Threaded
Open this post in threaded view
|

Re: FW: Sorting Sparse Arrays (Again)

Martin Marris

Hi Bob,

 

About 24 hours ago I optimistically started learning about Dictionaries but after many hours, just ended up totally bewildered. It's a level of abstraction that I find hard to understand. And I have read your good posts carefully….

 

For background: I don’t even know what a “hash table” or a C “struct” are, and I believe that’s what a “Dictionary” is, so it’s basically a question of unfamiliarity.

 

So let's say we create a dictionary, as in the manual:

 

The values in a dictionary can be accessed using square bracket notation, so you can use a dictionary like a hash table, e.g.:

test = CreateDictionary("fruit",apple,"vegetable",potato);

test["fruit"] = banana;

test["meat"] = lamb;

 

So far, so good. They are key/value pairs. But in all my attempts to use this, it is a single-data structure. There is one “fruit” in it (whose value is apple). I can change that value, but that hardly gets me beyond assigning values to a single string. I tried the various data-access syntaxes listed in those two pages in the manual but got nowhere: I always just seem to get one set of values.

 

I know that I can place an array inside a Dictionary, and have successfully done so. But again, when I tried to iterate with a “for each,” only one array was returned. (Strangely, it wasn’t even the first one, but the 24th out of something like one thousand.)

 

dictMyDictionary = CreateDictionary("arrData", CreateSparseArray());

 

a loop here, including                    

 

dictMyDictionary["arrData"] = arrTemp

 

where arrTemp is a temporary array that’s rebuilt in each loop;

 

and finally:

 

for each arrData in dictMyDictionary

     {

     for counter = 0 to arrData.NumChildren

           {

           trace(arrData[counter]);

           }

     }

 

What is the elementary mistake that I am making? I know that the above is just completely wrong, so how is it supposed to work?

 

Many thanks for your help so far!

 

Martin

 


_______________________________________________
Plugin-dev mailing list
[hidden email]
http://avid-listsrv1.avid.com/mailman/listinfo/plugin-dev
Reply | Threaded
Open this post in threaded view
|

Re: FW: Sorting Sparse Arrays (Again)

Alexander Plötz
Hello Martin,
 
sorry, I do not have any advice for your current question, but – mainly out of curiosity – I would like to ask: hexadecimals, multidimensional sorting, thousands of data sets... what the heck are you working on? : )
 
Well, since I am writing, and Bob has not been around again: I have not worked with dictionaries myself, but (disclaimer, I might be dead wrong here) as far as I have come to understand them, you can think of them like a crossbreed between an old style Array (which will not allow you to store objects, but comes with the ability to assign a label to each entry) and a Sparse Array (which will store anything, but the only way to get to certain entries is by enumeration). So, instead of putting your array into the dictionary, you should use the dictionary instead of the array. Remembering what Bob wrote about sorting a dictionary, the advantage is that the labels are stored in alphanumerical order in the dictionary by default, which could be utilised for quick sorting.
 
Alex

_______________________________________________
Plugin-dev mailing list
[hidden email]
http://avid-listsrv1.avid.com/mailman/listinfo/plugin-dev
Reply | Threaded
Open this post in threaded view
|

Re: FW: Sorting Sparse Arrays (Again)

Martin Marris
>>sorry, I do not have any advice for your current question, but – mainly out of curiosity – I would like to ask: hexadecimals, multidimensional sorting, thousands of data sets... what the heck are you working on? : )<<

Hi Alex,

We work on large volumes of files, some of which are themselves individually very large. We are music engravers and it's a tough business unless you can turn over almost all of the repetitive tasks to the computer! We've been in the business for 25 years but we still haven't run out of tasks to automate....

Martin



_______________________________________________
Plugin-dev mailing list
[hidden email]
http://avid-listsrv1.avid.com/mailman/listinfo/plugin-dev
Reply | Threaded
Open this post in threaded view
|

Re: FW: Sorting Sparse Arrays (Again)

Bob Zawalich
In reply to this post by Martin Marris

OK so let’s see what Martin was doing and try to get it to work. He did this:

 

dictMyDictionary = CreateDictionary("arrData", CreateSparseArray());

 

which should be equivalent to what I would usually do:

 

ars =CreateSparseArray();

dict = CreateDictionary();

dict[“arrData”] = ars;

 

Which is wordier and slower but seems clearer to me, and I rarely want to initialize a dictionary at creation. So you have a dict consisting of a single name:value pair  “arrData”:ars, where ars is an empty sparse array. He does this:

 

dictMyDictionary["arrData"] = arrTemp

 

where arrTemp is a temporary array that’s rebuilt in each loop;

 

and I will assume that arrTemp is not a sparse array but a normal Sib array created by CreateArray. (I would name a sparse array arsTemp, rather than arrTemp so I can tell the structure from the variable name, but it may or may not be significant). (EDIT: it does not really matter for the code that follows what type of array arrTemp is);

 

At any rate, he has wiped out the original data pair of arrData:ars that he initialized the dictionary with by doing this assignment, so at this point there is still just a single array in the dict. Let’s assume that entries have been put into arrTemp. So we have this loop:

 

 

for each arrData in dictMyDictionary

     {

     for counter = 0 to arrData.NumChildren

           {

           trace(arrData[counter]);

           }

     }

 

for each arrData in dictMyDictionary, by definition means we get the element values in the dictionary, ignoring the names/key field.

 

* To iterate over element values in Dictionary objects, use for each n in Dictionary or for each Value n in

Dictionary

 

The order we get them is not defined, but one might guess they will come out in key order, as if we had done

 

for each Name name in dictMyDictionary

{

            arr = dictMyDictionary[name];

}

 

So we should have an array, and we should be able to enumerate the elements of the array.  Just to be explicit, I will write what I think is equivalent code so I can run it:

 

arrTemp = CreateArray();

for i = 0 to 5

{

arrTemp[i] = i;

}

 

dictMyDictionary = CreateDictionary();

dictMyDictionary["arrData"] = arrTemp;

 

 

for each arrData in dictMyDictionary

{

trace(arrData.WriteToString());

for counter = 0 to arrData.NumChildren

{

trace(arrData[counter]);

}

}

 

And the output is, as I would expect

 

{

"0"

"1"

"2"

"3"

"4"

}

 

0

1

2

3

4

 

Which is what it would be if the arrData were a sparse array as well. So this works as I would expect. So what is Martin expecting?

I am guessing that he wants multiple arrays in the dictionary but is not updating the key.  He could create 5 arrays, and add them as

 

dictMyDictionary["arrData1"] = arrTemp1;

dictMyDictionary["arrData2"] = arrTemp2;

dictMyDictionary["arrData3"] = arrTemp3;

dictMyDictionary["arrData4"] = arrTemp4;

dictMyDictionary["arrData5"] = arrTemp5;

 

and then will have 5 arrays in the dict. If you keep doing something like

 

dictMyDictionary["arrData1"] = arrTemp1;

dictMyDictionary["arrData1"] = arrTemp2;

dictMyDictionary["arrData1"] = arrTemp3;

 

you will just replace the entry at key “arrData1”, just like assigning multiple arrays to

 

arsMySparseArray[0] = arrTemp1;

arsMySparseArray[0] = arrTemp2;

 

will only give you the last one assigned. A key string in a dictionary is in this sense equivalent to an array index in an array. arrTemp3 will be the only array in the dictionary.

 

So I think the code is fine if you are filling the dictionary properly.

 

As far as the loop goes, if I had

 

dictMyDictionary["arrData1"] = arrTemp1;

dictMyDictionary["arrData2"] = arrTemp2;

dictMyDictionary["arrData3"] = arrTemp3;

dictMyDictionary["arrData4"] = arrTemp4;

dictMyDictionary["arrData5"] = arrTemp5;

 

 

and wanted to access the arrays in key order, I would probably say

 

for each Name name in dictMyDictionary

{

            arr = dictMyDictionary[name];

}

 

because I trust that ordering. You can experiment if you want with just getting the values as your loop shows, but I have had experience with the Name name stuff and I am confident that I will get the entries in key order.

 

You should use the name/key field to identify the array you have in the value field.

 

Martin, you can send me actual code offline if you like and I can have a look at it if it is not behaving as expected.

 

Cheers

 

bob

From: Martin Marris [mailto:[hidden email]]
Sent: Wednesday, October 14, 2015 1:15 PM
To: [hidden email]; 'A mailing list for Sibelius plug-in developers'
Subject: RE: [Plugin-dev] FW: Sorting Sparse Arrays (Again)

 

Hi Bob,

 

About 24 hours ago I optimistically started learning about Dictionaries but after many hours, just ended up totally bewildered. It's a level of abstraction that I find hard to understand. And I have read your good posts carefully….

 

For background: I don’t even know what a “hash table” or a C “struct” are, and I believe that’s what a “Dictionary” is, so it’s basically a question of unfamiliarity.

 

So let's say we create a dictionary, as in the manual:

 

The values in a dictionary can be accessed using square bracket notation, so you can use a dictionary like a hash table, e.g.:

test = CreateDictionary("fruit",apple,"vegetable",potato);

test["fruit"] = banana;

test["meat"] = lamb;

 

So far, so good. They are key/value pairs. But in all my attempts to use this, it is a single-data structure. There is one “fruit” in it (whose value is apple). I can change that value, but that hardly gets me beyond assigning values to a single string. I tried the various data-access syntaxes listed in those two pages in the manual but got nowhere: I always just seem to get one set of values.

 

I know that I can place an array inside a Dictionary, and have successfully done so. But again, when I tried to iterate with a “for each,” only one array was returned. (Strangely, it wasn’t even the first one, but the 24th out of something like one thousand.)

 

dictMyDictionary = CreateDictionary("arrData", CreateSparseArray());

 

a loop here, including                    

 

dictMyDictionary["arrData"] = arrTemp

 

where arrTemp is a temporary array that’s rebuilt in each loop;

 

and finally:

 

for each arrData in dictMyDictionary

     {

     for counter = 0 to arrData.NumChildren

           {

           trace(arrData[counter]);

           }

     }

 

What is the elementary mistake that I am making? I know that the above is just completely wrong, so how is it supposed to work?

 

Many thanks for your help so far!

 

Martin

 


_______________________________________________
Plugin-dev mailing list
[hidden email]
http://avid-listsrv1.avid.com/mailman/listinfo/plugin-dev