Page 1 of 1

Binary Searchs

Posted: 15 Nov 2009
by bowlesj3
Special update: Post #14 has an improved version of the two binary search scripts but the test script is still in the zip file in this post.

Here are two binary search functions. They are in the attached zip files. There is a test study for each of them now.

They are very good for situations where you drop an arrow (or vertical line) on the chart and want the code to find it to determine the bar information where it is located. This function will operate faster than the findbar function since the search is in binary. I have programmed it so that it also warns you that you have placed the arrow farther back than the maxbarsback setting. It also gives the same error if you place the arrow out front of the last bar on the chart. Both times it returns -1 as the offset.

I have changed them a bit since the first post. The details of the differences are in the second post. It is also well documented now as mentioned farther down.


Posted: 10 Feb 2010
by bowlesj3
NOTE: If anyone is actually using the old versions of these binary functions (the ones with at least 4 input parameters - the first two being a start and end value of a table) I highly recommend changing your code to use the new ones instead. I just did extensive testing and these new functions are bug free as far as I can see (I actually redesigned the code first in a language which has a proper debugger to be sure that I had the logic correct for reverse offset processing). If you set the maxbarsback setting high enough it can search your whole chart a lot faster than the findbar function.

The original version had two input parameters at the start which have been eliminated. Originally I was thinking that I should write it with the approach on the web page where I found the logic which I had not used in years. Specifically that it would search a table with a starting element and an ending element (able to search the start, middle or end of the table). However I never do that. Instead it is now written such that the searchs are always from the last bar on the chart back maxbarsback distance (a significant difference in the internal logic of the routine). This second approach lends itself better for checking if the search has exceeded the maxbarsback setting (see more info below).

The original version had a bug and could only search back a limited amount. This study can search back in binary as far back as the maxbarsize. It could be 60,000, whatever.

If the binary routine does not find the date/time of the arrow or line on the chart it will issue an alert and it tells you that you may need to increase the maxbarsback setting. The offset is returned as -1 in this situation. It has to return -1 because an offset of zero is a valid offset.

the 3rd parameter is just a way of indicating what study called it and exectly where within the study the call took place (to help with debugging). It is included in the print statement at the bottom if the alert is triggered by a no find. The RaiseRunTimeError command is there if you want to use it (just above the alert but commented out).

Before you read the following paragraph on the test scripts note that there is more info on how to efficiently run the test scripts in the 4th post below this post.

The test study is included to demo it and test it. You place an arrow on the chart (the arrow number has to be set in the test study input parameter), it finds the arrow and submits the date and time location of that arrow to the binary search to get the offset and the test study then places the high of that bar in the text along with the offset (note: the text also now includes the time of that bar where the arrow is located). Check the high of the bar reading on a few tests to be satisfied that it is working properly. Try placing the arrow back farther than the maxbarsback setting to see what happens. Try putting an arrow out front of the bars. I tested it with a maxbarsback setting of 4 first so I could test all combinations easily. Later I set it to 5000 and placed the arrow at 5000 and 5001 to be sure it was working. Note that if you start the test script and it does not find an arrow on the chart that matchs the input arrowID parameter then it gives you an alert notice showing the ArrowID parameter value. Note that there is a spacing parameter for spacing the text a certain distance from the arrow. In the future maybe I will change it so the text is in the arrow text field.

Here is why I made the changes. Other than fixing the bug mentioned above, the function before could try to do an offset during the search which is farther out than the maxbarsback setting. This causes MC to do a hidden recalculate over and over until it gets the high enough maxbarsback setting to find the arrow or vertical line. This can cause a very large maxbarsback setting and could cause your study to act funny since it keeps going back and executing the currentbar = 1 code over and over without your realizing it. I had this happen just recently and these changes are the result of that problem. I submitted a request for change to TSS asking that MC be changed to issue a popup alert every time it does this hidden recalculate so the user knows what is going on. I have seen MC do up to 7 recalculates before it gets the setting correct (deteremined by a GV counting test). In the mean time while MC does not notify you of this, one suggestion to deal with the fact that you do not get such a popup is to put a playsound at the start of your studies to notify you that this is occuring for some reason. If you do not do this the problem with this hidden recalculate is that your print statements keep getting reset and you have no way of knowing this is going on unless you use GVs to track it (maybe file append holds its writes so that may work - I think it does actually). Another way to detect this recalculate is to have the currentbar=1 code add 1 to a GV and if its value gets too high you could cause an alert to sound. At least with the binary search function as I now have it programmed you can get a notice that it has exceeded the maxbarsback setting and you need to increase it. It will not trigger a recalculate on you now.

