On 14 Jan 2017, at 23:32, David Adams <[email protected]> wrote:
> There's no need to use recursion. Dave Terry's code avoids it with
> iteration but you can always replace recursion with a stack. Recursion
> automatically gives you a stack for "free"
Hi David
I think you’re possibly referring here to the implementation of the binary
search itself. I was more alluding to recursive operations on data sets at the
logical level in general.
For example say I have an array which holds hierarchical data (arrCHILD,
arrPARENT). When you want to scan the array with a logical function that tests
for each element being in a particular parent group then that scan will involve
a number of comparisons which will increase with the square of the data set
size times the number of levels in the hierarchy if we use a linear lookup such
as Find in Array.
Using a binary search brings the scan time back to a near-linear growth with
the size of the data set.
A while back I implemented a “home rolled” binary search for this reason (see
below) which dropped a 20 second (recursive) operation down to under a second.
But my point was that you only really get any practical benefit from binary
searches when there’s some kind of recursive data lookup like that involved
because Find in Array is so fast anyway.
Best Regards
Peter
(P.S. I long time ago I learned the lesson to not waste too much time coding
low level stuff in 4D because 4D eventually comes along and blows all your hard
work away by building it into the language. About 6 months after I did this -
feeling quite pleased with myself LoL, sure enough it appeared in some
R-version of v15. Lesson re-learned ! All the same the linear search was simply
unworkable at the time).
******************* Binary Search on Longint Array *********************
// $1: Pointer to data array to lookup (Must be pre-sorted in ascending
order)
// $2: Pointer to index array for cross-reference
// $3: Value to find (i.e. the value who's array index is to be returned)
// $4: Pointer in which to return array index in optimiser arrays
C_POINTER($1;$2;$4;$P_ptrREFERENCE;$P_ptrINDEX;$P_ptrOptiINDEX)
C_LONGINT($0;$3;$P_ID_FIND;$P_idxMIN;$P_idxMAX;$P_idxFOUND;$P_idxMIDPOINT;$P_SIZE_ARRAY;$P_SIZE_RANGE)
C_POINTER($C_NO_POINTER)
$C_NO_POINTER:=apf_run_c_getNoPointer
$P_ptrREFERENCE:=$1
$P_ptrINDEX:=$2
$P_ID_FIND:=$3
$P_ptrOptiINDEX:=$4
$P_SIZE_ARRAY:=Size of array($P_ptrREFERENCE->)
$P_SIZE_RANGE:=$P_SIZE_ARRAY
$P_idxMIN:=1 // Take an arbitrary halfway point
$P_idxMAX:=$P_SIZE_ARRAY
$P_idxFOUND:=(-1)
While (($P_idxMAX>=$P_idxMIN) & ($P_idxFOUND<0))
$P_idxMIDPOINT:=((($P_idxMAX-$P_idxMIN)\2)+$P_idxMIN)
Case of
: ($P_ID_FIND>$P_ptrREFERENCE->{$P_idxMIDPOINT})
$P_idxMIN:=($P_idxMIDPOINT+1)
: ($P_ID_FIND<$P_ptrREFERENCE->{$P_idxMIDPOINT})
$P_idxMAX:=($P_idxMIDPOINT-1)
: ($P_ID_FIND=$P_ptrREFERENCE->{$P_idxMIDPOINT})
// We've found it
$P_idxFOUND:=$P_idxMIDPOINT
$P_idxMAX:=$P_idxMIDPOINT
$P_idxMIN:=$P_idxMIDPOINT
End case
End while
If ($P_idxFOUND>0)
$0:=$P_ptrINDEX->{$P_idxFOUND}
Else
$0:=(-1)
End if
// Return the optimiser index if required
$P_ptrOptiINDEX->:=$P_idxFOUND
**********************************************************************
4D Internet Users Group (4D iNUG)
FAQ: http://lists.4d.com/faqnug.html
Archive: http://lists.4d.com/archives.html
Options: http://lists.4d.com/mailman/options/4d_tech
Unsub: mailto:[email protected]
**********************************************************************
