There is no way to check every element in a list without looking at every element in a list. This is not a Perl problem, nor is it a problem unique to Computer Science; it's a real-world problem. Unless you look at every oyster, you won't know which ones have pearls within. Statistical analysis might gain you insight regarding the probability of finding a certain number of pearls given a certain quantity of oysters, but until you open a given oyster, you won't know if it actually contains one.
There are shortcuts for look-ups, but in order for these shortcuts to exist, a sort of index, or some form of a hashing algorithm has to be generated or applied in the first place.
The fastest average-case look-up of an element within an array will be O(n). Ok, O(n/2) would be average case if you quit after finding the first occurrence, but in Big-O notation you generally drop the constant-value multiplicative co-efficient (ie, O(2n) becomes O(n), just like O(0.5n) is usually regarded as O(n)). Creation of the array takes O(n) too.
On the other hand, hash look-ups take O(1) time, but hash creation takes O(n log n). So a hash takes a little longer than a simple array to create, and doesn't maintain "order", but does provide faster look-ups.
There are a lot of other strategies too, but they all boil down to either keeping track of something at creation time, or keeping things in order at creation time to facilitate searches later, or blindly searching an unrefined list.
You might be able to hide the complexity of looping behind subroutines such as grep or first(), but a loop is still taking place behind the scenes.
Dave
In reply to Re: searching a list
by davido
in thread searching a list
by keiusui
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |