Announcement

Collapse
No announcement yet.

Speed of ARRAY SCAN

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Wyman A Belts
    Guest replied
    Don,
    Thank you very much!!

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

    Leave a comment:


  • Don Dickinson
    replied
    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

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

    Leave a comment:


  • Wyman A Belts
    Guest replied
    Hi Daniel & Michael,
    What does Binary Search mean?
    Thanks,
    Wyman

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

    Leave a comment:


  • Michael Mattias
    replied
    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

    Leave a comment:


  • Lance Edmonds
    replied
    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>

    Leave a comment:


  • Daniel Corbier
    started a topic Speed of ARRAY SCAN

    Speed of ARRAY SCAN

    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
Working...
X