in reply to better way to find list members?

You are basically doing it the only decent way to do it as things currently stand. I believe there is an RFC for Perl6 to include an array equivalent to exists. Unfornutaly there is no way to find out if an item is in a list without doing a O(n) search. (For the non CS/Math folks here, O(n) means that your question will require you to look *in the worst case* at every member of the array, short-circuiting buys you a little bit of time over grep but you could still end up searching for the last element in the array)

As someone pointed out, you are better off using a hash to store your data, but I should point out that this is not always true. First off, don't shove your data into a hash just to check if one item is in it. Why? Because this first requires you to do the O(n) operation of converting an array to a hash PLUS the time of the hash look-up.* So either start with a hash, or don't bother with a hash. Hashes have their own costs: They don't retain order (Okay, you can impose an order on a hash, but that's another post) and they consume more memory (but memory is cheap)

So the long and the short of it is that if you need to know if something is in an array either use grep or write your own short-circuit version. (If your array isn't too big you will be better off using the built in grep or map rather then trying to re-invent the wheel.) And yes, your routine should do the job nicely.


Yup, This is my 500th post here at PerlMonks.org!

*Update: I should point out that the cost of the actual hash lookup is almost negligable. My point was that you were insuring a worst-case scenario if you built the hash for only one lookup. Things get exponentially better from there.

Replies are listed 'Best First'.
RE: RE: better way to find list members?
by jptxs (Curate) on Oct 17, 2000 at 03:13 UTC

    My instincts (the same ones that told me not to post this at all -- and it ends up on the front page no less! ), told me it would be a waste to shove this in a hash just to sort it.

    The whole prolem here is I will never know what the length of the array will be, which thing I will be trying to find out is in the list or which list I need to compare it to until run time. This just makes it easier. I guess I'm not the only one who think's there could be a better way to do this though -- as there has been much debate over it. I love when the monks get going on something...even when it is my lame code : )

    -- I'm a solipsist, and so is everyone else. (think about it)