Re: faster solution

On Mon, 6 Apr 2009 11:12:22 -0700 (PDT), kizzienova@xxxxxxxxx wrote:

Dear all,

The following piece of code (a search algorithm) has to be evaluated
for more than 5e9 times in my program. Therefore, I'd like to obtain
te fastest implementationpossible. Can anyone help me improving this
piece of code?
Thanks,
Kizzie


int search (int ascnd, int ju, int jl, double xi, double *xpp, int P)
{
int jm, j;
while (ju-jl > 1)
{ /* if we are not yet done */
jm = (ju+jl) >> 1; /* compute a midpoint */
if (xi >= xpp[jm] == ascnd) {jl = jm; /* and replace
either the lower limit */ }
else {ju = jm; /* or the upper limit, as appropriate
*/ }
} /* repeat until the test condition is satisfied. */
if (xi == xpp[1]) j = 1;

xi and xpp[1] are independent of the while loop above.

else if (xi == xpp[P]) j = P-1;

xi and xpp[P] are also independent of the while loop.

else j = jl;
return j;
}

You can avoid the while loop completely for the cases where either of
the two above if statements evaluate to true.

Try something along the lines of
int search(...){...
if (xi == xpp[1]) return 1;
if (xi == xpp[P]) return P-1;
while (...)
{your while code}
return jl;

--
Remove del for email
.

Relevant Pages

  • Re: more hand written integer pow() functions (LONG POST)
    ... > trying to avoid implementation defined behavior. ... static int ibmpow ... I tested by replacing the test loop ... And the ibmpow() version is still faster than pow_b. ...
    (comp.lang.c)
  • Re: convert int[] to byte[]
    ... How the use of a BinaryWriter will avoid the need of a loop? ... >> convert each int to a byte and then write to the stream one by one. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: faster solution
    ... > The following piece of code (a search algorithm) has to be evaluated ... > int search ... Pascal) that the array is assumed to have P *USED* entries at ... according to ascnd being 1 or 0. ...
    (comp.lang.c)
  • Re: faster solution
    ... The following piece of code (a search algorithm)  has to be evaluated ... int search ...     int jm, j; ... The discussions with Eric on improving the algorithm are ...
    (comp.lang.c)
  • faster solution
    ... The following piece of code (a search algorithm) has to be evaluated ... int search ... while (ju-jl> 1) ... either the lower limit */} ...
    (comp.lang.c)