perltutorial Limbic~Region Purpose On a regular basis, people want to know if a particular thing, we will call it foo, is present in an array. The problem with just directing them to perldoc -q contain is that each question usually varies enough to make a single answer unsatisfactory. The goal of this tutorial is to give enough information so that someone can choose the right solution to the problem. Is This Tutorial For You? A typical mistake is to assume that there is a built-in way of determining presence in an array like there is with a hash. A red flag should go up if you try using a string for an index as in <CODE>print "gotcha\n" if $array['foo']</CODE>. Perhaps you should be using a hash. An array gives no "meaning" between the index and the value (though the programmer might as in the case of matrices). If you are still unsure which to be using, see perldoc perldsc and perldoc perldata for more information. What Will Be Covered There are typically 5 answers to the problem of identifying if foo is present in an array. <ul> <li>Convert the array to a hash</li> <li>Use the built-in grep</li> <li>Use [cpan://List::Util]'s first</li> <li>Use the smart match operator ~~ introduced in 5.10.0 <li>IYAW (Invent Yet Another Wheel)</li> </ul> There are a handful of things to consider and each solution has pros and cons accordingly. You will need to decide for yourself which is best. Convert The Array To A Hash Depending on your requirements, this can be a very attractive solution (<CODE>print "It's in there\n" if exists $sauce{spaghetti}</CODE>). There is a list of things to consider: <ul> <li>How many items do you need to check?</li> If you are only checking a single item, this is probably not the best solution. <li>Will the array change between checks?</li> If you need to rebuild the hash each time you check because you are not sure if the array has changed, this is probably not the best solution. <li>Do you need something other than an exact match?</li> Using a hash is a bad idea for non exact matches. The one noteable exception is perhaps case insensitivity. You can force the keys to a certain case during creation and foo to the same case when searching. Even then, it is questionable with regards to this being the best solution. <li>How big is the array?</li> Duplicating data structures for the convenience of searching can get quite expensive with regards to memory consumption. You will need to determine how large a footprint is acceptable to you. <li>Do you need to know if there is more than one match?</li> Remember that hash keys must be unique so using a hash when there is a possibility of duplicates is a bad idea if you need to know how many times foo is present in the array. <li>Do you need to know foo's index?</li> Typically for memory reasons, you would build your hash like: <CODE> my %lookup = map { $_ => undef } @array; print "There it is\n" if exists $lookup{foo}; </CODE> But if you have given some meaning to the relationship to the index and the value (or perhaps you want to use splice to remove it), then you should consider using the following instead: <CODE> my %lookup = map { $array[$_] => $_ } 0 .. $#array; my $index = $lookup{foo}; </CODE> </ul> Use The Built-In grep It is fast and powerful and deserves careful consideration: <ul> <li>How many items do you need to check?</li> If you are checking many items, this is probably not the best solution because it goes through the entire list even if the match is found the first time. Keep in mind that many is subjective and since it has been optimized for efficiency, it still may be acceptable. <li>Will the array change between checks?</li> You might want to use grep if the answer is yes or you are unsure since it is not checking against a copy that might be stale. <li>Do you need something other than an exact match?</li> You might want to use grep if the answer is yes or you are unsure. Since grep can accept a block, you can easily do a case insensitive search (<CODE>grep { $_ =~ /^foo$/i } @array</CODE>) <li>How big is the array?</li> If the array is very large, you may want to consider something other than grep. Of course very large is subjective. If you are not going to be checking numerous items and you can afford to wait a few extra seconds, grep might be the perfect choice. <li>Do you need to know if there is more than one match?</li> Since grep goes through the entire list, it is an ideal candidate if the answer to this question is yes. In list context, grep will return the list of matching items. In scalar context - it will return the number of matching items. <li>Do you need to know foo's index?</li> Since grep can take a block, it is very versatile and can easily be adapted to this situation: <CODE> my @indices = grep { $array[$_] eq 'foo' } 0 .. $#array; </CODE> </ul> Use [cpan://List::Util]'s first It works very much like grep except it returns on the first match, which depending on your situation can make it a perfect solution. It is worth noting that if it does not find a match, it returns [doc://undef] which may be problematic if that's the value you are trying to match. <ul> <li>How many items do you need to check?</li> At first glance, you might say it does not matter. One issue is that the first function is not a compiled built-in like grep. A code block is dereferenced and executed for each element in the list until a match is found. A second issue is that first does not currently accept a reference as an argument so a list of aliases has to be generated. Be sure not to worry about premature optimization when the net difference in runtime is a few seconds unless it really matters. <li>Will the array change between checks?</li> Like grep, if the answer is yes or you are unsure, you should be considering first since it is not checking against a copy that might be stale. <li>Do you need something other than an exact match?</li> Like grep, if the answer is yes or you are unsure then first is a possibility since it takes a block. <li>How big is the array?</li> Again, you might say it doesn't matter at first glance since it returns on first match. The first function was built to be flexible accepting a code block that has to be dereferenced against each item in the list until a match is found. If you really need lightening speed then you might want to consider a roll-your-own version that is hard-coded. <li>Do you need to know if there is more than one match?</li> If the answer is yes, do not choose first since it is designed to return on first match. <li>Do you need to know foo's index?</li> The first function can be adapted to handle this situation just like grep. </ul> Use the smart match operator ~~ introduced in perl 5.10.0 If all you need to know is if an item is in the array or not, this may be the fastest solution. The smart match operator can do much more complicated matching, but since 5.10.0 is only a few days old this tutorial does not cover them. <ul> <li>Do you need to maintain backwards compatibility?</li> If the answer is yes, the smart match operator is not the best option. <li>Do you need anything more complicated than an exact match?</li> The smart match operator can probably handle it but you will need to [cpan://Benchmark] to determine if it is the best solution. See the latest [doc://perlsyn] for details. </ul> IYAW (Invent Yet Another Wheel) There is rarely a good reason to do this. Sanity checks such as profiling and benchmarking should be done before you spending valuable time trying to squeeze a couple of seconds off the runtime. I can only think of a couple of reasons you might want to do this: <ul> <li>You can't afford the performance hit of alias construction and repeatedly dereferencing the code block passed to first</li> <li>You need to do some transformation before checking but need to keep the original array intact</li> I freely admit that this falls out of the scope of checking the presence of an item in an array. By copying the array and then transforming it you have changed the problem. This does not stop people from asking and so I have included it here for an attempt at completeness. </ul> Update: I modified the code snippet in the "Is This Tutorial For You" section to remove exists per [rob_au]'s suggestion. It was not necessary to illustrate the point. Update 2: 2004-10-02 - [wolv] pointed out to me that the inefficiencies in [cpan://List::Util]'s first are in the pure perl version. The XS version is obviously much faster. [cpan://Benchmark] to be sure but it still loses to [doc://grep] in many situations. Update 3: 2007-12-22 - Added smart match operator section as a result of the release of perl 5.10.0. See [http://use.perl.org/~schwern/journal/35186|this] for a speed comparison.