Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: Identical list members are sometimes counted as different when compared to each other.

by ikegami (Patriarch)
on Jan 02, 2010 at 17:12 UTC ( #815324=note: print w/replies, xml ) Need Help??


in reply to Identical list members are sometimes counted as different when compared to each other.

The problem with your approach is that you shift all the indexes by one with your splice, but your for loop continually increments $y. You tried to address that problem with if (not $words[$y]) {next}, but that was the wrong fix. The inner loop should visit the words in the reverse order (from the end to the front) to avoid that problem.

Also, your algorithm is very inefficient. It requires the visit of N/2 words (on avergage) for each of the N words in the input list ( O(N2) ). The algorithm I posted earlier is only O(N), so it scales *much* better.

  • Comment on Re: Identical list members are sometimes counted as different when compared to each other.
  • Download Code

Replies are listed 'Best First'.
Re^2: Identical list members are sometimes counted as different when compared to each other.
by di (Acolyte) on Jan 03, 2010 at 14:19 UTC

    Thank you, thank you. What a wonderful reply! The alternative approach is instructive but the explanation of its preferability (i.e. the error of my ways :-) is even moreso. I am studying the implications, reading about hash-related functions and so on, but did not want to delay in expressing my gratitude.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://815324]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (7)
As of 2022-12-07 20:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?