Posted: 10 Feb 2010
by bowlesj3
I just attached a new zip file. It includes a test study for the binary function which is to be used for second bars.

Again, as noted above, If anyone is actually using the old versions of these binary functions (the ones with at least 4 input parameters - the first two being a start and end value of a table) I highly recommend changing your code to use the new ones instead. I just did extensive testing and these new functions are bug free as far as I can see. If you set the maxbarsback setting high enough it can search your whole chart a lot faster than the findbar function.

Posted: 11 Feb 2010
by bowlesj3
Sorry about this. I missed one test and there was still a bug in this binary search. It could not get to offset zero. So I litterly rewrote it today in a different language which has a very good debugger and stepped through it to make sure it is definitely working. Once I was 100% sure it was working there I applied those revisions to the EL code version and I have attached the new version just now. This version will return an offset of -1 if it is invalid (I have to go back and fix up the prior post wording to reflect this). So the test scripts are also revised to deal with the return of a -1 instead of a zero.

Regarding testing I did a test with MaxBarsBack of 4 so I could test every single combination easily including 5 back for a not found condition and out front for the other not found condition (both return -1).

I also set the maxbarsback on the test script to 5000 and went back to test 5000 and 5001 to be sure it was working perfectly on a larger test.

Posted: 11 Feb 2010
by bowlesj3
She is running mighty fine in production now (and the popup warning about being outside the search range has already caught one other none serious bug I had kicking around). Now it is written as she should have been all along. She is fully trustable I would say and much better than using findbar.

Posted: 12 Feb 2010
by bowlesj3
I just replaced the binary search code with code that has a full set of proper comments explaining it all. It includes comments right down to every single statement. It explains how the binary search works which explains how it has to work backwards for EL backward offset. I think it is a good idea to fully understand how it works.

Also I have set the test code MaxBarsBack to a value of 4 so it is easy to test the code. To make for a fast and easy test follow these steps.

First place the test arrow out front of the last bar on chart by 2 bars.
Determine the number for that arrow.
Insert the test script and set the ArrowID parameter before you turn it on.
The text spacing parameter setting of 1 should work okay.
Turn on the script and it will first show "off the end".
Move the arrow back bar by bar checking the text for accuracy.
Move the arrow back to bar 4 then to bar 5 which is past the MaxBarsBack.
You will see the popup alert at that point.

With 10 second bars you can just leave the arrow in place and as the bars move MC essentially moves the arrow for you. Obviously production code will have MaxBarsBack settings in the 100s or higher.

I also renamed the test scripts to:

Posted: 12 Feb 2010
by bowlesj3
Note (if you are obtaining date and time info from arrows or lines to submit to this routine) you should check them all for a -1 value before calling the binary search routine. Sometimes the ID of the arrow or line is okay but these other values return as -1 until a subsequent execution of the code causes them to finally return a good value. If you call the binary routine with a date of -1 or time of -1 it will issue a -1 offset. It may shut off your study if you are not testing for a -1 offset since your offset will cause your code to try and process in the future.

Posted: 13 Feb 2010
by bowlesj3
Actually it just occured to me that I could write something to autotest this binary search. I am thinking of a loop back to maxbarsback which calls the binary search on every bar and compares its result with the calling bar result. They should have the same offset. It could also test both off the front and off the back automatically. It would be a stronger test. If I do that I will include it in the zip file.

At the same time however, for others considering using this function, I figure the existing test has a different type of value since they can see it actually working and get some ideas for the use of arrows if they have never used them before.

Posted: 12 Mar 2010
by ctrlbrk
I'm new to MC. I think I know what you are describing but a couple screen shots would be helpful and probably elicit more input from the community as well ;)

Thx for the efforts and details!

Posted: 12 Mar 2010
by bowlesj3
Hi Mike,

Okay I attached a png picture of what you get when you run the test script on a 1 minute bar chart.

Also if you download the zip files, extract them and import the ELA files there are lots of comments in there and sample calls. I had the actual code in the forum but it does not indent well.


Posted: 12 Mar 2010
by bowlesj3
I included a picture in the post above.

Of note, after working with the new binary search function for a while, I have found that at times I will drop an arrow on a bar in the 10 second bar chart and the Arw_GetTime_s command returns a time but the bar for that time is not actually there. So you get the popup alert from the binary search which is exactly what it should do. I am assuming this is a bug in MC.

