Re^3: A brain twister? (how to make 2 lines->1)

[MidLifeXis]

Hash lookups, if done right, are O(1) algorithms (see hash_table - thanks Ransom and possibly perldata (unverified) - thanks moritz). Since you are just looping through the list of keys (O(n)), looking up the hash table entry for that key (O(1)), and generating a string from the two values (O(1)), the order of the map should be O(n)^*.

Performance is another issue entirely, but unless you are profiling the two implementations, and the speed performance boost is appreciable and worth the additional complexity, go with the implementation that is simpler to understand.

* - assuming that I am remembering my undergrad coursework properly.

Update: used performance instead of speed since you may not be optimizing for speed, but some other metric.

[perl-diddler]

One of the reasons perl went to randomizing hashes was people were deliberately using bad hash data to create DOS's ... HASH's with the wrong data become O(n) -- slightly worse than linear search due to the overhead, but in the IDEAL case, they are O(1). That's why I ***thought*** on the average, they'd grow at ~ the square root of n, but it's largely dependent on # keys and size of hash table. When #keys ~<=~ 70% hash table size, you get near O(1)...

wikipedia says it is possible with a self-balancing hash tree (brain hurts just thinking about intermixing one of those with a hash tree...) to reduce worst case to O(log n), but its not usually worth the tradeoff in algorithmic complexity -- sorta like me trying to improve on 'map' and 1 hash lookup... ;-)