Alf McLaughlin said:
Thanks, Anno. I am realizing after posting with Xho that I did not
state my question precisely right, but you did deduce what I am
interested in I think. Basically, I have a list of 500 values and I
would like to take another list of values (which happens to be 80 long
at the moment, but this could be longer as well) and for each of these
80 values I would like to find which 2 of the 500 values is the next
greater value and the next lesser value.
That's exactly what binary search does, in log n time for lists of
length n.
# return the index $i, such that $a->[$i] <= $x and $x < $a->[$i+1]
# if no such index exists, return empty
sub binsearch {
my ( $x, $a) = @_;
return if $x < $a->[ 0] or $x >= $a->[ -1];
my ( $l, $h) = ( 0, $#$a + 1);
while ( $h - $l > 1 ) {
my $mid = int( ($l + $h)/2);
$a->[ $mid] <= $x ? $l : $h = $mid;
}
return $l;
}
I've been doing this (in
pseudocode, please take syntax mistakes and finer points lightly):
my @val1 = (my 80 values); my @val2 = (my 500 values);
foreach my $i (@val1) {
for (my $j = 0; $j < @val2 - 1; $j++) {
my $current = $val2[$j];
my $next = $val2[$j + 1];
if ($i > $current && $i < $next) {
#then this value is between $current and next.
}
}
}
Apparently you are already supposing that the list @val2 is sorted. Your
search time is linear in the size of @val2. Binary search will greatly
speed it up.
[rest snipped]
Anno
Ok Anno, after reading everybodys response, I finally found a place to reply.
It was a hard choice but I think your the winner here. I actually speed read
most of the posts so I may not have all the details entirely. However I did
understand the problem and the solution immediately after readin the OP' post.
For instance, I don't know for sure if the "data" array is static or it is being
added to as time goes by. I also don't know if its a singular column, as in an
array of numbers. Is it relational, an array of indexes/references/pointers?
Hey, it all means something I guess. First impressions with this entire thread
is that there is whoe'full lack of knowledge of columns and records.
But it appears trivial as some have suggested, just sort the array and do a
"binary" search as you have shown above.
Disregarding the prospect of a dynamic array, ie: adding and removing elements,
Clearly, sorting is not necessary unless its static. Binary is used for searching
that basically yeilds a logrithmic halfing. Weather the element is removed, added,
array resized, depends on the usage.
So the array could be a monolithic standalone or an index (offset) into another
array, like an array of pointers to more meaningful data such as strings and such.
This is commonly known as an index in DB terms.
A "index" array is an "indirection" array into the body of real data that lies static
in some other location. The index array is maintained in an order that represents
some logical concept such as when its data is accesed serially, will address the
static data in that logical concept. Yeah, its sorted. This allows multiple indexes
to be maintained on the same static data, and will show different views of it when
accessed serially.
Before big DB managers arrived on the scene (with sql), we did it like this (I'm sure
nothings changed).
The indexes (record views) were grown (from defaults) starting from scratch, with zero
size. As a record (common structure) was created, space was malloc'd, and the pointer
was stored into an array. The index routine of interest was called with the record
pointers index. That routine knew what field(s) to compare. It compared the field(s)
with its current list. But *NOT* linearly, a "binary" search was used as Anno shows above.
So the log-n binary search located the position in the index array and shifted things
down to "insert" the new index. Now in 'C' the *index* array is not an array. It is
a "block" of memory alloc'd with a fixed size, so the actual *index* is a pointer
malloc'd and re-alloc'd. So to shift a sequential block was as simple as a memmove.
And indexing as such: int *Xndxptr; Xndxptr[insert_loc] = index_to_static_mallocd_record;
Contracting was the same. Although nowadays its voided until a garbage collection threshold,
then contracted. And some block optimizations for expansion exist also.
Lots of blow-hard shit huh? But thats the way I did it back in the old days.
The important thing to remember is as Anno said is the "binary" search.
I've done this many times in C apps but never for Perl. The thing that realy,
realy, realy impresses me with the "binary" search is the meticulous attention needed
for *boundry conditions*. This is *not* something that can be perfected in 5 minutes.
The OP just mentioned he might want to do this in C++ so I thought I would drop in here
a simple "real" binary search, albeit custom (but they all are). The important items of
note are the *optimizations* I use, crafted over the years.
I have not had a need to do this in Perl. Hell, I'm just floored when I see linked-lists
in Perl.
gluck
robic0
// Get ptr to unit rec (cstr)
UNIT_REC * CUnitsServ::GetPtrToUnitRec(LANG_REC *pLangRec, CString sUnitName)
{
sUnitName.MakeUpper();sUnitName.TrimLeft();sUnitName.TrimRight();
if (sUnitName == _T(""))
return NULL;
if (pLangRec)
{
// New 2/11/02 - Binary search via Units Name Hash array
int width = pLangRec->vaUhash_Ary.size();
if (width <= 0)
return NULL;
int nret;
int pos = 0;
int last = width;
int cnt = 0;
int chkndx = pos;
while (1)
{
nret = pLangRec->vaUhash_Ary[pos].sUname.CompareNoCase((LPCTSTR)sUnitName);
if (nret > 0) // if pos > user name
{
last = pos;
pos = pos - width;
chkndx = pos;
}
else
if (nret < 0) // if pos < user name
{
chkndx = pos;
width = (last - pos) / 2;
pos = pos + width;
}
else // if pos == user name
{
pLangRec->vaUhash_Ary[pos].nUndx;
return &(pLangRec->vaUnits_Ary[pLangRec->vaUhash_Ary[pos].nUndx]);
}
if ((last - chkndx) < 5)
{
for (int i = chkndx; i < last; i++)
{
if (pLangRec->vaUhash_Ary
.sUname == sUnitName)
return &(pLangRec->vaUnits_Ary[pLangRec->vaUhash_Ary.nUndx]);
cnt++;
}
return NULL;
}
cnt++;
if (cnt > 200)
return NULL;
}
}
return NULL;
}