[jawsscripts] Re: JAWS Sorting Library
- From: "John Martyn" <johnrobertmartyn@xxxxxxxxx>
- To: <jawsscripts@xxxxxxxxxxxxx>
- Date: Mon, 9 Apr 2012 08:46:39 -0700
Very cool.
Of course I like while statements over for statements. I am sure there is
some time difference since you are iterating on an integer rather than a
dynamic condition. Usually I write my while statements like
While trigger != 1
Let safety = safety+1
If something == something then
Let trigger = 1
Endif
If safety == 20 then
Let trigger = 1
Endif
endwhile
Personally I like the arrays for huge data amounts, but nothing beats a
string segment when you are calling different language sets. I put all my
messages in a segmented string, well, the variables I mean, then call the
function like message(1) and so it passes the 1 through to the segment and
speaks the correct message. For this I have different JSS files for each
language, and one code file that every JSS file uses. With each language set
of files, they all contain the same code except for the includes of JSM
files.
Best way to have multi language sets since I had to come up with this one
all on my own. I didn't like a bunch of different languages compiled into
different packages. This was my own way of using the string segment for
something totally simple. The messages can be long, so I try to limit it not
knowing how long the whole message file will be. So far, I haven't over
stretched the limits now knowing how long a segment can be and the size.
If need be, you can separate the messages into different functions or place
another variable in the function to call the different segments.
I was kind of bummed that I didn't see multi language solutions when I first
got the idea to compile it all into one package. It certainly adds up the
files in the ENU directory though. But on the plus side, less work for you
the programmer. This is also a fine way to hide the source for translators
since all the language files look the same and merely call functions. Each
language set must have it's own JKM file too which can be a pain when you
add a key shortcut.
Anyway, good morning to all and I'm off to my coffee.
John
-----Original Message-----
From: jawsscripts-bounce@xxxxxxxxxxxxx
[mailto:jawsscripts-bounce@xxxxxxxxxxxxx] On Behalf Of Doug Lee
Sent: Monday, April 09, 2012 8:04 AM
To: jawsscripts@xxxxxxxxxxxxx
Subject: [jawsscripts] Re: JAWS Sorting Library
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 __________o?=
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
Other related posts:
