Some hours after I posted this, I got the impressions that it might be
better
to explain some of the hidden secrets that may be still in this code.
First, the key field is in the records of the table at offset 3, that is
the reason,
why the compares with the search argument SUCHARG are done with
3(R7). The length of the compare is derived from the definition of SUCHARG,
and the type of the compare is CLC or CP; the Structured Programming macro
IF selects the machine instruction depending on the definition of SUCHARG.
Then, as you can see, the IF has two conditions, separated by an asterisk;
if the first condition is true, then control goes to the first THEN, if the
second condition is true, then control goes to the second THEN,
otherwise to the ELSE. This is in fact not a simple IF statement -
looks more like SELECT ... WHEN ... OTHERWISE.
The SP macros are home grown ... originally bought from another company
in the early 70s, IIRC - long gone history. It's part of my job to keep
them running;
I'm working as a free lancer for this company since 1988.
The rest should be self explaining ... I hope.
To generalize this example (for example, to put it into a macro), it is
only necessary to
parameterize some pieces of the code, that is:
- the number of the elements on entry
- the size of one element which is multiplied to the index
- the position of the key field
- the length of the key field (which goes into the compare instruction)
- and maybe the type of the compare instruction
To further generalize it, the compare instruction should be a function
call ...
Kind regards
Bernd
Am 26.10.2013 10:54, schrieb Bernd Oppolzer:
This is not necessary, and the binary search code is not at all
complicated.
Look at this:
MVI GEFUNDEN,C'0'
LH R4,=H'1'
L R5,EINGANZ
*
XR R9,R9 DURCHLAUFZAEHLER = 0
*
LOOP WHILE,((R4),<=,(R5))
AHI R9,1
* MITTE DER RESTL. ELEMENTE ERMITTELN
LA R6,0(R4,R5) R5+R4->R6 (ANZ. ELEMENTE)
SRA R6,1 DURCH 2 DIVIDIEREN
LR R7,R6
BCTR R7,0
MH R7,=Y(L'ESATZ)
AR R7,R3 TATSAECHL. ADR. MITTE
IF (SUCHARG,<,3(R7)),*,(SUCHARG,>,3(R7))
*
THEN
LR R5,R6 GROESSER, WEITERSUCHEN
BCTR R5,0
*
THEN
LA R4,1(R6) KLEINER, WEITERSUCHEN
*
ELSE
MVI GEFUNDEN,C'1'
BREAK
*
EIF
ELOOP
R3 - points at the start of the sorted table at the beginning
R4 - index, starting from 1, of the lower limit of the range to be
examined
R5 - upper limit, is initialized with EINGANZ at the beginning
R6 - is used to compute the index "in the middle"
R7 - is used to compute the address of the element "in the middle"
then the element in the middle is compared against SUCHARG,
depending on the result, R4 and R5 are adjusted, and the LOOP is
executed again, if necessary.
if not, you have a result (found or not).
R9 is used to count the loop executions, which will be floor(log2(n)),
where n is the number of elements in the vector (in the worst case).
At our shop, we have a macro which does this. No need to code
the binary search yourself every time you need it.
Kind regards
Bernd
Am 21.10.2013 22:49, schrieb Robert A. Rosenberg:
At 06:27 -0700 on 10/21/2013, retired mainframer wrote about Re:
Linear search vs binary:
If your search target is uniformly distributed against the key, then on
average a linear search will require 1750 iterations of your compare
loop.
A binary search will require a constant 12 iterations regardless of
distribution.
One trick that would make the binary search code simpler is to make
the table 4096 entries long not 3500 long. Place 298 low value
entries, then the 3500 live entries, and then 298 high values. This
will cause some wasted compares when you hit the padding low/high
values but you do not need to worry about how to spit the table in
half for each round (the size is always the prior power of 2).
