Fast integer array search
Tor Tveitane
I have an array of integers in ascending order (but not consequtive values).
Does anyone have a fast, simple and efficient routine to locate a specific
value in it or return false it the value doesn't exist?
Thanks for any hint
regards
Tor
Roman Krejci
I would suggest to use asembler for that
{ LongintFound searches for a longint in the longint array InArray^.
Arraylen is the number
of longints in the array }
Function LongintFound(aLongint: longint; InArray: pointer; arraylen:
longint): boolean; assembler;
asm
push edi
jecxz @@false
mov edi,edx
repnz scasd
jnz @@false { aLongint not found }
mov eax,1 { AL=TRUE }
jmp @@end { bypass @@false }
@@false:
sub eax,eax { AL=FALSE }
@@end:
pop edi
End;
--
Roman
(please remove STOPSPAM. in header)
URL: www.rksolution.cz (Delphi corner)
MAIL: IN...@rksolution.cz
Tor Tveitane wrote in message <75539d$nv...@forums.borland.com>...
Cyrille de Brebisson
If your array is realy big, you should use a dicotomie. o(ln2(n))
Function FindInTable(Value: integer; Table: Array of integer): integer;
var
b, e, m: integer;
Begin
while b<>e do
Begin
m:= (b+e) div 2;
if table[m]=Value then Begin result:= Table[m]; exit; end;
if Table[m]<Value then b:= min(m+1, e) else e:= max(e, m-1);
end;
result:= -1;
end;
if you know things on your table. like that the integers are more or less
linears, you can inprove it
Function FindInTable(Value: integer; Table: Array of integer): integer;
var
b, e, m: integer;
Begin
while b<>e do
Begin
m:= ((e-b)*(Value-table[b])) div (table[e]-table[b]) + b;
if table[m]=Value then Begin result:= Table[m]; exit; end;
if Table[m]<Value then b:= min(m+1, e) else e:= max(e, m-1);
end;
result:= -1;
end;
--
A+ Cyrille de Brebisson
Le Meilleur moment pour planter un arbre etait il y a 20 ans. Le Deuxiemme
meilleur moment est maintenant
The Best Time to plant a tree was 20 years ago. The second best moment is
now.
http://www.capway.com/brebisso
Roman Krejci wrote in message <7557mp$nv...@forums.borland.com>...
Tor Tveitane
Thanks for the tip. But my D3 compiler doesn't recognize the min() and
max() expression, and I don't fint anything relevant in the HLP file. What
am I missing??
regards again
Tor
Cyrille de Brebisson wrote in message <7558jk$nv...@forums.borland.com>...
Andreas Koch
>
> Hi again,
>
> Thanks for the tip. But my D3 compiler doesn't recognize the min() and
> max() expression, and I don't fint anything relevant in the HLP file. What
> am I missing??
you are missing (i think it was in) math.tpu , which a) has to be
included and b) is only available in professinal and C/s versions .
Roman Krejci
<367636...@rbg.informatik.tu-darmstadt.de>...
>
>you are missing (i think it was in) math.tpu
you are referring to BP pro-C/S version, I think <g>
Andreas Koch
standard , at least (causing lots of discussions) .
And the min and max functions seem to be in the math.tpu in D4 , at
least i found this at the help files so i wrote them by myself .
...
<brain on>
...
oops... you were refereing to min/max properties of arrays ?
Sorry then ...
Tor Tveitane
-----Original Message-----
From: Roman Krejci <STOPSPA...@MBOX.CESNET.CZ>
Newsgroups: borland.public.delphi.objectpascal
Date: 15. desember 1998 11:23
Subject: Re: min(), max() nor recognized
>Andreas Koch wrote in message
><367636...@rbg.informatik.tu-darmstadt.de>...
>>
>>you are missing (i think it was in) math.tpu
>
>you are referring to BP pro-C/S version, I think <g>
>
Roman,
Hi again <g>. Because my integer array was actually a TList record field I
didn't know how to use your assembler snippet. (As a newbie I know my
bounds) Anyway I have D3.02 C/S and I included the math unit but the
compiler still didn't accept the min/max functions.
Here is Cyrille's modified function modified to suit my scenario. Note that
I want returned the index to the found number, not the number itself. Any
other way to write this so D3 will compile it...?
Function FindAccNo(Value: integer; MyList: TList): integer;
var
b, e, m: integer;
Begin
while b<>e do Begin
m:= (b+e) div 2;
if PAccArray(MyList[M])^.No = Value then begin result:= M; exit; end;
if PAccArray(MyList[M])^.No < Value then b:= min(m+1, e) else e:=
max(e,m-1);
end;
result:= -1;
end;
Thanks again
Tor
Roman Krejci
>BP ? Borland Pascal ? The math.tpu is missing in Delpi2 and Delphi4
>standard , at least (causing lots of discussions) .
>
>And the min and max functions seem to be in the math.tpu in D4 , at
>least i found this at the help files so i wrote them by myself .
>...
><brain on>
>...
>oops... you were refereing to min/max properties of arrays ?
>Sorry then ...
<brain off>
... no, I was only referring to TPU extension. No TPU's are
(as far as I know) generated by any D version. I bet you meant DCU,
sorry not to make it clearer from the start <SG>
Roman Krejci
The assembler I presented assumed true array of longint.
If tList is used (I assume the List is sorted), the binary search
suggested by Cyrille is the method of choice. If you cannot bind to
library Min/Max functions, you can write them yourself!. As an alternative
(principially the same approch is used) a more generic
routine is presented below that, given the List and TListSortCompare func
used for sorting
the list, will search for the item that would Compare to "p" in the
sorted list (the good old BP tCollection had this method!)
Function returns true if the item comparing to p is found - in this case
Var Index returns item's position. If the item is not found,
function returns false - in this case Var Index returns position where
p would be placed if added to the list.
function ListSearch(List: tList; Compare: TListSortCompare; p: pointer; Var
Index: integer): Boolean;
var
L, H, I, C: Integer;
Itm: Pointer;
begin
Result := False;
L := 0;
H := List.Count - 1;
while L <= H do begin
I := (L + H) shr 1;
C := Compare(List.Items[I], p);
if C < 0 then L := I + 1 else begin
H := I - 1;
if C = 0 then begin
Result := True;
L := I;
end;
end;
end;
Index := L;
end;
Now your example
Function MyListCompare(p,q: PAccArray): Integer;
begin
Result := p^.No - q^.No
end;
Function FindAccNo(Value: integer; MyList: TList): integer;
var
b, e, m: integer;
AccArr: tAccArray;
Begin
AccArr.No = Value;
if not ListSearch(MyList,MyListCompare,@AccArr,Result)
then Result := - 1;
end;
--
Roman
(please remove STOPSPAM. in header)
URL: www.rksolution.cz (Delphi corner)
MAIL: IN...@rksolution.cz
Tor Tveitane wrote in message <755e9d$nv...@forums.borland.com>...
>
>-----Original Message-----
>From: Roman Krejci <STOPSPA...@MBOX.CESNET.CZ>
>Newsgroups: borland.public.delphi.objectpascal
>Date: 15. desember 1998 11:23
>Subject: Re: min(), max() nor recognized
>
>
>>Andreas Koch wrote in message
Rene Tschaggelar
The order is log2(N).
1023 items can be searched with only 10 compares.
65535 items with 16 compares.
The programming effort required is the biggest.
Rene
Volker W. Walter
>
> The quickest for a variable array is a balanced binary tree.
> The order is log2(N).
> 1023 items can be searched with only 10 compares.
> 65535 items with 16 compares.
> The programming effort required is the biggest.
>
> Rene
1. The "Binary Search" in an ordered array is the same as search
in a PERFECT balanced tree. Perfect balancing is expensive.
2 .Searchung in AVL balanced trees in worst case needs about 1.45 times
comparisons than in perfect balnced trees.
Philippe Ranger
<<
Dichotomy, but you mean binary search.
PhR
Philippe Ranger
<<
You mean that each integer is an item? Then all you need is IndexOf. See the
Help.
PhR
Philippe Ranger
<<
The Tlist is that. But, as it supplies IndexOf, this is getting academic...
Still, IndexOf is brute-force in OP. The call to your quick asm is ?
with myTlist do
if LongintFound (myKey, list, count) then itIsFound
else itIsMissing;
PhR
Roman Krejci
the trouble is that items are not integers -
items hold records that have "No" field
with integer Tor is searching for.
IndexOf will not help here.
--
Roman
Terry Hoffmann
HTH,
Terry
Tor Tveitane
Roman Krejci wrote in message <755m4o$ok...@forums.borland.com>...
.....
>
>Now your example
>
>Function MyListCompare(p,q: PAccArray): Integer;
>begin
> Result := p^.No - q^.No
>end;
>
>Function FindAccNo(Value: integer; MyList: TList): integer;
>var
> b, e, m: integer;
> AccArr: tAccArray;
>Begin
> AccArr.No = Value;
> if not ListSearch(MyList,MyListCompare,@AccArr,Result)
> then Result := - 1;
>end;
Roman,
Thanks again, this example is more general. But I have problems assigning
the AccArr variable. I use typecasting in my current solution, here is my
type for the list:
type
TAccRec = record
No : longint;
....
end;
PAccArray = ^tAccRec;
var
AccountArr : TAccRec;
AccountList : array[idAcc..idDim3] of TList;
This is what I currently use:
if PAccArray(MyList[M])^.No = Value .....
What will the correct AccArr declaration in your FindAccNo function be? The
example doesn't work.. I have <brain off> for the moment..
Regards
Tor
Roman Krejci
... as the pointer to the structure was named PAccArray,
I assumed (wrong :-( ) that the structure type is named
tAccArray (as usual naming convention would suggest),
whereas the name of the type is tAccRec. Simply change
type name "TAccArray" in the example to "tAccRec" and it should work.
Cyrille de Brebisson
>The quickest for a variable array is a balanced binary tree.
>The order is log2(N).
>1023 items can be searched with only 10 compares.
>65535 items with 16 compares.
>The programming effort required is the biggest.
It's exaclty the same complexity that my first function (Dicotomie)
The Second one is even better (if the value are quite linears), in fact, you
can find your value in less that 10 loops most of the time for 1000000
entries.
Cyrille de Brebisson
>Thanks for the tip. But my D3 compiler doesn't recognize the min() and
>max() expression, and I don't fint anything relevant in the HLP file. What
>am I missing??
They are in math.pas in delphi 9only in some version).
but you can easely reprogram them:
Function Min(i, j: integer): integer;
Begin
if i<j then
result:=i
else
result:= j;
end;
Function Max(i, j: integer): integer;
Begin
if i>j then
result:=i
else
result:= j;
end;
--
Cyrille de Brebisson
Philippe Ranger <.> wrote in message <755vfo$oj...@forums.borland.com>...
>Cyrille: >>dicotomie
>Dichotomy, but you mean binary search.
> PhR
I realy mean <French>Dichotomy</French> now, if in english you call it
binary search, it's up to you :-)