I just would like to add that the program that I posted some days ago
can be used to do non matching searches as well. In the not-found case
the loop is left with R6 containing the index (and R7 the address)
of the element that matches best (the element that has been compared
in the last execution
At 07:20 -0500 on 10/28/2013, John Gilmore wrote about Re: Linear
search vs binary:
A greatest lower bound (GLB) on a search argument or a least upper
bound (LUB) on it came be searched for in the same tables in which
matches are sought.
An example will help here. Suppose that we have a set
There is one respect in which this thread on binary search has been
unsatisfactory. It has concerned itself only with match-seeking
binary search, and bounds-seeking binary search is at least as
useful.
A greatest lower bound (GLB) on a search argument or a least upper
bound (LUB) on it came be
BTW: the German mainframe Telefunken TR440 had a machine instruction
which did a binary search on a sorted table of (48 bit) machine words;
the instruction
was called TLOG. Of course, there were other instructions for linear
search, too.
See page 17 of the instruction set reference (only availabl
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 b
1.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 sear
On 25 October 2013 13:28, John Gilmore wrote:
> Apart from its vulnerability to security-breaching abuses and the fact
> that it must often be copied to be operated upon, another major defect
> of ther nul-terminated string is that it may not contain a nul.
>
> I do not regard the nul-terminated s
>
> From: Robert A. Rosenberg
>To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
>Sent: Thursday, October 24, 2013 5:12 PM
>Subject: Re: Linear search vs binary
>
>
>At 12:45 -0400 on 10/24/2013, Tony Thigpen wrote about Re: Linear
>search vs binary:
>
>>All entries wil
Apart from its vulnerability to security-breaching abuses and the fact
that it must often be copied to be operated upon, another major defect
of ther nul-terminated string is that it may not contain a nul.
I do not regard the nul-terminated string as a serious, i.e.,
non-frivolous data type. Oddl
On 2013-10-25, at 10:11, John Gilmore wrote:
>
> Moreover, nuls are unproblematic; they are invariant, the
> same in ASCII, EBCDIC, . . .
>
Mostly true. But don't overlook the curse of the null-terminated
string.
-- gil
I will be out of the office on Monday and Tuesday the 28th & 29th of October,
returning to work on Wednesday 30th.
I will have no access to email / phone during this time.
For all urgent project/maintenance related questions or issues, please send a
mail to ANI - BOB-Visuals Support. For all ot
As I made clear in an earlier post, it is my habit to pad out table
elements with nuls, instances of x'00', to make all of their lengths
equal.
This operation is trivial in the macro language, but in response to
some off-line questions I note that either of
|&nulchar setc BYTE(x'00')
or
|&nulch
robin
Sent: Friday, October 25, 2013 7:13 AM
To: MVS List Server 2
Subject: Re: Linear search vs binary
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 10:05 PM
Convert your PLX code to assembler and you will see that you are
binary searching a pointer table that has fixed length ent
: Linear search vs binary
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 10:05 PM
> Convert your PLX code to assembler and you will see that you are
> binary searching a pointer table that has fixed length entries.
In PL/I , each string value (= each element of an array)
As I don't know PL/I or PLX and this is the Assembler list, let's talk
assembler.
You stated that your code produced a binary search against a table where
each row was variable length.
I said binary search can't work on such a table.
So, produce the code in assembler.
Tony Thigpen
-Origin
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 10:05 PM
Convert your PLX code to assembler and you will see that you are binary
searching a pointer table that has fixed length entries.
In PL/I , each string value (= each element of an array) occupies exactly the
same storage.
Convert your PLX code to assembler and you will see that you are binary
searching a pointer table that has fixed length entries.
Tony Thigpen
-Original Message -
From: robin
Sent: 10/25/2013 04:52 AM
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 12:16 PM
> In XPL, each strin
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 12:16 PM
> In XPL, each string is accessed via descriptor that contains in a single
> word
> the memory address and the length.
Your code is doing a binary search of the FIXED length POINTER table.
No it's not. The code re-posted for you i
> In XPL, each string is accessed via descriptor that contains in a single
> word
> the memory address and the length.
Your code is doing a binary search of the FIXED length POINTER table. It
is not doing a binary search of a table that has variable length rows.
As I said, any table with variabl
From: "Savor, Tom"
Sent: Friday, October 25, 2013 11:40 AM
Robin,
InterestingI would have said the same thing (if asked), that you can't have
binary search on
variable length keys.
Is your code posted C+ ?? I don't know it at all.
The code is PL/I.
How would you do this in Assembler
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 11:35 AM
Repost the code. Nothing I still have in my inbox shows code to perform
a binary search of a table where each row occurrence can be any length.
Array c has lower bound 0, upper bound n:
i = -1; k = n+1; /* pointers that always poin
Repost the code. Nothing I still have in my inbox shows code to perform
a binary search of a table where each row occurrence can be any length.
Tony Thigpen
-Original Message -
From: robin
Sent: 10/24/2013 08:15 PM
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 8:43 AM
After
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 9:14 AM
> On 2013-10-24 11:29, Blaicher, Christopher Y. wrote:
>> ...
>> The second method used a binary chop of the data then scanned for
the next entry. It was ugly, but it did its job. There are lots of
limitations to it.
>>
> Somewhat e
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 8:43 AM
After a couple of posts about my post, I will go back to my point.
You can only binary search a fixed length table.
Nonsense.
The table for the code that I posted previouisly consisted
of varying-length strings.
If you create an
From: "Tony Thigpen"
Sent: Friday, October 25, 2013 3:45 AM
All entries will be fixed length. Can't really have variable length and
use a binary search. :-)
The code that I posted previously was for variable-length strings.
Its been a while but bear with me and tell me if I am talking drivel...
I guess on a modern machine its not a problem, but on an older
environment with restricted memory and 4K page sizes then that is
going to be around 10 pages. If the data is paged out and item you are
looking for is in the firs
> On 2013-10-24 11:29, Blaicher, Christopher Y. wrote:
>> ...
>> The second method used a binary chop of the data then scanned for
the next entry. It was ugly, but it did its job. There are lots of
limitations to it.
>>
> Somewhat elliptical. I assume he means that from any point
> in the table
data to be compared. But,
> the pointer table is still a fixed length table. :-)
>
> You just can't binary search a variable length table.
>
> Tony Thigpen
>
> -Original Message -
> From: Robert A. Rosenberg
> Sent: 10/24/2013 05:12 PM
>> At 12:45 -0400 o
I am out of the office until Monday 11/4/2013. I will read your note, as time
permits, when I return to the office. If your e-mail is urgent and concerns a
production issue/problem, please send your note to the 'GLO-RETS zOS Content'
mailbox for attention.
Thanks!
On 2013-10-24 15:51, John Gilmore wrote:
> Tony writes that you just can't binary search a variable length table,
> and this is certainly true if what he means is that you cannot search
> a table the length of which changes while you are searching it.
>
> You can, however, search a table that varie
By variable length, I was talking about each ROW being variable length.
I.e, one row is 22 bytes, the next 10, the next 444.
Nothing to do with the number of rows in a table changing.
My original post stated:
"All entries will be fixed length. Can't really have variable length and
use a binary s
Tony writes that you just can't binary search a variable length table,
and this is certainly true if what he means is that you cannot search
a table the length of which changes while you are searching it.
You can, however, search a table that varies in length on different
occasions. How not?
Joh
/2013, Tony Thigpen wrote about Re: Linear
search vs binary:
All entries will be fixed length. Can't really have variable length and
use a binary search.
That depends. If the table you are sorting is a table of pointers to
the actual data (and is ordered by the compare field), the entries
can b
At 13:52 +0200 on 10/24/2013, Rob van der Heij wrote about Re: Linear
search vs binary:
On 24 October 2013 12:50, Don Higgins wrote:
I see discussion about optimizing the binary search, but I don't see any
discussion about optimizing linear search which might make it much faster
At 12:45 -0400 on 10/24/2013, Tony Thigpen wrote about Re: Linear
search vs binary:
All entries will be fixed length. Can't really have variable length and
use a binary search.
That depends. If the table you are sorting is a table of pointers to
the actual data (and is ordered by the co
P: 201-930-8260 | M: 512-627-3803
E: cblaic...@syncsort.com
-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU] On
Behalf Of Tony Thigpen
Sent: Thursday, October 24, 2013 11:46 AM
To: MVS List Server 2
Subject: Re: Linear search vs binary
All
I was thinking something more generic. The table description and layout
is outside the code. The code would be a generic branch and return routine.
How the table is loaded is also not part of the code. It could be done
at assemble time or at run time by reading a file.
Correctness of data is the
Tony,
The code you want must address a number of additional issues.
Are the elements to be assembled into the table all of the same
length? If not, they must be padded with nuls, x'00', and not blanks,
x'40'|x'20', at table-assembly time to make them so.
Is the search argument shorter than the
Now, I would like to see REAL assembler code for a binary search that
takes into consideration all the items being discussed and works for a
varying length tables, including an odd number of rows in the table.
To make it simple, assume:
R2 = @ first entry
R3 = @ last entry
R4 = length of each entr
Knuth's analysis of match-seeking binary search deals in an ordered
set of n keys
{k(1) < k(2) < . . . < k(i) < . . . k(n)}
and another set of 2n + 1 searches, viz.,
o one such that s < k(1), which fails,
o n - 1 such that k(i) < s < k(i+1),
i = 1, 2, . . . , n - 1, all of which fail,
o n
On 24 October 2013 12:50, Don Higgins wrote:
> I see discussion about optimizing the binary search, but I don't see any
> discussion about optimizing linear search which might make it much faster
> than binary depending on the search history. Putting the last key found at
> front of most recentl
All
I see discussion about optimizing the binary search, but I don't see any
discussion about optimizing linear search which might make it much faster
than binary depending on the search history. Putting the last key found at
front of most recently used list or just holding last found as a firs
On 24 October 2013 02:43, Paul Gilmartin wrote:
>
> The search may be terminated early (however infrequently) on
> discovering an exact match. But this requires an extra comparison
> if ternary results are unavailable (as they are in assembler --
> is that sufficiently on-topic?) The cost of th
On 2013-10-23 17:51, robin wrote:
>>>
>> ... the value of comparison operands [operators -- gil] having
>> a ternary result. Of course this is available in (zSeries)
>> assembler. It might typically shorten a table search by one
>> iteration.
>
> How is that?
>
The search may be terminated early
Glad you got some use out of it.
It's a pretty simplistic implementation, but sufficient for our needs.
Although based on how rapidly the discussion veered into other languages I
thought I'd missed your point somehow.
Sent from my iPad
> On Oct 23, 2013, at 9:43 AM, "Dougie Lawson" wrote:
>
From: "Paul Gilmartin"
Sent: Tuesday, October 22, 2013 1:42 AM
On 2013-10-21, at 07:13, John Gilmore wrote:
Perhaps also worth noting explicitly is that the linear-search scheme
done well is not significantly less complex than the binary-search
one.
You've earlier advocated the value of com
Hi Alan,
I found some test data.
I found a ready written IMS macro to sort my test data (which was a real
bonus).
And I got your code sample to run and get the right answer.
Thank you - I owe you a virtual beer.
To all the other correspondents - thank you - a simple request has
generated some
From: "Dougie Lawson"
Sent: Monday, October 21, 2013 10:32 PM
If I have a table of 3,500 entries of twelve bytes (I'm doing a compare of
eight bytes to find the entry I'm looking for and a check on a half word
marker for the end of the table to avoid running off the end) then is it
worth the p
I understand. I don't even need a computer to do that :-) The "return" was
just to discourage the optimizer to throw away all the code because I
didn't use the result.
The thing that kept me awake briefly was whether the optimizer would
recognize that the shortcut and code a single compare with tw
Rob,
Interestingly, when I take your C example,
if ( j < k ) m = -1;
else if (j > k) m = 1;
else m = 0;
return m;
and rewrite it trivially modified in PL/I as
if j < k then m = -1;
else if j > k then m = 1;
else m = 0;
return (m);
I cannot reproduce your results.
John Gilmor
From: "Rob van der Heij"
Sent: Wednesday, October 23, 2013 8:12 PM
Since the machine architectures that came to mind all have this 3-state
result after comparison, I expected the compiler to take advantage of it
when I write something like
if ( j < k ) m = -1;
else if (j > k) m = 1;
else m
Since the machine architectures that came to mind all have this 3-state
result after comparison, I expected the compiler to take advantage of it
when I write something like
if ( j < k ) m = -1;
else if (j > k) m = 1;
else m = 0;
return m;
A few surprises with gcc, like pretty dumb code wit
From: "John Gilmore"
Sent: Tuesday, October 22, 2013 9:31 AM
PL/I was robbed of FIXEDOVERFLOW for binary fixed values.
Use SIZE instead.
It is still
available for PL/I decimal fixed, i.e., packed decimal values.
The LE does in fact make a facility available for executing what is in
efff
PL/I was robbed of FIXEDOVERFLOW for binary fixed values. It is still
available for PL/I decimal fixed, i.e., packed decimal values.
The LE does in fact make a facility available for executing what is in
efffect an arbitrary SPM instruction; but it is documented so
poorly---It has been all but h
On 2013-10-21 11:06, John Gilmore wrote:
>
> [signum] is available as a BIF called sign in PL/I, where it is [almost
> always]
> implemented in line. An analogous function is available for strings
> in C, where it is implemented as a library subroutine. It has always
> been available in FORTRAN
On 2013-10-21 14:35, Gainsford, Allen wrote:
>> It is known, was indeed emphasized by Backus, is that he was much
>> concerned not to deprive 704 assembly-language programmers of
>> facilities they prized. His situation was very different from
>> ours today. He wanted to open up programming to ot
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
> It is known, was indeed emphasized by Backus, is that he was much
> concerned not to deprive 704 assembly-language programmers of
> facilities they prized. His situation was very different from
> ours today. He wanted to open up programming to others, but he
> crucially needed to convince 704 a
John McCarthy, who for a time used CAS---as well as CAR and CADDR,
which survived---in LISP, thought that the instruction came first,
i.e., that the instruction was the model for the arithmetic-IF
statement. It is my guess that he was right, but it may now be too
late to resolve this particular ch
On 10/21/2013 1:06 PM, John Gilmore wrote:
It has always
been available in FORTRAN in the form of the much deprecated but in
fact enormously useful arithmetic-IF statement
Which brings up the question of whether the trinary compare results
(e.g., CAS [C
:29 PM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: Linear search vs binary
On 21 October 2013 13:34, Alan Atkinson wrote:
>
> MHRF,ISKEYLN4
>
Hi Alan,
Thanks for the code sample. I wasn't sure what value that ISKEYLN4 half word
should hold.
I found a really neat
On 21 October 2013 13:34, Alan Atkinson wrote:
>
> MHRF,ISKEYLN4
>
Hi Alan,
Thanks for the code sample. I wasn't sure what value that ISKEYLN4 half
word should hold.
I found a really neat macro as part of IMS (member IMSORT in IMS.SDFSMAC)
which means I can easily build a static t
The arithmetic function that mathematicians call signum, viz., for an
arithmetic expression x
signum(x) = -1, a < 0,
signum(x) = 0, a = 0,
signum(x) = +1, a > 0
is available as a BIF called sign in PL/I, where it is [almost always]
implemented in line. An analogous function is available for st
> - Original Message -
>
> From: "Dougie Lawson"
> To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
> Sent: Monday, October 21, 2013 6:32:15 AM
> Subject: Linear search vs binary
>
> If I have a table of 3,500 entries of twelve bytes (I'm doing a compare of
>
words, ID. [1[
Bill Fairchild
Franklin, TN
[1] It Depends.
- Original Message -
From: "Dougie Lawson"
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Sent: Monday, October 21, 2013 6:32:15 AM
Subject: Linear search vs binary
If I have a table of 3,500 entries of twelve bytes
On 2013-10-21, at 07:13, John Gilmore wrote:
> Perhaps also worth noting explicitly is that the linear-search scheme
> done well is not significantly less complex than the binary-search
> one.
>
You've earlier advocated the value of comparison operands having
a ternary result. Of course this is a
m: IBM Mainframe Assembler List [mailto:ASSEMBLER-
:>: l...@listserv.uga.edu] On Behalf Of Dougie Lawson
:>: Sent: Monday, October 21, 2013 4:32 AM
:>: To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
:>: Subject: Linear search vs binary
:>:
:>: If I have a table of 3,500 entries of twelve by
Perhaps also worth noting explicitly is that the linear-search scheme
done well is not significantly less complex than the binary-search
one.
John Gilmore, Ashland, MA 01721 - USA
For match-seeking binary search Knuth's classical figure of merit for
an ordered table of n elements is
M(n) = 2[(n + 1)q + 2e] – n
in which q = floor[log2(n + 1)] and e = n - (2**q - 1).
Here q = 11, e = 3500 - 2047 = 1453, and thus
M(3500) = 2[3501 x 11 + 2 x 1453] - 3500 = 78324
For linear
LIST@LISTSERV.UGA.EDU] On
Behalf Of Alan Atkinson
Sent: Monday, October 21, 2013 8:35 AM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: Linear search vs binary
Leaving aside hashing and suchlike, we've used this for a while in multiple
places.
It's a ripoff of the C binsrch algorithm in
Guys- doesn't that depend - a lot - on how often the code is actually executed?
A couple billion times a day makes it a no-brainer to do a binary search, a
couple thousand times per day, perhaps just the opposite.
Paul
Typos courtesy of my iPhone and my fat fingers!
> On Oct 21, 2013, at 7:38
CH'0'
*
BSMTCH CLC 0(0,R4),0(RF) COMPARE REQUESTED KEY WITH RECORD
*
BSXITSTRF,FULL
-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU] On
Behalf Of Rob van der Heij
Sent: Monday, October 21, 2013 7
As Rob has already said- YES it is worth it
I say that too- worth it- here is my point.
assumptions:
1.) every instr is one unit (yes I know this is pretty simple but ...)
2.) random access pattern
so here we go
a simple search is n instructions-
a binary search is +x instructions
for a
I would use a hash table. It's much faster.
John
-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@listserv.uga.edu] On
Behalf Of Dougie Lawson
Sent: Monday, October 21, 2013 7:32 AM
To: ASSEMBLER-LIST@listserv.uga.edu
Subject: Linear search vs binary
If you want to make it 4096 entries, you could step through the table with
binary search very cheap by shifting a mask on each pass. I would already
think about it with 35 entries... ;-)
On 21 October 2013 13:32, Dougie Lawson wrote:
> If I have a table of 3,500 entries of twelve bytes (I'm doi
If I have a table of 3,500 entries of twelve bytes (I'm doing a compare of
eight bytes to find the entry I'm looking for and a check on a half word
marker for the end of the table to avoid running off the end) then is it
worth the pain of re-writing it as a binary search.
If it is worth the pain a
76 matches
Mail list logo