The same thing happens with any code in the 10 second bars where you are stepping a text box forward bar by bar and calculating the time of the next bar then doing a binary search on it. It may be that this bar does not actually exist on the chart and if it does not the binary search will report it as missing with the popup. In this case you need to step that text box by using the same offset rather than increasing the time to match a bar that you think should be there but which is not.

Posted: 18 Mar 2010
by bowlesj3
I changed the binary searchs to return
-1 if not found,
-2 if in the future.
-3 if before the maxbarsback

I also set it up to bypass the alert popup and the print statement if the word "Fix" is at the end of the Study input string. I won't get into why I did this other than the binary search in my 10 second bar studies often gets a valid bar not found popup and I did not want to add another parameter to have it bypass this alert/print message.

I was going to restrict this "fix" string bypass to only when a -1 was returned but decided to blanket any < 0 return status. Tweeks like this are pretty easy now.

Also the not found alert shows the date and time which was submitted to the function.

Re: Binary Searchs

Posted: 29 Jan 2012
by bowlesj3
Note: This loop function is now obsolete. Instead use the new version of the binary scripts which are described below in post #14. The new binary scripts (minute bar version and seconds bar version) are contained in Posts #15 and !6 give a bit more info on them.

I have created a loop function that calls the second bar binary search. I did this because often on the 10 second bars there is no actual bar with the date and time that is submitted. So this loop can be set to search ahead for X number of tries.

Warning: Note that the export included the binary search itself and the seconds calculation for adding 10 seconds. If you are using any time interval other than 10 second bars you need to change the script since the one in the zip file adds 10 seconds hard coded.

Re: Binary Searchs

Posted: 26 Dec 2012
by bowlesj3
Here is a version of both the minute bars and second bars binary script that has an option that allows you to get a valid offset value even if the date/time you are searching for is not found (normal offset return value of -1). What it does when you run the script this way is it will find the closest date/time offset in the future. If you study the code you can see how this works very clearly.

To run it with this new option, you call it as normal except you convert the input date to a negative value and the function figures out what to do. Here is an example.
offset = A_FindOffsetViaBinary(ArrowDate * -1,ArrowTime,"Calling Study and location");

If your search item is too old such that it is before the maxbarsback setting it will still return an offset of -3. (not tested yet but it should be okay).

If your search item is in the future it will still return an offset of -2. (not tested yet but it should be okay)

By the way, the script in the post above ( that loops over and over to find the same "closest future no find offset" is more efficiently replaced by this script. Post #15 indicates I added the change to the seconds version of the search.

Have fun.

Re: Binary Searchs

Posted: 27 Dec 2012
by bowlesj3
The zip file now contains both the "minutes" version and the "Seconds" version of the new binary search as described in the post above. After about 5 hours of use it seems to be working okay. A sample call is below. There are a few new comments in the minutes version.

offset = A_FindOffsetViaBinary_10Sec(Arw1Date * -1,Arw1Time,"Calling Study and location");

One note. I put in a field called "ClosestPastOffset" and included the move to this field. I am not using it anywhere else. It is just to demonstrate where this move would be if anyone wants to get the first date/time offset older than the one that was submitted and not found. I put a print statement in the one minute version to test this and it works.

Re: Binary Searchs

Posted: 28 Dec 2012
by bowlesj3
The new versions of the binary search scripts (available in post #14) are still basically working after a full day of use. However the alert message was still coming out when the bar being searched for was not found and the "closest future no find bar" option gets executed to return a valid offset. I fixed that small bug and reloaded both scripts in post #14. I also changed the Fileappend path to the C root directory.

Re: Binary Searchs

Posted: 30 Dec 2012
by bowlesj3
I should mention that in the event of running the new binary search scripts with the new option of submitting a negative date, in the event that the search finds the date/time element you are searching for if you still want the offset immediately next to that offset that is returned you would have to use the offset value that was returned after the function is completed to make that adjustment. In other words the two fields inside the binary script which are called ClosestPastOffset and ClosestFutureOffset will not have the correct value you are looking for during a successful find situation.

I wanted to point this out because it occurred to me that someone who does not fully understand the logic of the function may think they could write the value of these two fields out and always get a correct value. The fact is they will only be correct in a no find situation if the offset returned is valid. Also they of course will not be valid if -2 or -3 is returned.