Sorting collections at runtime

[ConvertFromOldNGs]

by Craig Shearer >> Mon, 8 Feb 1999 23:09:11 GMT

Hello All

I've been doing some experiments on sorting an array at runtime. The basic requirement is to have an array of objects and sort the objects in the array according to one or more of their properties, kind of like specifiying the keys for a member key dictionary at runtime. This sort of thing is very useful where users want to specify the order of records in their reports etc.

Anyway, since JADE lacks such a feature I thought I'd have a go at implementing this using the extractSort method on the File class.

I added a method to the ObjectArray class to sort its contents. The method takes a collection of SortKey objects (of my own devising) which basically store the name of the property on the class, the length, whether or not the key is numeric and whether or not the key should be sorted ascending or descending.

The idea is that each object in the array gets its key values written to the file, along with its Oid so that it can be identified on the way back in. The file is sorted, then the collection cleared, then the collection is re-populated from the sorted file.

Thus, all the objects in the collection will magically appear sorted.

The reason for this post is that the performance (as you can imagine) isn't very good. Here's the details:

Sort of a collection with 1 key containing 2000 objects takes about 8 seconds - pretty bad. However, when the actual parts of the sorting are broken down, the file sort actually only takes about 1/2 a second (much more respectable). It's the writing and reading the file that takes the time.

So, what I would propose is that JADE have a feature that allows this sorting to happen WITHOUT having to write objects out to a file.


Here's the code, in case you want to try it yourself. There are various things you'd need to do to make it work in your environment (like creating the SortKey and SortKeyArray classes, and implementing a getTempFileName method on app).



sort(sortKeys: SortKeyArray) lockReceiver, updating;

vars
sortSrc,
sortDest : File;

srcFileName,
destFileName : String;

actor : SortActor;
actors : SortActorArray;

sortKey : SortKey;

pos,
fieldNum,
keyStart,
oidPosition : Integer;

obj : Object;

oid,
line : String;

propValue : Any;
propString : String;

i : Integer;
begin

create sortSrc transient;

srcFileName := app.getTempFileName("srt",0);
sortSrc.fileName := srcFileName;
sortSrc.recordSize := 0;
sortSrc.endOfLine := CrLf;

create sortDest transient;
destFileName := app.getTempFileName("srt",0);
sortDest.fileName := destFileName;
sortDest.allowReplace := true;
sortDest.allowCreate := true;

create actors transient;
actors.kway := 3;

// create the SortActor objects
keyStart := 1;
fieldNum := 1;
foreach sortKey in sortKeys do
create actor;

actor.numeric := sortKey.fNumeric;
actor.length := sortKey.fLength;
actor.startPosition := keyStart;
actor.fieldNo := fieldNum;
actor.ascending := not sortKey.fDescending;
actor.random := false;

actors.add(actor);

fieldNum := fieldNum + 1;
keyStart := keyStart + actor.length;
endforeach;

oidPosition := keyStart;

i := app.clock;

// now, write the objects to the source file
foreach obj in self do
line := "";
foreach sortKey in sortKeys do
propValue := obj.getPropertyValue(sortKey.fPropertyName);
propString := propValue.String[1:sortKey.fLength].padBlanks(sortKey.fLength);
line := line & propString;
endforeach;

oid := obj.getOidString;
line := line & oid;

sortSrc.writeLine(line);
endforeach;

sortSrc.close;

write "Write to file takes " & (app.clock - i).String;

// perform the sort
i := app.clock;
sortSrc.extractSort(actors, sortDest);
write "Actual sort takes " & (app.clock - i).String;

// clear the collection
clear;

i := app.clock;

// reload the collection from the sorted file
sortDest.mode := File.Mode_Input;
sortDest.open;
while not sortDest.endOfFile do
line := sortDest.readLine;

oid := line[oidPosition:end];
obj := oid.asOid;
add(obj);
endwhile;

write "Read from file takes: " & (app.clock - i).String;

epilog
sortSrc.purge;
sortDest.purge;

delete sortSrc;
delete sortDest;

actors.purge;
delete actors;

end;

[ConvertFromOldNGs]

by Brian Johnstone >> Mon, 8 Feb 1999 23:58:17 GMT

Craig,

The purpose of these news group forums is to allow developers to discuss aspects of JADE Development with other developers. Should the result of discussions be a general agreement that it would make a good new feature in JADE, then please raise an NFS in the Contact system.

ie: The Contact system is still the official means by which to request a New Feature in JADE.

As JADE increases in popularity, a good New Feature Suggestion could quickly become lost in the maze of discussions on the boards and JADE Support will not necessarily read all postings made to the newsgroups.

Thanks,
Brian Johnstone,
JADE Support.

[ConvertFromOldNGs]

by Craig Shearer >> Tue, 9 Feb 1999 0:44:46 GMT

Thanks Brian

While I take your point about New Feature Suggestions, it is always good to find out what other JADE users might think of the idea first, particularly with a feature as important as this one. Also, it might help you and the plant to guage the amount of interest in the feature and so prioritise it accordingly

Craig.

[ConvertFromOldNGs]

by Leigh Roberts >> Wed, 10 Feb 1999 2:31:42 GMT

Brian

I agree with Craig's reply to you. Also...

As JADE increases in popularity, a good New Feature Suggestion could quickly become lost in the maze of discussions on the boards and JADE Support will not necessarily read all postings made to the newsgroups.

But a useful way to view and vote on existing New Feature Suggestions would be much greater value than the present black hole.

