Article Preview
Buy Now
| Print: | |
| PDF: |
Algorithms
Searching Arrays and Lists
The Virtues of Brute Force
Issue: 4.5 (May/June 2006)
Author: Charles Yeomans
Article Description: No description available.
Article Length (in bytes): 9,104
Starting Page Number: 38
RBD Number: 4514
Resource File(s): None
Related Web Link(s):
http://www.declareSub.com
Known Limitations: None
Excerpt of article text...
Searching a list is a common task in REALbasic programming. Lists include not only arrays, but control arrays, the rows of a Listbox or MenuItem, etc. The first algorithm of choice for searching lists is sequential search, which works as follows: given a list and an object, compare each element of the array to the object and return the match index, if one is found; otherwise return -1.
Sequential search has two advantages. First, it is very simple to understand and to implement. For those looking for rules of thumb about data structures and algorithms, here is one attributed to Ken Thompson, co-creator of Unix.
"When in doubt, use brute force."
Sophisticated algorithms may or may not be faster, but they are always harder to implement and debug. The second advantage of sequential search is that, in general, it is the fastest possible algorithm.
To see why one cannot do any better, consider searching a randomly generated array of objects. Checking an element of an array for a match provides no information about the rest of the array. To do better, you need to impose more structure on the array; in particular, you could sort the array. But keep in mind that sorting an array is significantly slower than searching it, so presorting an array is usually only profitable for arrays that will be searched repeatedly.
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
