Tuesday, December 12, 2017

#1 2015-01-31 09:53:37 am

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Inserting values into a sorted list, using binary sort.

Hello.

I haven't seen such a handler here already, and I think it should be a tad faster, than concatenating  two list, and running quickSort over the new list, since the list is sorted up front.

I have snagged Nigel Garveys binarySearchForClosestMatch match handler in order to do so. And StefanK's orderdInsert handler, because that handler is what made me make binaryOrderedInsert. StefanK's handler, should be used as long as there are less than 16 items in the list or so.

Applescript:

on orderedInsert(_list, _itemToInsert)
   -- [url]http://macscripter.net/viewtopic.php?pid=178428[/url]
   -- StefanK
   set end of _list to _itemToInsert
   set i to count _list
   repeat while i > 1 and _itemToInsert < item (i - 1) of _list
       set item i of _list to item (i - 1) of _list
       set i to i - 1
   end repeat
   set item i of _list to _itemToInsert
   return i -- position of new item
end orderedInsert



on binarySearchForClosestMatch(theList, theKey)
   # Based on:
   # [url]http://macscripter.net/viewtopic.php?id=41483[/url]
   # by: Nigel Garvey
   script o
       property lst : theList
   end script
   
   set l to 1
   set R to (count theList)
   
   repeat while (R > l + 1)
       set m to (l + R) div 2
       
       if (item m of o's lst < theKey) then
           set l to m
       else
           set R to m
       end if
   end repeat

   if class of theKey is integer or class of theKey is real then
       if (theKey - (item l of o's lst) > (item R of o's lst) - theKey) then
           return R
       else
           return l
       end if
   else if class of theKey is string then
       if theKey ≤ item l of o's lst then
           return l
       else if theKey ≤ item R of o's lst then
           return R
       else
           return (R + 1)
       end if
   end if
end binarySearchForClosestMatch

on binaryOrderedInsert(theList, newItem)
   -- [url]http://macscripter.net/viewtopic.php?pid=178453#p178453[/url]
   script o
       property lst : theList
   end script
   
   set ix to my binarySearchForClosestMatch(o's lst, newItem)
   if ix is 1 then
       if newItem < item 1 of o's lst then
           set nl to {newItem} & o's lst
       else
           set nl to {item 1 of o's lst} & {newItem} & items 2 thru -1 of o's lst
       end if
   else if ix < (count o's lst) then
       if newItem < item ix of o's lst then
           set nl to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
       else
           set nl to items 1 thru ix of o's lst & {newItem} & items (ix + 1) thru -1 of o's lst
       end if
   else
       if newItem < item -1 of o's lst then
           set nl to items 1 thru -2 of o's lst & {newItem} & {item -1 of o's lst}
       else
           set nl to o's lst & {newItem}
       end if
   end if
   return nl
end binaryOrderedInsert

Edit
I have removed a bug, which was testing for class = number, when the correct is to test for class = integer or class = real.

Thanks to Nigel Garvey.

Edit2

There was a another bug here as well, when concatenating the list when the new item, was bigger than the last item in the list.

Last edited by McUsrII (2015-02-01 12:47:17 pm)


Filed under: sort, insertion

Offline

 

#2 2015-01-31 03:06:18 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello.

I modified Nigels ClosestBinaryMatch handler, to work with strings as well as numbers, because I strings is really what I want to use it for at the moment. smile


Filed under: list, sorted, binary, insertion

Offline

 

#3 2015-02-01 09:01:57 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4451

Re: Inserting values into a sorted list, using binary sort.

Hi McUsrII.

Stefan's and your processes are essentially the last repeat in an insertion sort, with all but the last value having been sorted already and the last value being added to the list just before being sorted. Stefan's is an in-place sort; yours uses a binary-search for speed and returns a different list from the one which went in. It's also class dependent [*] and errors if the list starts off empty. [* Your check for the class of theKey being 'number' always returns 'false'. A number's class is either 'integer' or 'real'.]

Another, possibly unimportant difference is that a standard insertion sort is "stable". A value coming in from the right is inserted to the right of any values which are equal to it and so equal values remain in the original order with respect to each other. Since a binary search searches from both ends of the target range, it has to be weighted so that the right index remains to the right of any values which are equal to the one being inserted — if you want a "stable" insertion, that is. (It's a good idea anyway in an in-place sort, because fewer values then need to be shifted make room for the insertion.) Your binary search sets R to m if item m is greater than or equal to theKey, so it could place the insertion point to the left of an equal value.

Here's a stable in-place version adapted from my own binary-search insertion sort:

Applescript:


on binaryOrderedInsert(theList, v)
   script o
       property lst : theList
   end script
   
   set end of o's lst to v
   set len to (count theList)
   
   -- Binary search for a "stable" insertion point (ie. after any similar values).
   set l to 1
   set here to len
   repeat until (l = here)
       set m to (l + here) div 2
       if (item m of o's lst > v) then
           -- Reduce the right index only if item m's value is GREATER than v.
           set here to m
       else
           -- Otherwise advance the left.
           set l to m + 1
       end if
   end repeat
   
   -- Shift the values to the right of the insertion point.
   repeat with i from len - 1 to here by -1
       set item (i + 1) of o's lst to item i of o's lst
   end repeat
   -- Insert the new value.
   set item here of o's lst to v
   
   return -- nothing.
end binaryOrderedInsert

set lst to {}
repeat with i from 1 to 1000
   set end of my lst to i
end repeat

binaryOrderedInsert(lst, 0)
lst

The binary search idea allows an interesting development in that, if the insertion point's identified as being in the left half of the list, the insertion can be done from that end instead, reducing the number of values which have to be moved out of the way:

Applescript:


on binaryOrderedInsert(theList, v)
   script o
       property lst : theList
   end script
   
   set len to (count theList) + 1 -- What the list's length will be after the new value's added.
   
   -- Binary search for a "stable" insertion point (ie. AFTER any similar values).
   set l to 1
   set here to len
   repeat until (l = here)
       set m to (l + here) div 2
       if (item m of o's lst > v) then
           -- Reduce the right index only if item m's value is GREATER than v.
           set here to m
       else
           -- Otherwise advance the left.
           set l to m + 1
       end if
   end repeat
   
   -- Insert from the end of the list containing the insertion point.
   if (here > len div 2) then
       -- Insertion point in right half. Append the new value to the end of the list.
       set end of o's lst to v
       -- Shift the intervening values to the right.
       repeat with i from len - 1 to here by -1
           set item (i + 1) of o's lst to item i of o's lst
       end repeat
   else
       -- Insertion point in left half. Append the new value to the beginning of the list.
       set beginning of o's lst to v
       -- Shift the intervening values to the left.
       repeat with i from 2 to here
           set item (i - 1) of o's lst to item i of o's lst
       end repeat
   end if
   -- Insert the new value.
   set item here of o's lst to v
   
   return -- nothing.
end binaryOrderedInsert

set lst to {}
repeat with i from 1 to 1000
   set end of my lst to i
end repeat

binaryOrderedInsert(lst, 0)
lst


NG

Offline

 

#4 2015-02-01 10:35:45 am

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello.

You have made some nice handlers there

Thanks for the heads up on the fact that class has to be integer, and real. I have fixed that. When it comes to the checking for an empty list, then I am not sure, if it is wise, since I follow a convention of checking preconditons before I call a handler.

I didn't worry to much about stable, only that the items should come along in right order, I figured I'd reuse the closest match handler, and it is problematic for it to return a stable match, and so the problem permeats into the binaryOrderedInsert handler, if the list consists of non-unique values.

I am quite perplexed, over how fast the shifting of elements in your handlers are done. Your handlers isn't that much faster than what I came up with though. The average difference is 2 milliseconds faster, on 15000 elements. (I inserted129, so there is a lot of shifting going on. smile, but my unstable version becomes faster, when the element to insert is more of in the middle of the list, in those unrealistically large lists.

Your second handler is 1 millisec faster on the average when the element was 0. If the element to insert was 4500, then your handler seemed to be around 6 millseconds slower, (the list contained 10000 elements).

So, at some point, the shifting is slower than concatenating, but the number of elements in the list, is far higher than I anything I presume I am going to need. So, a stable version, and just one handler, is a way better alternative. Thanks. smile

Last edited by McUsrII (2015-02-01 11:03:34 am)


Filed under: binary, insertion

Offline

 

#5 2015-02-01 12:58:57 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello NIgel.

I scavenged your binaryOrderedInsert, into a binaryInsPos, and combined it with my insertion handler, that I have rewrote, based on the fact that binaryInsPos() is stable.

I am very pleased with the result.  It performs well on the average.

Applescript:

on binaryInsPos(theList, v)
   # Based on Nigel Garvey's BinaryOrdered Insert,
   # since it delivers a stable positioning.
   script o
       property lst : theList
   end script
   
   -- set end of o's lst to v
   set len to (count theList)
   
   -- Binary search for a "stable" insertion point (ie. after any similar values).
   set l to 1
   set here to (len + 1)
   repeat until (l = here)
       set m to (l + here) div 2
       if (item m of o's lst > v) then
           -- Reduce the right index only if item m's value is GREATER than v.
           set here to m
       else
           -- Otherwise advance the left.
           set l to m + 1
       end if
   end repeat
   return here
end binaryInsPos

on binaryOrderedInsert(theList, newItem)
   -- [url]http://macscripter.net/viewtopic.php?pid=178453#p178453[/url]
   script o
       property lst : theList
   end script
   
   if theList is {} then
       return {newItem}
   end if
   
   set ix to my binaryInsPos(o's lst, newItem)
   
   if ix is 1 then
       set NL to {newItem} & o's lst
   else if ix ≤ (count o's lst) then
       set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
   else
       set NL to o's lst & {newItem}
   end if
   
   return NL
end binaryOrderedInsert


Last edited by McUsrII (2015-02-08 08:12:45 am)


Filed under: list, binary, insertion

Offline

 

#6 2015-02-01 01:26:39 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4451

Re: Inserting values into a sorted list, using binary sort.

In my original, it's the 'here' variable which goes on to indicate the insertion point, as in "The insertion point is here." It doesn't matter technically, of course, because the exit from the search is when 'l' and 'here' are the same, but it's a bit perverse to call one of the variables 'here' and then return the other one!  lol


NG

Offline

 

#7 2015-02-01 01:42:47 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello.

My binaryOrderedInsert, now works a little bit better, because I removed anything from it, that could indicate that you wouldn't have to use the return value. And, the binaryInsPos, now returns here, and not l. smile

Last edited by McUsrII (2015-02-01 01:43:39 pm)

Offline

 

#8 2015-02-03 11:50:29 am

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello Nigel.

Having given this a little more thought, especially with regards to realistic sizes of lists. I doubt I'll ever need something more than say 500 items, at least as long as I deal with the kinds of data I can extract from the OS, with AppleScript.

As long as that assumption holds, I think your second handler is the best, but it should return the "here" value, so that one can update related lists, (one to one relations), using the already found position. for insertion. And then use some handler, that delivers the list, the pos, and the item, and returns a new list. smile


Filed under: Lists, sorted, binary, insertion

Offline

 

#9 2015-02-03 05:46:11 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4451

Re: Inserting values into a sorted list, using binary sort.

McUsrII wrote:

I think your second handler is the best, but it should return the "here" value…


Ah. Good idea! The return of nothing was a hangover from the sort from which the handler was adapted.

PS. By the way, I was thinking earlier today that a better way to compare the speeds of the various methods would be to see how long they take to build up a list of a certain length rather than how long they take to add one item to a list of a certain length. That should give a good idea of average performance. Generate a list of random numbers and see how long it takes each method to append items from that to its own, initially empty, test list.

Just for interest, I've also tried appending items to a list arranged as a heap rather than as a straight line, but there doesn't seem to be any advantage. And progressing though the heaped items in order would be a bit of a performance!

Last edited by Nigel Garvey (2015-02-03 06:34:20 pm)


NG

Offline

 

#10 2015-02-03 07:01:31 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello Nigel.

Let me say first of all, that at least my intended usage for binaryInsertionSort, is working with presorted lists, there is much more to gain, from using quicksort, or your stable sort, to sort the list before any elements are inserted. -But then it is rather nifty, to be able to insert an element or two at the correct position, and even update related lists.

It could be interesting to try to figure out the sweet spot with regards to peformance on a different number of  elements, and using a common  random number sequence. For the tests, between your and my take on the problem.


The heapSort algorithm would be interesting to see, but I can't see any use for it, in AppleScript directly, a priorityQueue could be an interesting tool, if the need ever arises, huffman encoding isn't practical from AppleScript either.

By the way: The sort command that comes with the shell, is  capable of doing topological sorts (like traversing a graph, or tree), so people are using it for sorting todo's and the like out there. smile

Edit

I think I now have understood what you were getting at. smile The binaryInsertionSort, uses the same number of comparisions, as you would, to insert a node in an unbalanced tree, which if memory is correct, is the underlying structure of a heap.  I would be easy to traverse, it would be efficient, for both insertion, and lookup.
The deletion of an element, would be the inverse of an insertion, so that is efficient as well. A change of an element would require a deletion and an insertion.

We could probably make an ubalanced tree work, as a datastructure for sorting in AppleScript,  but I'm not sure if it would be practically feasible, first and foremost, because of the complexity needed to implement it. But it could be a challenge. I'm not sure if there is any utility of it though, given the lengths of the lists, at least I operate on. It would maybe shave off a millsecond or two with  those numbers of elements.. It is not much of a gain. The other point against it, is that we are served most of our items in chunks, I believe it is faster to sort those chunks up front, if we don't get the chunks presorted somehow. So, heapsorting a pre-fabricated chunk of items, doesn't sound very efficient to me, (compared to quick/stable sort).

I am not going for implementing a heapsort, that is the conclusion, not now anyways, I don't see any "bang for the buck" in it.

Actually
Having said that, it is also a pity that the stackspace in AppleScript is so scarce, so you can't rely on recursion, to maintain the heap. That is one factor that complicates matters. You'd also probably need to use a list with three items for a node so the overall structure can become large given the structure around each item. That is  another limiting factor, (The max  number of actual items can't  greater than 4-5000, if the max number of elements is stil 2^14 items).

Sedgewick in "Algorithms" Second editon. Page 153 wrote:

The method called HeapSort, uses no extra memory, and is guaranteed to sort M elements in about MlogM steps, no matter what the input. Unfortunately, its inner loop is quite a bit longer than QuickSorts, and it is about twice as slow as QuickSort on the average.


Quicksort is N log N on the average, so HeapSort is 2N log N on the average. Having read up a little, I remember that we simulated trees with arrays (Lecture 10 - Implementing a Tree in an Array), which is perfectly doable with AppleScript's lists, it is even quite easy to grow the lists in either direction, where you simulate a tree with a simulated array. big_smile You can get a perceived speed advantage, if the data lends itself to it, as time consumption for sorting, are acquired each time something is inserted, if using something like a priortiy queue, which a user won't perceive as easily as one big list being sorted, which may become noticeable, as the sorting may stall a script or applet for some small amount of time, without the user fully understanding what is happening behind the scenes.

Last edited by McUsrII (2015-04-27 06:21:40 pm)

Offline

 

#11 2015-02-05 01:24:23 am

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello.

I implemented a priority queue, and used it for sorting, just as a theoretical excercise. It is really just an implementation of how a priority queue works, in the simplest possible way. smile

Applescript:

script pQueue
   property parent : AppleScript
   property beholder : {}
       
   on insert(pItem)
       set beginning of my beholder to pItem
   end insert
   
   on remove()
       set lcount to count my beholder
       if lcount is 0 then
           return missing value
       else
           set maxItem to item 1 of my beholder
           set tag to 1
           if lcount = 1 then
               set my beholder to {}
           else
               repeat with i from 2 to lcount
                   if item i of my beholder > maxItem then
                       set maxItem to item i of my beholder
                       set tag to i
                   end if
               end repeat
           end if
           if tag = 1 then
               set my beholder to rest of my beholder
           else if tag < lcount then
               set my beholder to items 1 thru (tag - 1) of my beholder & items (tag + 1) thru -1 of my beholder
           else
               set my beholder to items 1 thru -2 of my beholder
           end if
           return maxItem
       end if
   end remove
end script

set sorted to {}

repeat with i in {9, 4, 1, 19, 24, 93, 45}
   pQueue's insert(i)
end repeat

set resItem to {}

repeat while resItem is not missing value
   set resItem to pQueue's remove()
   if resItem is not missing value then
       set beginning of sorted to resItem
   end if
end repeat
log sorted
-- > (*1, 4, 9, 19, 24, 45, 93*)

Last edited by McUsrII (2015-04-27 06:54:28 pm)


Filed under: priority, queue, heap

Offline

 

#12 2015-02-05 03:40:12 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello.

Ok,  so I sat down, and wanted to implememt the heap for the priorityQueue with AppleScript, and then I realized, that the binaryInsertionSort, really is an as efficient method/datastructure for implementing a heap in AppleScript, as it can be. smile

Offline

 

#13 2015-02-07 05:27:18 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4451

Re: Inserting values into a sorted list, using binary sort.

Hi McUsrII.

Looking again at your script in post #5:

1. In the binaryInsPos() handler, since the new item's not added to the list there, 'here' should been initialised to len + 1 in case the new item has to go on the end.
2. In binaryOrderedInsert() handler, 'else if ix < (count o's lst) then' should be 'else if ix ≤ (count o's lst) then'.
3. binaryOrderedInsert() should return NL.

The following handler's just for the hell of it. I doubt it has many advantages!  smile

Applescript:


on ternaryInsPos(theList, v)
   script o
       property lst : theList
   end script
   
   -- The insertion point will be somewhere between item 1 and after the last item.
   set l to 1
   set here to (count theList) + 1
   
   -- Ternary search for a "stable" insertion point (ie. after any similar values).
   repeat until (l = here)
       -- m is here a third-of range marker rather than a middle-of-range one.
       set m to l + (here - l) div 3
       if (item m of o's lst > v) then
           -- Reduce the right index only if item m's value is GREATER than v.
           set here to m
       else
           -- Otherwise advance the left and third-of-range indices and try again.
           set l to m
           set m to (l + here) div 2
           if (item m of o's lst > v) then
               -- Reduce the right index only if item m's value is GREATER than v.
               set here to m
           else
               -- Otherwise advance the left.
               set l to m + 1
           end if
       end if
   end repeat
   
   return here
end ternaryInsPos

Last edited by Nigel Garvey (2015-02-08 06:56:18 am)


NG

Offline

 

#14 2015-02-08 04:50:30 am

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello Nigel.

I have corrected the handlers in post #5,  thanks for spotting the bugs.

I haven't looked at your ternaryInsertionSort but I will. I think its for specialized usage. smile

I hope I get time to implement a priority Queue, I have figured out before long, so spotting the culprits came in really handy at this stage.

Offline

 

#15 2015-02-08 07:20:39 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4451

Re: Inserting values into a sorted list, using binary sort.

McUsrII wrote:

I have corrected the handlers in post #5 …


Hi McUsrII.

binaryOrderedInsert()'s still returning the original list, not the concatenation result.

My ternary handler in post #13 also had an indexing problem when insertion points occurred at the ends of lists of certain lengths. I think it's now fixed. As I hinted earlier, it's just for fun. It appears on average to be slower than the binary version, having usually to test more items from the list.

Last edited by Nigel Garvey (2015-02-08 07:30:25 am)


NG

Offline

 

#16 2015-02-08 08:18:00 am

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Nigel Garvey wrote:
McUsrII wrote:

I have corrected the handlers in post #5 …


Hi McUsrII.

binaryOrderedInsert()'s still returning the original list, not the concatenation result.

My ternary handler in post #13 also had an indexing problem when insertion points occurred at the ends of lists of certain lengths. I think it's now fixed. As I hinted earlier, it's just for fun. It appears on average to be slower than the binary version, having usually to test more items from the list.


Sorry for the sloppiness, I am in the middle of something.

Algorithms are fun. smile I have to sit down and investigate your ternary sort a little. Now, a ternary search, as known from Alogrithm books, works over a range That hopefully only contains one extremal value. (Like the Newton Raphson method.) Now, you have bypassed that problem, since your range is sorted to begin with.


I'd say it could be used to fill in more values correctly, say if you miss point, and interpolate values, and then use your sort method so theey come in correct order before using the points to draw a graph or something. smile

On the other side of the extremal value, you'll have to reverse the result of course.

Just one usage, I came to think of.

Offline

 

#17 2015-02-08 03:19:58 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

This is for simulating a heap inside a priority queues, if the priorites,
are increasing with the value.

Priority queues are good for simulating stuff. Where you may have listeners
and writers, or both to the queue, and maybe uses a dispatcher, for sending
the event with the highest priority to the right receiver/observers.

The handler below, is totally scavenged from Nigel Garvey's binaryInsPos, and its
intended usage is for when the values increases with the priority.  This handler
is also "stable" which it needs to be, since I will use it too, as the basis
of a priority queue, which treats events with equal priorities in chronological
order.

Many places, priorities are made up the other way around, where a lower number
signifies a higher priority, then Nigels binaryInsPos is the best to use.

The principle of using a binarySearch based algorithm for inserting new values
in an already sorted list is effectively is, a practical implementation of a
"heap"  in  Applescript.  It however only  a  partially  acceptable  situation,
but the overhead/gain,is hard to measure, or at least complicated. The thing
is, a real heap uses a binary complete tree.  That's a lot of overhead
in AppleScript!  Real applications often uses arrays to simulate binary
complete trees, especially if they are residing in a kernel, and wants to
avoid memory leaks.

Thus, in order to use a binary complete tree in AppleScript, we may  implement it
by  simulating  a  tree  by an array, it is just that we don’t have arrays,
so  we’ll  have  to simulate  the array as well.  The alternative is to
use a "real" node structure, this means that for every value we’ll need to
have a record,  with four  values, that  we’ll have to book-keep.  (I see
no other way of implementing the "upheap" routine, that balances the tree.)
- We need to keep track of the parent node, in order to balance the tree, and
we need to have room for to new childnodes. Every node has to be created, as
new values are inserted and that operation isn’t as cheap, as in  languages
that  support memory  allocation -on the heap!  We’ll  have to use a handler
for it.  The priority queue that uses the "heap", is quite efficient, in that
you  just  remove the top item, and return the value, like a stack. A priority
queue can be viewed as the common ancestor of  both  a  stack and a queue.

Given all of the above I purport that using a binaryInsPos, is the best way
to implement a priorityQueue with AppleScript, even though the cost of inserting
elements are drastically higher than in a "real heap", -where that cost is 2logN (log(2)N)
it is here N-1 in the worst case.

But then again, we don't use priority queues that much in AppleScript.

It is mostly for fun, to simulate what the coffee maker says, when the customer
spills the coffee into the cash register. (That should be an event with high priority.) wink

Applescript:


on rBinaryInsPos(theList, v)
   # Based on Nigel Garvey's BinaryOrdered Insert,
   # since it delivers a stable positioning.
   script o
       property lst : theList
   end script
   
   -- set end of o's lst to v
   set len to (count theList)
   
   -- Binary search for a "stable" insertion point (ie. after any similar values).
   set l to 1
   set r to (len + 1)
   repeat until (l = r)
       set m to (l + r) div 2
       if (item m of o's lst < v) then
           -- Reduce the right index only if item m's value is LESSER than v.
           set r to m
       else
           -- Otherwise advance the left.
           set l to m + 1
       end if
   end repeat
   return r
end rBinaryInsPos

on rBinaryOrderedInsert(theList, newItem)
   -- [url]http://macscripter.net/viewtopic.php?pid=178453#p178453[/url]
   script o
       property lst : theList
   end script
   
   if theList is {} then
       return {newItem}
   end if
   
   set ix to my rBinaryInsPos(o's lst, newItem)
   
   if ix is 1 then
       set NL to {newItem} & o's lst
   else if ix ≤ (count o's lst) then
       set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
   else
       set NL to o's lst & {newItem}
   end if
   
   return NL
end rBinaryOrderedInsert

Edit
Changed a fact: the cost of insertion at least for some circumstances is around 2LogN for a "real" heap, not logN. (first locate the element which is logN (downheap), then insert it  somewhere else (upheap) which is also LogN.
LogN means the base 2 logarithm of N. Log(2)N

Last edited by McUsrII (2015-05-31 05:14:13 pm)

Offline

 

#18 2015-04-27 07:57:14 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello.

Here is a practical implementation of a priority queue. What's interesting with it apart from it being a proper priority queue, is that it exceeds the specifications, thanks to Nigel's work on the binary insertion sort handlers, which he made to be stable. Also great thanks to StefanK, that gave me the idea in the first place.

It takes records as values, and the records need to have a priority property.

The one unusal call to describe further here, is the replace() call, if the priority queue is made to be descending, and the item you want to replace has a greater priority than the item on top of the list, then that item is just returned.
if the list is ascending, then an item with lower priority is returned immediately, otherwise the top item is returned.

look() returns the top of the priority queue. remove() returns the top of the priority queue, and removes it. insert(v) inserts one, at its correct place according to its priority.

empty() tells if the priority queue is empty.

Applescript:

on newPriQueue(isDescending)
   -- Copyright © 2015 Nigel Garvey and McUsr, all faults are McUsr's.
   -- you may not publish this on the web or in print as your own work, but please
   -- refer to this link: [url]http://macscripter.net/viewtopic.php?pid=178453#p178453[/url]
   --    Creates either a descending or ascending priority queue.
   -- Uses in every practical sense a heap datastructure.
   -- the priorityQueue needs
   --Modify it to suit your needs.
   -- Sedgewick 2end Ed. p 146
   script pq
       property _pqList : {}
       property descending : isDescending
       
       on rBinaryOrderedInsert(theList, newItem)
           -- [url]http://macscripter.net/viewtopic.php?pid=178453#p178453[/url]
           script o
               property lst : theList
           end script
           
           if theList is {} then
               return {newItem}
           end if
           
           set ix to my rBinaryInsPos(o's lst, newItem)
           
           if ix is 1 then
               set NL to {newItem} & o's lst
           else if ix ≤ (count o's lst) then
               set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
           else
               set NL to o's lst & {newItem}
           end if
           
           return NL
       end rBinaryOrderedInsert
       
       on rBinaryInsPos(theList, v)
           # Based on Nigel Garvey's BinaryOrdered Insert,
           # since it delivers a stable positioning.
           script o
               property lst : theList
           end script
           
           -- set end of o's lst to v
           set len to (count theList)
           
           -- Binary search for a "stable" insertion point (ie. after any similar values).
           set l to 1
           set r to (len + 1)
           repeat until (l = r)
               set m to (l + r) div 2
               if (|priority| of item m of o's lst < |priority| of v) then
                   -- Reduce the right index only if item m's value is LESSER than v.
                   set r to m
               else
                   -- Otherwise advance the left.
                   set l to m + 1
               end if
           end repeat
           return r
       end rBinaryInsPos
       
       
       on binaryInsPos(theList, v)
           # Based on Nigel Garvey's BinaryOrdered Insert,
           # since it delivers a stable positioning.
           script o
               property lst : theList
           end script
           
           -- set end of o's lst to v
           set len to (count theList)
           
           -- Binary search for a "stable" insertion point (ie. after any similar values).
           set l to 1
           set here to (len + 1)
           repeat until (l = here)
               set m to (l + here) div 2
               if (|priority| of item m of o's lst > |priority| of v) then
                   -- Reduce the right index only if item m's value is GREATER than v.
                   set here to m
               else
                   -- Otherwise advance the left.
                   set l to m + 1
               end if
           end repeat
           return here
       end binaryInsPos
       
       on binaryOrderedInsert(theList, newItem)
           -- [url]http://macscripter.net/viewtopic.php?pid=178453#p178453[/url]
           script o
               property lst : theList
           end script
           
           if theList is {} then
               return {newItem}
           end if
           
           set ix to my binaryInsPos(o's lst, newItem)
           
           if ix is 1 then
               set NL to {newItem} & o's lst
           else if ix ≤ (count o's lst) then
               set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
           else
               set NL to o's lst & {newItem}
           end if
           
           return NL
       end binaryOrderedInsert
       
       
       (* The implementation of the Abstract datastructure Priority queue *)
       
       on insert(v)
           -- WAS tested 2015-4-24
           if class of (|priority| of v) is not integer then error "insert(): only integers are accepted as input to this priority queue!"
           if my descending then
               set my _pqList to rBinaryOrderedInsert(my _pqList, v)
           else
               _pqList of me to binaryOrderedInsert(my _pqList, v)
           end if
       end insert
       
       on remove()
           -- WAS tested 2015-4-24
           -- returns the largest element of the priority queue
           set pqllen to length of my _pqList
           if pqllen is 0 then return null
           set v to item 1 of my _pqList
           set my _pqList to rest of my _pqList
           return v
       end remove
       
       on replace(u)
           -- tested 2015-4-24
           set v to look()
           -- replaces the largest/smallest item (descending/ascending)
           -- if the new item is lesser / bigger.
           if my descending then
               if |priority| of u < |priority| of v then
                   remove()
                   insert(u)
                   return v
               else
                   return u
               end if
           else
               if |priority| of u > |priority| of v then
                   remove()
                   insert(u)
                   return v
               else
                   return u
               end if
           end if
       end replace
       
       on look()
           if length of my _queueList is 0 then return null
           return item 1 of my _queueList
       end look
       
       --    change the priority of an item
       -- no can do, since we don't take data with us.
       -- so there is no priority to change.
       -- The way to do it, is to get at the item.
       -- thru binary search.
       -- then delete it, so we get it out,
       -- give it new priority, and
       -- insert it back in.
       
       on empty()
           return my _pqList = {}
       end empty
   end script
end newPriQueue

Edit

Removed: deleteItemNr() deletes a specific item number from the priority queue, because it has nothing to do there, really.

2015-04-28 19:00 CET: Added "bars" or "pipes" around the property priority, "manually", so they are compiled into the code, they may then just disappear, but that is perfectly fine. (Thanks to StefanK and DJ Bazzie Wazzie)

Last edited by McUsrII (2015-04-28 01:00:23 pm)


Filed under: pq, priority queue

Offline

 

#19 2015-06-03 04:51:51 pm

McUsrII
Member
Registered: 2012-11-21
Posts: 3046
Website

Re: Inserting values into a sorted list, using binary sort.

Hello.

This is a fully working minimum priority queue, that is, a priority queue, where the lesser priority is the most significant, -gets out of the priority queue fastest.

The records fed to the queue needs to have the fields |priority| and |key|. It is not optimized in any way, with regards to inlining of calls. And it wouldn't be so easily implemented, hadn't it been for the insights of Nigel Garvey. Thanks.

If you want a priority queue of descending order, and don't have the patience for me to come around to it, then feel free to do so yourself. smile

Applescript:

on newMinPqueue()
   script content
       (*
       Implemented by McUsr in Applescript, with the help of contributions by Nigel Garvey.
       Original API description found in Sedgewick Algorithms 2nd. edition.
       *)

       property _pqList : {}
       
       (* Internal handlers *)
       
       on _binaryInsPos(theList, v)
           # Based on Nigel Garvey's BinaryOrdered Insert,
           # since it delivers a stable positioning. This handler only considers |priority|
           # whereas the binaryDelPos must consider |key| as well.
           
           script o
               property lst : theList
           end script
           
           set len to (count theList)
           
           -- Binary search for a "stable" insertion point (ie. after any similar values).
           set l to 1
           set here to (len + 1)
           repeat until (l = here)
               set m to (l + here) div 2
               if priority of item m of o's lst > priority of v then
                   -- Reduce the right index only if item m's value is GREATER than v.
                   set here to m
               else
                   -- Otherwise advance the left.
                   set l to m + 1
               end if
           end repeat
           return here
       end _binaryInsPos
       
       (*

   Assumptions, there can just be one combination of the same key and the same priority in the priority queue
   in one single instance of time. Said in a different way: there can be no equal pairs in the priority queue
   Example: {|priority|:5,|key|:10} can't be inserted, if the item already exists.
   
   It is your responsibility, to see to, that this doesn't happen.
*)

       
       on _binaryDelPos(theList, v)
           -- Based on Nigel Garvey's BinaryOrdered Insert,
           -- since it delivers a stable positioning. -Its inlined for speed!
           -- After being put behind last item with that priority in the queue,
           -- we scan forward one by one, until we find the one, or not, with "our" key.
           script o
               property lst : theList
           end script
           set len to (count theList)
           -- Binary search for a "stable" insertion point (ie. after any similar values).
           set l to 1
           set r to (len + 1)
           repeat until (l = r)
               set m to (l + r) div 2
               if (priority of item m of o's lst > priority of v) then
                   -- Reduce the right index only if item m's value is LESSER than v.
                   set r to m
               else
                   -- Otherwise advance the left.
                   set l to m + 1
               end if
           end repeat
           set found to false
           
           set start to (r - 1)
           -- this is the "last" item, (closest to the end) with that priority
           -- from here on after, we must see if we can find a record with the
           -- same key, while the priority doesn't change "upwards" in the priority queue.
           repeat with i from start to 1 by -1
               
               if priority of item i of o's lst = priority of v then
                   if |key| of item i of o's lst = |key| of v then
                       set r to r - (start - i + 1)
                       -- There can be only one!
                       set found to true
                       exit repeat
                   end if
               else
                   exit repeat
               end if
           end repeat
           if not found then
               return 0
           else
               return r
           end if
       end _binaryDelPos
       
       on _deleteItemNr(ix)
           if ix > length of my _pqList then return null
           set i to item ix of my _pqList
           if ix is 1 then
               set my _pqList to rest of my _pqList
           else if ix < length of my _pqList then
               set my _pqList to items 1 thru (ix - 1) of my _pqList & items (ix + 1) thru -1 of my _pqList
           else
               set my _pqList to items 1 thru -2 of my _pqList
           end if
           return i
       end _deleteItemNr
       
       (* The API *)
       
       on pqinsert(v)
           -- inserts an item into the queue, according to its priority.
           -- Relies on _binaryInsPos, with internals by Nigel Garvey.
           -- [url]http://macscripter.net/viewtopic.php?pid=178453#p178453[/url]
           if my _pqList is {} then
               set end of my _pqList to v
           else
               set ix to my _binaryInsPos(my _pqList, v)
               
               if ix is 1 then
                   set my _pqList to {v} & my _pqList
               else if ix ≤ (count my _pqList) then
                   set my _pqList to items 1 thru (ix - 1) of my _pqList & {v} & items ix thru -1 of my _pqList
               else
                   set my _pqList to my _pqList & {v}
               end if
           end if
       end pqinsert
       
       on pqremove()
           -- returns the element of the priority queue with the lowest priority (pop()).
           set pqllen to length of my _pqList
           if pqllen is 0 then return null
           set v to item 1 of my _pqList
           set my _pqList to rest of my _pqList
           return v
       end pqremove
       
       on pqreplace(v)
           -- replaces the smallest item (ascending priority queue) with the new item,
           -- unless the new item is lesser, returns the item that aren't staying in
           -- the priority queue.
           -- Opposite of:"Replace largest with new item, unless the new item is larger."
           set u to pqlook()
           if priority of v > priority of u then
               pqremove()
               pqinsert(v)
               return u
           else
               return v
           end if
       end pqreplace
       
       on pqempty()
           return my _pqList = {}
       end pqempty
       
       
       on pqlook()
           -- returns a peek of the next item that
           -- is to be removed from the priority queue
           if length of my _pqList is 0 then return null
           -- The priority queue starts at the top.
           return item 1 of my _pqList
       end pqlook
       
       on pqchange(v, pri)
           --Change the priority of an arbitrary item.
           -- returns the item, whether the priority was changed or not.
           set foundPos to my _binaryDelPos(my _pqList, v)
           if foundPos > 0 then
               if priority of v ≠ pri then
                   -- the pri wasn't the same, we'll have to remove it.
                   my _deleteItemNr(foundPos)
                   -- we update the priority
                   set priority of v to pri
                   -- and we insert it back
                   pqinsert(v)
               end if
               return v
           else
               error "pqchange: The item wasn't in the priority queue"
           end if
       end pqchange
       
       on pqdelete(v)
           -- delete an arbitrary specified item with the same |priority| and |key|.
           -- returns true upon success
           set foundPos to my _binaryDelPos(my _pqList, v)
           if foundPos > 0 then
               _deleteItemNr(foundPos)
               return true
           else
               return false
           end if
       end pqdelete
       
       
       on pqupdate(v, pri)
           (*
               It sees to that a vertices priority is lowered if possible, (in an ascending priority queue)
               if the record is not there, then it is inserted with the lowest priority.
           
           *)

           -- find the position of u in the queue, if it is there . . .
           set foundPos to my _binaryDelPos(my _pqList, v)
           if foundPos > 0 and priority of v = pri then
               return false
           else if foundPos > 0 then
               -- this is effectively the pqchange operation
               -- it is inlined, for efficiency
               --        log "prioritiy of v : " & priority of v
               if pri < priority of v then
                   -- the priority of v was larger, we'll have to remove it: Sedgewick p. 455
                   my _deleteItemNr(foundPos)
                   -- we update the priority
                   set priority of v to pri
                   -- and we insert it back
                   pqinsert(v)
                   -- and
                   return true
               else
                   -- priority of v was lesser than pri
                   return false
               end if
           else if foundPos = 0 then
               -- we blatantly update the priority queue with the record, and the least priority (ascending queue).
               if pri < priority of v then set priority of v to pri
               pqinsert(v)
               return true
           else
               error "update(u, pri): Hull breached, logic error!"
           end if
       end pqupdate
       
       on textRec(v)
           -- convenience, if you want a record to appear after some
           -- text in a log statement! :)
           return "priority: " & priority of v & ", key: " & |key| of v
       end textRec
       
       on pqinitialize()
           set my _pqList to {}
       end pqinitialize
   end script
end newMinPqueue

Driver:

Applescript:

set minpq to makeNewMinPqueue()
repeat with i from 1 to 10 -- by -1
   minpq's pqinsert({priority:i, |key|:(character id (i + 64))})
end repeat
-- return my _pqList
set rc to {priority:3, |key|:"N"}
set i to minpq's pqreplace(rc)
log "replaced : record with : " & minpq's textRec(i)
set delItem to minpq's _deleteItemNr(10)
set sc to {priority:2, |key|:"B"}
set ex to {priority:3, |key|:"O"}
minpq's pqinsert(ex)

set ex to minpq's pqlook()
minpq's pqupdate(ex, 2)
minpq's pqupdate(rc, 2)
minpq's pqupdate(rc, 4)
log "Thoroughly testing pqupdate:"
set lc to {priority:4, |key|:"Q"}
minpq's pqupdate(lc, 4)
minpq's pqchange(lc, 5)
set priority of delItem to 0
set y to minpq's pqreplace(delItem)
set newDelItem to {priority:9, |key|:"I"}
return minpq's pqdelete(newDelItem)

Edit

Added a pqinitialize handler, because this should be faster than "making" a new priority queue, and I changed the name of the "constructor" to newMinPqueue.

Last edited by McUsrII (2015-06-03 05:47:26 pm)

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)