Re: Counting keys with defined or undefined elements in a hash

[antirice]

*Considers getting -- on this post...ah..*

OK. I don't know why this post strikes a nerve. I think it's just the original post. Maybe it's the feeling projected by some of the participants in this thread that this can be a very very efficient algorithm that may approach O(1)?? when in fact, it's O(n) at best. How do I know this? Quite simply, if you are presented a list without knowing anything about it prior and nothing can be deduced from any value from that list about other values contained therein, then EVERY value in the list must be checked. In short, yes you absolutely MUST iterate over the entire hash. grep does it. A for loop will do it. Maybe you can sort the values, nuh uh...that iterates over the entire hash (values, mind you...but with this option, why aren't you using grep?). Even the setup with the insertion value counter must do it (although, only once instead of repeating). The only benefit there is that you don't need to repeat a count everytime you insert values. Of course, the cost is pretty much creating your own mechanism to catch all changes to said hash.

I don't know. It seems all this week I've been running into programmers who think you can squeeze blood out of a turnip. This is the fifth time I've seen this particular topic within a week. The last time was 15 minutes ago before I opened Perl Monks to settle down from having to convert the unbelieving (Who's been working on making his item counter faster for the past 3 hours. Three hours!!! !@$%!@#$^. Three hours trying to make something faster than grep which was based upon creating an array and sorting!! And he has a deadline coming up Tuesday and he "might get it done by then"). And then I open my browser, check out seekers of perl wisdom and... *sigh*. Sorry to lash out. I just felt that someone had to say it.

If I hurt anyone's feelings, I'm truly sorry. I'm just trying to vent and be somehow reassured that someone else can see what I see :-/

antirice    
The first rule of Perl club is - use Perl
The ith rule of Perl club is - follow rule i - 1 for i > 1

[shemp]

I must agree that many people dont understand (that there exist) limitations of algorithmic efficiency. For Perl programmers, this could be particularly predominant because Perl has so many cool built-ins. Often we forget that something powerful like grep or map still is O(n) when iterating thru an array. There are many other subtle (to the uninitiated) things Perl does that are oft overlooked, such as that foreach creates an anonymous array of what is being iterated over. But, this particular one is mentioned over and over in most Perl literate.
Update: My old school perl is showing, foreach does not create a copy of the list. (thanks to jsprat for pointing this out to me)

In any case, i think that most people learn the portions of a language that are necessary to the task at hand, and later on (maybe) pick up the bits and pieces in between. We're all probably there to some extent, in fact i have been for a while now trying to figure out how to best find and fill some of the holes in my perl knowledge. (I've been programming Perl since 1994.)

Anyway, I think this would be a good discussion that may want to be moved to meditations.

Also, to again plug my tied hash solution to the problem, the tie should be only a few lines of code (50ish ?), and once programmed, the run time penalty for hash modifications should only add a few percent (like 5%) to the overall time of hash operations. I have not benchmarked this tie, as i havent written it, the estimate is from my experience from other simple ties that ended up with small performance penalties. shemp

[thelenm]

Maybe you could direct your colleague to PerlMonks that he might gain wisdom and see the error of his ways...

-- Mike

--
just,my${.02}