Speed of ARRAY SCAN

[Daniel Corbier]

I was thinking of using ARRAY SCAN to search an array, hoping
that it would be faster than the sequential search I was doing.
However, I didn't notice much of a difference in speed. Then I
tried sorting the array to see if would be scanned faster. But
I didn't see much difference either. Does ARRAY SCAN simply do
a sequential search? If so, would it would be nice if the next
version of PB did a binary search, which would be significantly
faster. Maybe, you can also have a function to index the array,
in such a way that you could do the binary search without having
to sort the array itself.

Different subject; I've used the InputBox$() function before,
but I wanted to look up the full syntax, but I didn't see it
listed in the help file index. Also, while on the topic of help file
index, under ARRAY, there's DELETE, INSERT, SCAN, and SORT. It
would be nice if clicking on one of these items jumped directly
to the appropriate topic, instead of always going to ARRAY SORT.


------------------
Daniel Corbier
UCalc Fast Math Parser
http://www.ucalc.com

[Lance Edmonds]

INPUTBOX$ is described in the Errata thread in the FAQ forum.

Regarding ARRAY SORT, etc, in the help file: The Help file is likely to be improved significantly for the next update, and this is one of the things that is on the cards to be improved.

ARRAY SCAN must do a sequential scan - the data does not need to be in any particular order for it to work, and it will work as described in the documentation.

It is also worth pointing out that ARRAY SCAN is designed to perform matches based on an expression (not just exact matches) and that includes non-equal, greater than, less then, etc. Doing a binary search with these sorts of tests would complicate things dramatically for the unwary, in the same way that doing a binary search on unsorted data in an array would produce "undefined" results that would depend on how the data was actually stored in the array. Catch-22.

That said, I'll be sure to pass your idea for a binary search feature along to R&D.


------------------
Lance
PowerBASIC Support
mailto:[email protected][email protected]</A>

[Michael Mattias]

One other note: ARRAY SCAN (sequential) can test for "greater than" or "less than" conditions as well as equality.

A binary search can only test for equality. (That is, if you expect the correct results).

I have "binary search array" code around here somewhere. I'll see if I can dig it up.

MCM

[Wyman A Belts]

Hi Daniel & Michael,
What does Binary Search mean?
Thanks,
Wyman

------------------
[email protected]

[Don Dickinson]

Hi Wyman,

With a sequential search, every item in the list is checked.

If the list is sorted, you can do a binary search. Suppose you
were looking for a person's name in an alphabetical sort of 100 items.
If you were were to search binary, you'd check the 50th item.
If what you were looking for was less than 50, then you'd
check to 25th item (repeat). If it was greater than the
50th, you'd check next the 75th item. Each time, you cut the list
of items you have to search in half. You very quickly can find
the item you're looking for. Finding one in 100 would take at
most 7 or 8 comparisons (my math is close, but not exact) instead
of the the 100 comparisons necessary for a sequential search.

Best Regards,
Don

------------------

[Wyman A Belts]

Don,
Thank you very much!!

------------------
[email protected]