Announcement

Collapse
No announcement yet.

Speed of ARRAY SCAN

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

  • 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
    Daniel Corbier
    uCalc Fast Math Parser
    uCalc Language Builder
    sigpic

  • #2
    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>
    Lance
    mailto:[email protected]

    Comment


    • #3
      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

      Michael Mattias
      Tal Systems Inc. (retired)
      Racine WI USA
      [email protected]
      http://www.talsystems.com

      Comment


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

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

        Comment


        • #5
          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

          ------------------
          Don Dickinson
          www.greatwebdivide.com

          Comment


          • #6
            Don,
            Thank you very much!!

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

            Comment

            Working...
            X