Re: Implementing binary search without going deeper than top 2 items on stack?

Newsgroups	comp.lang.forth
Date	2016-07-26 01:53 -0700
References	<5db2ff24-c31d-45a0-a4f9-6b0515203925@googlegroups.com> <1a44b537-9878-43e0-95d4-3e41dbdd8614@googlegroups.com> <b41662eb-e500-4caf-8def-d63f33e17dc8@googlegroups.com> <a2c20464-67c7-476a-bb43-06d758f21adc@googlegroups.com>
Message-ID	<944a7e5d-2e29-4eab-8fa8-fa0abefbcbc0@googlegroups.com> (permalink)
Subject	Re: Implementing binary search without going deeper than top 2 items on stack?
From	josv@planet.nl

Show all headers | View raw

Hi,

See in the latest version of Win32Forth: 
~\win32forth\apps\Player4\mshell_r.f

Characteristics:
Uses relative as pointers.  So there is no need
  to generate the same pointers again when they are saved in a file.
Multiple keys can be used and sorted in one go.
The number of keys is only limited by the unused size of the stack.
Each key can be sorted in an ascending or descending way.
A key may contain a byte, word, cell, float or a string.
The sort is case-insensitive for strings.
Easy to expand to sort doubles etc.
Uses a shellsort.

Jos

On 25 july 2016 21:15:25 UTC+2 hughag...@gmail.com wrote:
> On Monday, July 25, 2016 at 1:32:57 AM UTC-7, humptydumpty wrote:
> > On Monday, July 25, 2016 at 11:10:21 AM UTC+3, Alex Dowad wrote:
> > > Here is another crack at it:
> > > 
> > >     : align<  [ cell 1- invert literal ] and ; \ align downwards to a cell boundary
> > > 
> > >     : reach ( a b c -- a b c a ) 2 pick ;
> > >     : mid   ( l r -- mid ) + 2/ align< ;
> > >     : pivot ( l r -- l r mid val ) 2dup mid dup @ ;
> > > 
> > >     : right-side ( l r mid -- mid+1 r ) rot drop cell + swap ;
> > >     : left-side  ( l r mid -- l mid ) nip ;
> > >     : bisect     ( l r val -- l' r' ) >r pivot r> < if right-side else left-side then ;
> > >     : different? ( a b -- a b f ) 2dup <> ;
> > >     : found?     ( val a a -- a|0 ) @ rot <> if drop false then ;
> > >     : bsearch    ( val l r -- addr|0 ) begin different? while reach bisect repeat found? ;
> > 
> > Hi!
> > 
> > : align<		( u -- u' )
> >   [ cell 1- invert ] literal and
> > ;
> > : mid  		( al ar -- am ; avoid sum overflow)
> >   over - 2/ align< +
> > ;
> > 	variable vp
> > : bis		( l r -- l' r')
> >   2dup mid dup @ vp @ @ < IF rot drop cell+ swap ELSE nip THEN
> > ;
> > : (bsearch)	( l r -- a|0 )
> >   begin 2dup <> while bis repeat @ vp @ @ <> if dup xor then
> > ;
> > \ needed? if
> > : bsearch		( l r v -- a|0)
> >   here vp ! , (bsearch) [ -1 cells ] literal allot
> > ;
> > \ then
> > \ TEST:
> > \ create first 1 , 3 , 5 , 7 , 9 , here cell - constant last
> > \ first 0 cells + dup vp ! first last (bsearch) = . .s -1 <0>  ok
> > \ first 1 cells + dup vp ! first last (bsearch) = . .s -1 <0>
> > \ last dup vp ! first last (bsearch) = . .s -1 <0>  ok
> > \ first last 8 bsearch . .s 0 <0>  ok
> > 
> > --
> > Have a nice day,
> > humptydumpty
> 
> You guys don't know what general-purpose code is? If you are going to write a binary-search function, it should work with any data-type! What happens if you later on need to binary-search an array of floats, or an array of structs sorted by some key? I know exactly what will happen --- you will cut-and-paste this binary-search (written specifically for an array of integers) and change it throughout so that it works with whatever data-type your application uses --- I can't actually think of any application that would involve an array of integers, so this cut-and-paste and modify exercise will certainly have to be done the first time your code is actually used in an application.
> 
> I already showed my SORT function. This was the API:
> 
> : sort { array limit recsiz 'comparer -- }
>     ... ;
> 
> \ The SORT locals:
> \ array             \ the address of the 0th element
> \ limit             \ the number of records in the array
> \ recsiz            \ the size of a record in the array     \ this must be a multiple of W (FIELD assures this)
> \ 'comparer         \ adrX adrY -- X>Y?
> 
> I would do something similar with a SEARCH function. I can write code like this easily --- now that the subject of binary-search has come up, I will write a SEARCH function and put it in my next novice-package release (not that I expect anybody to ever use it) --- in the meantime, I will leave it as an exercise for the comp.lang.forth experts.
> 
> I'm responding to HumptyDumpty's post because he is the only Forther on comp.lang.forth that I would expect to be capable of succeeding at this challenge (there is nobody on the Forth-200x committee who knows how to general-purpose code) --- come on HumptyDumpty, you can do it!
> 
> BTW: I think that HumptyDumpty is the smart one here because he uses a pseudonym on comp.lang.forth. If I had used a pseudonym rather than my real name then Elizabeth Rather would not have known that I was the guy who stole the job at Testra from her (after she makes a sales pitch to a potential customer, she considers that job to be her's, and she will hate forever anybody who steals her job from her) --- Elizabeth Rather would not have felt obliged to attack me and encourage her clown army to say that I'm totally incompetent as a Forth program and also insane --- she would have largely ignored me because a Forther who won't reveal his real name can't be considered to be competition to Forth Inc..
> 
> The lesson here is that anybody who is going to program in Forth should conceal his real name so as to avoid being attacked in public and made to feel ashamed of his hobby.

Thread

csiph-web