[jawsscripts] Re: JAWS Sorting Library
- From: Andrew Hart <ahart@xxxxxxxxxxxxx>
- To: jawsscripts@xxxxxxxxxxxxx
- Date: Wed, 04 Apr 2012 23:59:01 -0300
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
Other related posts:
