It is currently Tue May 30, 2017 3:57 am



Welcome
Welcome to rfobasic

You are currently viewing our boards as a guest, which gives you limited access to view most discussions and access our other features. By joining our free community, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content, and access many other special features. In addition, registered members also see less advertisements. Registration is fast, simple, and absolutely free, so please, join our community today. **You are not required to provide truthful information to any registration questions. Be whomever you wish to be.!


Post new topic Reply to topic  [ 18 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: array.binarysearch
Unread postPosted: Fri Dec 11, 2015 8:30 am 
Offline
User avatar

Joined: Wed Jul 10, 2013 8:11 am
Posts: 328
In November Nicolas told us something about Binary Search.

What is Binary Search?
Is Binary Search a search routine in assembler or byte code?
No, it isn't. It's a search method with a different approach.

But in this case you need a sorted array like { A, C, H, I, K, P, T }.
If you are looking for P:
First compare the item in the middle of the array.
If P > I then look in the middle of the part rightwards.
If not then look in the middle of the part leftwards.
…. and so on.
You see, you are faster at the right position.

A simple search method starts at the first item and compares each item and stops at the right position if the item is on the list.

If you have to search in an array of 1,000,000 items you need averagely 500.000 steps with Binary Search only 22 with a little more effort.
Is this fantastic? Do you agree?

If you search in text lines for special words may be in program code for faster results you doesn't need extra arrays or you haven't to place keywords on top.

A snippet of the attached sample code:
Code:
! Binary search

   for   i = 1 to length
      left = 1
      right = length
      for   k = 1 to length
         middle = floor(left + ((right - left) / 2))
         if (result2$[middle] = result$[i])
               ! print middle, i
               F_N.break
            else
               if (result2$[middle] > result$[i])
                     right = middle - 1
                  else
                     left = middle + 1
               endif
         endif
      Next k
   Next i

Please try the attached code!
Attachment:
File comment: BASIC! sample file
BinarySearch2 forma.zip [990 Bytes]
Downloaded 23 times


So your Binary Search results should be 30 percent better as the common approach.

But the direct array.search command is 30 times faster.

So I suggest an array.binarysearch command which returns a positive index number if the right item is found or a negative index number with the nearest point to split the array and insert the new item in the right order.

An option in the array.sort command to delete double items would be nice, too.


Last edited by aFox on Fri Dec 11, 2015 9:31 am, edited 1 time in total.

Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Fri Dec 11, 2015 9:01 am 
Offline

Joined: Tue Dec 04, 2012 10:50 am
Posts: 656
Location: UK
aFox wrote:
If you are looking for P:
First compare the item in the middle of the array.
If P > I then look in the middle of the part above.

With the usual meaning of "P > I" then I think you should be searching the "part below", if the sort is towards higher values...

Mike.


Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Fri Dec 11, 2015 9:34 am 
Offline
User avatar

Joined: Wed Jul 10, 2013 8:11 am
Posts: 328
Hallo Mike,

I will change it to leftwards and rightwards.

Gregor


Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Fri Dec 11, 2015 3:09 pm 
Offline
User avatar

Joined: Sun Nov 23, 2014 8:15 am
Posts: 2185
Location: romania
We talked about this. Yes, binary search is effective ONLY on already sorted lists. And is way the fastest method.
For a list of n items, the number of iterations is LOG2(n). eg., as you said, for 1000000 sorted items, we need - at most - about 20 comparisons to find it.


Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Sat Dec 12, 2015 12:45 am 
Offline

Joined: Sat Dec 22, 2012 2:32 pm
Posts: 830
sorry, i don't understand why the request is connected to binary search ?

--edited--


.....now i got it ! (original remark obsolet!)

regards,
brochi


Last edited by brochi on Sat Dec 12, 2015 2:35 am, edited 1 time in total.

Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Sat Dec 12, 2015 1:22 am 
Offline

Joined: Sat Dec 22, 2012 2:32 pm
Posts: 830
Another little hint/remark, related to above shown code snippet: brackets in logical expressions are extremly 'expensive' in terms of execution-speed.

Just modifying
Code:
IF (result2$[middle] = result$[i])
..
IF (result2$[middle] > result$[i])
..

to
Code:
IF result2$[middle] = result$[i]
..
IF result2$[middle] > result$[i]
..


.....increases speed about 50% !



Our the other way around:
Code:
IF ((result2$[middle] = result$[i]))
..
IF ((result2$[middle] > result$[i]))
..

...is enough to make the bin search as slow as lin search (...for the given example).


regards,
brochi


Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Sat Dec 12, 2015 11:47 am 
Offline
User avatar

Joined: Wed Jul 10, 2013 8:11 am
Posts: 328
Yes, Bronchi you are right.

I translated this example from C.
In C and Java the brackets are standard.
So I overlooked the brackets.

I hope, we find a smarter and faster interpreter solution for the expensive brackets.

Happy coding!


Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Sat Apr 02, 2016 10:28 am 
Offline

Joined: Wed Oct 03, 2012 9:53 am
Posts: 2797
Location: Colorado, U.S.
aFox wrote:
An option in the array.sort command to delete double items would be nice, too.
You can't do this, because you can't remove elements from an array. Or did you have something else in mind?

You could have a command that removes duplicates from a list.

- Marc


Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Sat Apr 02, 2016 1:20 pm 
Offline
User avatar

Joined: Wed Jul 10, 2013 8:11 am
Posts: 328
Hi Marc,

In my opinion it make only sence to delete double items in a sorted list.
Copy the array, sort the copy, delete double items, delete the old one and rename the new one with the old Name.
Yes, the returned array is smaler.
What is the problem, I have overlooked?

- Gregor


Report this post
Top
 Profile  
 
 Post subject: Re: array.binarysearch
Unread postPosted: Sat Apr 02, 2016 10:32 pm 
Offline
User avatar

Joined: Tue Jan 03, 2012 9:31 am
Posts: 5518
Location: Paris, France
The only way to do that it to sort the array, dump it to a list, delete doubles in the list, then undim the original array, and dump the re-arranged list to it again.
And remove the list to clean memory...

Quite tedious, but possible.

The strange thing is having some functions for arrays and some others for lists, but it's not harmonized.
For example we can sort or shuffle an array but not a list.
And on the opposite we can remove elements from a list but not from an array.

Ideally I would like that we propose all functions for both structures.
It would avoid programmers to juggle between list and array.

Nicolas

_________________
- Creator of the Android BASIC! Compiler


Report this post
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 18 posts ]  Go to page 1, 2  Next


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
suspicion-preferred