vList Xtra VLIST XTRA HELP: HOW DIRECTOR HANDLES LIST SORTING  
  All lists have an internal flag set to true or false that indicates to Director whether the list is currently in a sorted state or not. When Director searchs in a list (getProp, findPos, findPosNear), it first checks to see whether the sorted flag is true. If the list is sorted, then Director searches beginning at the middle of the list. If the value there is greater than the one to look for, then Director goes back and starts looking at the value located in the middle of the first middle part of the list, etc. until the target value is found and the position returned. In other words Director uses a standard binary search to find an item in a sorted list, which is usually more efficient than searching straight from beginning to end. If the list has its sorted flag set to false, Director's search begins with the first element, then the second, etc. until the value is found. This method is usually much slower, unless by chance, the target item is at the beginning of the list.

 

When you do:

 

sort (list)

 

Director does two things: the list is ordered (alphabetically) on its elements and the list's sorted flag is set to true.

 

When you store a sorted list as text with a string() conversion and then retrieve it back in memory with value(), the list is still in order, but the sorted flag is set to false. So searching inside the list is slow again, as slow as searching on an unordered list. If you want to have fast searchs, you are forced to do a sort(aList) again, which will take approximately half the time needed to sort an unordered list. What the vList Xtra does is to KEEP that sorted state on disk. When the list is read back into memory, vList lets Director know that the list is still in a sorted state WITHOUT the need to do a time-consuming sort(). So you have the ability to do a fast search of your list immediately after reading it into memory.

 

Note: There is one situation where sorting a list can actually slow things down. If the list is a property list, and the properties are symbols, Director temporarily converts the properties to strings to order them aphabetically. The same process happens when you search for a target symbol. Both the target symbol and the list's symbols are converted to strings and a string compare is done until a match is found.