[jawsscripts] Re: JAWS Sorting Library
- From: Doug Lee <doug.lee@xxxxxxxxxxxxxxxx>
- To: jawsscripts@xxxxxxxxxxxxx
- Date: Mon, 9 Apr 2012 11:04:08 -0400
Your assertion that stringSegment fails starting at the 4,000th
segment fascinates me, because I found a message I wrote way back in
2003 in which I actually pulled the 100,000th segment out of a string
with that function successfully. The message I wrote back then is
surely out of date by now, but for fun and perhaps nostalgia, I will
put it below in its entirety. I was testing several limits of JAWS at
the time, so the outlandishness of my tests and results may amuse some
people here. I have only the text file where I composed the message
text, not the message itself; therefore, the subject line is lost and
the posted copy may have been revised after this. I think the subject
was something along the lines of a "top ten scripting trivia" or
something silly like that. The stringSegment reference appears in item
7 below.
---begin old message---
1. getCursorCol and getCursorRow take more time to execute when
the PC cursor is active than when the JAWS or invisible cursor is
active. If JAWS can't find the PC focus, these functions can take
several times their normal execution time to complete. It is
therefore wise to avoid calling them from within frequently executed
code segments, such as high-speed loops or very often-called
functions or events.
2. There is an apparently undocumented function, int FindCaret(int
byRef x, int byRef y), which JAWS calls when it can't find the PC
focus. You can define this function in a script file and set x and
y to tell JAWS where the PC cursor is. WARNING: This function has
been known to get called up to 80 times per second, so it should
not contain code which takes much time to execute. The function
should return True if, on return, x and y point to the intended
location of the PC cursor, and False otherwise. An example of a
use for this function might be a terminal application which insists
on using a block cursor, which JAWS has trouble tracking. If you
can find the cursor by other means, such as a color search or use
of row/column numbers on the status line, you can make the PC cursor
work normally.
[Current note: FindCaret is now documented. Back to old text]
3. A loop construct of the form "let i=n while i ... let i=i-1
endWhile" runs a bit faster than "let i=0 while i<n ... let i=i+1
endWhile." Probably only important for very tight loops which may
iterate over 100 times.
4. Variable name length has a very tiny but measurable performance
impact on a running script. A very long variable name in a tight
and frequently-executed loop can cause a slight decrease in speed.
This is not nearly enough of an issue to cause any changes in coding
practice though; to find this, I had to compare execution speeds
of two loops that ran 10,000 times each, one using variable x and
the other using a variable whose name was 70 characters long. On
this machine, the two loops took about 300 miliseconds and 500
miliseconds, respectively. I just thought it was an interesting
find.
5. Contrary to what I've heard, I can't find any performance penalty
at all for accessing a global variable as opposed to a local one.
Neither do I see a difference in performance between using
pass-by-value and pass-by-reference variables when the variable is
re-used inside the function. I did not test the call times for
these two cases though.
6. JAWS can create a string of around 64 megabytes, but the
StringSegment command will cause JAWS to crash if executed against
a string longer than 534 K or so. Don't ask me what I was doing
mucking about with a 500 K string. <grin> Note to Paul Magill on
this one: Way back in March of 2001, you mentioned a practical
string size limitation of about 4K. Am I missing something here?
(The comment I refer to is in a messaged dated 03/19/2001 in which
Paul presented a pretty impressively thought-out system for managing
array structures in JAWS.)
7. StringSegment appears to be very efficient, contrary to what I
have been assuming for a long time. I got the 100,000th segment
of a 524 K string in a split second on a PIII 800. substring gave
me similar results. At least on this machine, I didn't notice
significant delays until the string got longer than 2 megabytes.
This machine has 128 megabytes of memory.
8. IniReadString and possibly IniWriteString truncate .ini file
lines at 255 characters. This includes the parameter name. I
believe this is a limitation of the Windows call used by JAWS to
access .ini files.
9. It is possible to define a function and a script with the same
name in the same .jss file, but only if the script is defined first.
If you try to define the function above the script, the Script line
will cause an "Ignoring previous definition" error message when
you try to compile the file.
10. JAWS can handle up to 6,000 headings on a web page. After
that, it will say you have only 6,000 headings and will only show
the first 6,000 in the insert+f6 list, though you can still see
the whole page in the virtual buffer. Typing insert+f6 from within
a section below the 6,000th section will land you at the bottom of
the list of headings but will not crash JAWS. Tested under JAWS
4.51 public beta. Subheadings' effect on heading count limit not
tested.
---end old message---
On Wed, Apr 04, 2012 at 11:59:01PM -0300, Andrew Hart wrote:
John,
No worries. Your welcome. The good news is that I didn't use
collections in the code. It's all done with arrays and the array size
doesn't change anywhere. the only thing is that you have to tell the
HeapSort function how big the array is, but your existing code probably
knows that already. It is possible to sort using collections, but while
collections are good for ... *embarrassed wink* collecting things ...
and of course they have their uses, they would be less efficient than
arrays.
Btw, while the code is well written (imho) and I have commented it
extremely liberally (both for myself, but also since other folks may
wish to study it), it could be a bit hairy to follow, especially if
you're not familiar with how binary trees, heaps and priority queues
work. But that shouldn't deter you from using it if it does the job.
Although I haven't seen your code, I suspect there is a good chance that
HeapSort could be integrated into it, but you'll have a far better idea
of just how feasible/easy/hard that will be to do once you have had a
chance to look at the samples and play with the code. Of course, don't
hesitate to ask any questions.
Oh, and I'm not sure if anyone is aware of this, but while I was
initially playing around with segmented strings, since that was what
John was using at the time, I discovered that the StringSegment function
only works for up to 3999 segments. Segment 4000 contains the entire
rest of the string (including the vertical bars and all) and segments
after that return empty strings. So, it looks like StringSegment has a
dodgy implementation. Perhaps JAWS strings were once upon a time
limited to only 4000 or 4096 bytes in length.
Cheerio,
Andrew.
On 4/04/2012 11:20 PM, John Martyn wrote:
> Oh my god Andrew. That just dumbfounded me. I was trying to follow along,
> but I am not familiar with collections yet. I just finally finished the
> conversion process for the super playlist creator, so I'll put out a link
> for the source. I don't think I could use what you are saying because I
> can't just sort the array to just anything because I need the count to stay
> the same, unless... I guess I could just put an integer value in with the
> array so it wouldn't lose the track integer when playing stuff or deleting
> items. I think it might be a little over kill though. I turned everything
> into arrays and it all works really fast now. That was my goal. It takes
> less than 2 seconds to process all the data.
> I'm going to study this code of yours and try to understand it.
> Thanks,
> John Martyn
>
> -----Original Message-----
> From: jawsscripts-bounce@xxxxxxxxxxxxx
> [mailto:jawsscripts-bounce@xxxxxxxxxxxxx] On Behalf Of Andrew Hart
> Sent: Wednesday, April 04, 2012 8:21 AM
> To: jawsscripts@xxxxxxxxxxxxx
> Subject: [jawsscripts] JAWS Sorting Library
>
> Hi folks,
>
> Recently we've been discussing sorting in JAWS. Here's a small library of
> code I have written for doing fast sorting in JAWS. It may be possible to
> make the code faster, but this is a good start. I'll paste the code below,
> but before I do that, perhaps I'll just give a brief explanation of how to
> use it.
>
> The function that does the sorting is called HeapSort. There are two helper
> functions HeapSort uses, Heapify and SiftDown. There are two utility
> functions for converting from segmented strings to string arrays and back
> again: SegmentedStringToArray and ArrayToSegmentedString. The final two
> functions are samples that you can play with to see how it all
> works: HeapsortSample1 and HeapsortSample2.
>
> To see it working, just paste the code into a jss file, dump one or both of
> the sample functions into a script, assign the script a key, compile and try
> it out.
>
> I've tried to make the code fairly generic so it can just be added to
> existing scripts and used without modification. However, if you are doing
> something really special, the paradigm I've used may not suffice and you'll
> have to get in and hack things to fit your purpose.
> So, here's how you use it. Suppose you have something you want to sort.
> You first create a StringArray, say, keys, and fill it with a set of sort
> keys corresponding to what you want to sort. If we use John's project as an
> example, he has a large 8 column array. For the purpose of exposition I'll
> call it tuneData. tuneData is, say, 2000 by 8. If one of those columns
> contains the album title and we want to sort the data by album, we would
> create a one-dimensional array containing the album titles using code like
>
> keys = New StringArray[2000]
> For i = 1 To 2000
> keys[i] = tuneData[i, 2] ; supposing that the album title is the second
> column of tuneData endFor
>
> We also need to declare an IntArray to hold the result of the sort.
> Var IntArray indices
>
> Now we're ready to sort, which is done with the statement Heapsort(keys,
> 2000, indices)
>
> That's it. indices now holds the indices to keys but sorted into their
> correct order. Note that Heapsort does not modify the keys array. The
> indices array that it returns tells you how to arrange the items in keys so
> that they are in lexicographic order. So, if you were to examine
> keys[indices[1]], keys[indices[2]], keys[indicies[3]], etc., you'd find them
> in order.
>
> I haven't written a utility function for applying indices to keys, because
> it depends on what it is you are sorting. For example, rearranging a simple
> StringArray like keys in this example is different from rearranging the rows
> of tuneData. I've left this for the programmer to write, but here's an
> example of how to do it:
>
> Var tuneDataSorted = New VariantArray[2000, 8] For i = 1 To 2000
> For j = 1 To 8
> tuneDataSorted[i, j] = tuneData[indices[i], j]
> EndFor
> EndFor
>
> I should probably write a couple of functions for handling stock standard
> cases of sorting segmented strings and string arrays so they can just be
> used as black boxes, but I haven't had time to do that as yet.
>
> I hope this is enough info to get anyone interested started in playing with
> it.
>
> Now, here comes the code library, just after my sig. Btw, I also have a
> jsd file for these scripts, since I compiled them in a sortlib.jsb and
> simply invoked the Use statement to import them into my test scripts.
> If anyone wants the jsd file, just let me know.
>
> Cheers,
> Andrew.
>
>
> ; JAWS Sorting Library
> ; andrew Hart (April 2012)
>
> ; *** Heap sort ***
>
> Void Function HeapSort(StringArray keys, Int arrayLen, IntArray ByRef
> indices)
> Var
> Int i, ; integer counter
> Int nIdx ; temp Int for swapping
> Let indices = new IntArray[arrayLen]
> ; Set up the original indices
> For i = 1 to arrayLen
> Let indices[i] = i
> EndFor
> Heapify(keys, arrayLen, indices) ; organise the array into a binary heap Let
> i = arrayLen While i>1
> ; swap the root node (index 1) with the last node in the heap (index i)
> Let nIdx = indices[i]
> Let indices[i] = indices[1]
> Let indices[1] = nIdx
> Let i = i - 1 ; decrement i to shrink the heap by one, removing the last
> element from the heap and thus leaving it sorted
> SiftDown(keys, 1, i, indices) ; sift the new root node into the correct
> place in the heap, since it will most probably be in the wrong place
> EndWhile EndFunction
>
> Void Function Heapify(StringArray heap, Int nEnd, IntArray indices) ;
> Organise the indices array so that when the array "heap" is ordered
> according to it, we obtain a heap.
> ; A heap is a tree in which each node is larger than (or is ranked as coming
> after) any of its children.
> Var
> Int nStart
> Let nStart = (nEnd-2)/2 + 1 ; find the last parent node in the heap While
> nStart>=1 ; while we haven't processed the root node of the tree
> SiftDown(heap, nStart, nEnd, indices) ; sift the current node down the
> tree until it is larger than any of its children
> Let nStart = nStart-1 ; move to the next node that we haven't sifted yet
> EndWhile ; That's it. The indices and heap arrays now encode a heap
> structure.
> EndFunction
>
> Void Function SiftDown(StringArray heap, Int nStart, Int nEnd, IntArray
> indices)
> Var
> Int nLeftChild, ; for holding the index of the left child of the root
> Int nSwap, ; for holding the swap index
> Int nRoot, ; for holding the root index
> Int nIdx ; temp Int for facilitating swap If nStart<1 || nStart>nEnd Then
> ; trap caller stupidity so JAWS doesn't go tropo
> Return
> EndIf
> Let nRoot = nStart ; set the root to the start node specified by the caller
> While nRoot*2<=nEnd
> Let nSwap = nRoot ; initially set the swap index to the root index
> nLeftChild = nRoot*2 ; get the index of the root's left child node
> If StringCompare(heap[indices[nSwap]], heap[indices[nLeftChild]])<0 ; if
> the root is smaller than it's left child
> Let nSwap = nLeftChild ; make the left child the swap target
> EndIf
> If nLeftChild<nEnd then ; if the root has a right child node
> If StringCompare(heap[indices[nSwap]],
> heap[indices[nLeftChild+1]])<0 Then ; if the currently selected swap target
> is smaller than the root's right child
> Let nSwap = nLeftChild+1 ; make the right child the swap target
> EndIf
> EndIf
> ; Decide whether or not to swap
> If nRoot!=nSwap Then ; if the swap target is no longer the root node
> ; exchange the root and swap nodes
> Let nIdx = indices[nSwap]
> Let indices[nSwap] = indices[nRoot]
> Let indices[nRoot] = nIdx
> Let nRoot = nSwap ; make the swap node the root and repeat to continue
> sifting the root down the branch Else
> Return ; heap property recovered, done sifting, bail out here EndIf
> EndWhile EndFunction
>
>
> ; *** Utility functions for converting back and forth between segmented
> strings and string arrays ***
>
> String Function ArrayToSegmentedString(StringArray a, Int arraylen, String
> sep, optional IntArray indices) Var
> Int i,
> String s
> If indices[1]<1 ; if no indices array is passed in
> Let indices = New IntArray[arrayLen]
> For i = 1 To arrayLen
> indices[i] = i
> endFor
> EndIf
> Let s = a[indices[1]]
> For i = 2 to arrayLen
> Let s = s + sep + a[indices[i]]
> EndFor
> Return s
> EndFunction
>
> Int Function SegmentedStringToArray(String segString, String sep,
> StringArray ByRef a) Var
> Int i,
> Int segCount
> Let segCount = StringSegmentCount(segString, sep) Let a = New
> StringArray[segCount] For i = 1 to segCount
> Let a[i] = StringSegment(segString, sep, i) EndFor Return segCount
> EndFunction
>
>
> ; *** Sample Code and Example Code ***
>
> Const
> testarraylen = 10000 ; number of items to sort in HeapSortSample1
>
> Void Function HeapSortSample1()
> Var
> Int i, ; a counter
> Int j, ; used as a counter and to hold a boolean value during testing
> String s, ; a string
> StringArray testarray, ; the array of sort keys IntArray perm ; the array
> to hold the indices output by the sort ; Build a string containing 500 b's
> Let s = ""
> For j = 1 To 500
> Let s = s+"b"
> endFor
> ; Create the test array and fill it with something to sort Let testarray =
> new StringArray[testarraylen] ; create an array of testarraylen elements ;
> fill the test array with keys for i = 1 To testarraylen
> Let testarray[i] = IntToString(testarraylen+1-i)+s EndFor ; Now perform
> the sort
> SayString("starting") ; announce start
> Let i = GetTickCount () ; record starting time heapSort(testarray,
> testarraylen, perm) ; do the sort
> SayInteger(GetTickCount()-i) ; announce the number of ticks that elapsed
> during the sort. 1 tick = 1 ms
> SayString("done") ; announce done
> ; Check to see if the perm array holds the indices sorted into lexicographic
> order Let j = 1 ; set j to True For i = 1 To testarraylen-1
> Let j = j && (StringCompare(testarray[perm[i]], testarray[perm[i+1]])<=0)
> EndFor If j Then
> SayString("Sort successful")
> Else
> SayString("Sort failed")
> EndIf
> EndFunction
>
> Void Function HeapsortSample2()
> Var
> String s, ; the initial segmented string to sort
> String sorted, ; the resulting segmented string
> Int nKeys, ; the number of keys in the keys array
> StringArray keys, ; array for holding the sort keys
> IntArray indices ; the sorted key indices output by Heapsort Let s =
> "dog|rat|pig|cat|bat|ant|owl|ox|tiger|elephant|fish|whale|snake|llama|frog"
> ; convert to a string array of sort keys Let nKeys =
> SegmentedStringToArray(s, "|", keys) HeapSort(keys, nKeys, indices) ; do the
> sort Let sorted = ArrayToSegmentedString(keys, nKeys, "|", indices) ; build
> a segmented string from the keys array DlgSelectItemInList(sorted, "Animal
> Names", 0) EndFunction
>
>
> __________???
>
> View the list's information and change your settings at
> //www.freelists.org/list/jawsscripts
>
> __________???
>
> View the list's information and change your settings at
> //www.freelists.org/list/jawsscripts
>
>
>
__________???
View the list's information and change your settings at
//www.freelists.org/list/jawsscripts
--
Doug Lee, Senior Accessibility Programmer
SSB BART Group - Accessibility-on-Demand
mailto:doug.lee@xxxxxxxxxxxxxxxx http://www.ssbbartgroup.com
"While they were saying among themselves it cannot be done,
it was done." --Helen Keller
__________�
View the list's information and change your settings at
//www.freelists.org/list/jawsscripts
Other related posts:
