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

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.

--MidLifeXis

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

Replies are listed 'Best First'.
Re^4: A brain twister? (how to make 2 lines->1) by perl-diddler (Chaplain) on Jun 27, 2012 at 23:30 UTC
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... ;-)	[reply]

Replies are listed 'Best First'.

Re^4: A brain twister? (how to make 2 lines->1)
by perl-diddler (Chaplain) on Jun 27, 2012 at 23:30 UTC

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... ;-)

[reply]