Leigh

[ConvertFromOldNGs]

by John Porter >> Fri, 26 Feb 1999 2:00:01 GMT

If i/o is the bottleneck, you could write the file to a memory file (ie, using RamDrive.sys or equivalent).

Have you tried using a sorted (invisible) table? I use sorted listboxes in Visual Basic for that, and they are quite effective.

Cheers,
John P

[ConvertFromOldNGs]

by Craig Shearer >> Mon, 1 Mar 1999 19:10:37 GMT

<snip>

If i/o is the bottleneck, you could write the file to a memory file (ie, using RamDrive.sys or equivalent).

Have you tried using a sorted (invisible) table? I use sorted listboxes in Visual Basic for that, and they are quite effective.

Cheers,
John P

Using an invisible table or listbox and sorting that is an option, but I was looking for something a little more scaleable.

Whilst I haven't tried the ramdrive.sys option you describe, I'm pretty sure that most of the time goes in JADE's concatenation of strings.

It would seem to me that all of this runtime sorting could be solved if JADE allowed the creation of new classes at runtime. Then you'd just create a new subclass of MemberKeyDictionary, with the appropriate keys, copy your collection to a transient instance of the new class, and voila, you have a sorted collection. Anybody from the plant care to comment on how difficult this would be to achieve? (Of course, there's already a JADE application called JADE that has the ability to create classes. I guess there would be some difficult issues to consider, especially with read only schema systems.)

Comments?

Craig.

[ConvertFromOldNGs]

by Dean Cooper >> Mon, 1 Mar 1999 22:31:04 GMT

It would seem to me that all of this runtime sorting could be solved if JADE allowed the creation of new classes at runtime. Then you'd just create a new subclass of MemberKeyDictionary, with the appropriate keys, copy your collection to a transient instance of the new class, and voila, you have a sorted collection. Anybody from the plant care to comment on how difficult this would be to achieve? (Of course, there's already a JADE application called JADE that has the ability to create classes. I guess there would be some difficult issues to consider, especially with read only schema systems.)

Allowing user applications to (safely!) add and remove persistent classes at runtime would not be trivial, and there are currently no plans to do this. Apart from maintaining the schema definition itself, there are wider issues of updating schema files at runtime (raises security/integrity/maintenance issues; also defeats read-only schema), and synchronisation of many of the kernel's internal structures (possibly on multiple nodes; if not all of them). Slightly less complicated would be the creation/deletion of transient classes at runtime; where the definition of the class is transient (it is not added to the persistent schema), is visible only on the node of the process that created it, and for which only transient instances can be created. While there are currently no plans to implement this either, I think it would be preferable to adding/removing persistent classes.

The addition/removal of classes at runtime strikes me as a heavyweight solution to the requirement this newsgroup thread seems to be discussing; which is the ability to dynamically specify the membership and keys of a dictionary at runtime. Say there was a new type of dictionary class (possibly for which you could only create transients) that provided methods allowing you to specify the member class and key properties. You could then create a transient dictionary, define the membership and keys, and populate it with the objects you require sorted. Memory management and overflow would be handled by the kernel's caching mechanisms. I think that this feature would be more desirable than the ability to add and remove classes at runtime.

Dean.

[ConvertFromOldNGs]

by Craig Shearer >> Tue, 2 Mar 1999 2:50:58 GMT

<snip>

Say there was a new type of dictionary class (possibly for which you could only create transients) that provided methods allowing you to specify the member class and key properties. You could then create a transient dictionary, define the membership and keys, and populate it with the objects you require sorted. Memory management and overflow would be handled by the kernel's caching mechanisms. I think that this feature would be more desirable than the ability to add and remove classes at runtime.

Dean.

Sounds perfect to me Dean. When can we expect it in the product?

Craig.

[ConvertFromOldNGs]

by Eric Peachey >> Thu, 4 Mar 1999 19:13:33 GMT

Is this necessary. Couldn't you just use a sub-class of ExtKeyDictionary (even the ObjectLongNameDict class), create a string containing the key properties (padded out as necessary so the sorting works) for each object and then just add them to the dictionary using your home-made key?

Eric Peachey
Cardinal Eng. Centre Dunedin

[ConvertFromOldNGs]

by Craig Shearer >> Thu, 4 Mar 1999 23:55:08 GMT

Hi Eric

Yes, you *could* do this, and, in fact, I used just this solution in a JADE system I helped write about 3 years ago. While it could be made to work in some situations, if you want a reasonably generic solution it's an ugly solution for the following reasons:

- You don't know how long to make the key. If you want it user configurable, you need to make the key long so you can fit all the parts of the key into it, ie. 90 characters could handle 3 x 30 character string keys, but what if the user wants 4 keys?

- Because the keys have to be long to cope with all situations, the sort is less efficient.

- It can't cope with having some parts of the key sorted descending and others ascending.

- You run into problems sorting by key fields that aren't strings - you have to pad an integer with leading zeros to make it sort properly.

- Creating the keys requires lots of time-consuming string concatenation code.

The solution we came up with, for efficiency reasons, was to use several subclasses of ExtKeyDictionary - each class containing a different number of keys ie. 1 key, 2 keys, 3 keys, 4 keys, 5 keys etc. Each key was limited to 30 characters.

The solution, as you can imagine, was incredibly complex. What I'm aiming for is a solution which is simple to use, and as I'm sure you'd agree, is provided by the majority of other development environments.

Craig.