|Perl: the Markov chain saw|
Re^3: secret code generatorby BrowserUk (Pope)
|on Dec 20, 2006 at 02:49 UTC||Need Help??|
Why bother with a function
Because it allows for code reuse:
an anonymous function
Because it allows me to run multiple independent generators:
and all those nasty indices?
Ignoring that [-1] is an index, one reason is efficiency.
Now, I realise that either there is a bug in the code (which can be fixed) or my attempt to tweak it so that it would self-terminate after producing a set number of iterations may have broken it. But, having spent an hour trying to figure out how it is meant to work, I failed. So I could not make the correction.
And that bring me to the second reason. Those "nasty indices", make for a eminently understandable algorithm. The generating statement, return [ @set[ @is ] ]; is obviously an array slice using the array of indices @is to select characters from the set. The rest of the code is a simple loop incrementing the indices in sequences, and 'rolling over', when each one reaches the number of characters in the set. This is what Limbic~Region dubbed the odometer pattern.
In your first attempt, you have
It took me nearly an hour to try and type that description, and I'm still not sure it's right. I can see no benefit in that level of complexity for any task, let alone this one. Even if it worked. And to think I get accused of posting unmaintainable code.
When I wrapped your second attempt into a sub in order to benchmark it, it produced reams of warnings. There appears to be an out-by-one error when it is run multiple times. Possible due to my attempt to make it stop after a set number of iterations? But since I (again) couldn't work out how to correct the error, attempting to trace the contents of your @stack which seems to accumulate a lot of content, all but the first element of which you discard, defeated me. Again, unwarranted complexity.
To my critique of the use of OO
Some of the benefits I've attributed to my solution--multiplicity and code reuse--could also be cited as reason for using OO in the Python solution posted by the OP, but I would like to counter them.
The class contains a constructor, 2 methods--value and next and an iterator. In order for the object state to make a transition, both the methods have to be called in sequence, which is a useless split of functionality, and is probably why it is seen as necessary to add the iterator method. But, unintuitive, the value method has to be used to get the current value before the next method is called, which means that the value method has to temporarily cache the value.
Finally, as there is no possibility of resetting the generator, it becomes a 'use once and discard' instantiation. The only instance variables it has are those used entirely for it's own internal workings. And the only methods it has, other than the instantiator, could equally effectively be combined into a single method. This makes it (IMO, but also that of others), a "useless use of OO". OO for the sake of OO. OO dogma.
So each of these objects is a single use object, with only internal use state and a single method for getting the results. That is an unusual, but accurate description of an iterator subroutine. And exactly what my solution provided. I don't have Python--I threw it away about a week after I installed it because I really disliked the significant whitespace aspect of it--so I couldn't benchmark that. Instead, I converted it verbatim to Perl and compared it against my solution. Even without going through the hoops of adding performance sapping accessor/mutator methods, it's about half the speed.
More importantly, it's considerably more complex. The individual methods are simple enough, and easy enough to construct and maintain, but the complexity lies in the recursive nature of the code and data structure with one instance methods calling those of it's nested instances. There is 'hidden' state maintained in the depth of the structure--the length of the passwords being generated--along with the current state of the overall result being maintained across those multiple, nested instances. This makes it very difficult to debug or trace. Harder even that a normal recursive function.
Imagine for instance if it was decided to limit the length of the passwords to say 8 characters so that the iterator will eventually self terminate. It becomes necessary to add a test to see how deep the chain of instances is, by chaining down the self.Outer chain until it bottoms out counting as you go. But that would also require that the depth test was only initiated from the top level instance, which is another test to be run at every iteration.
I know 'efficiency' doesn't rate too highly around here, but since to generate a list of all the passwords to a maximum of 8 characters would require 5.6e15 iterations, each microsecond saved will save 177 years on the overall task! With over 50% savings relative to the (lightweight OO) version, and 7000% compared to your first attempt, these are not insignificant savings.
Even if you ignore efficiency on the basis that no one would attempt to generate such a large number of passwords--though I see no other use for this code--(IMO), my solution wins over the others on the grounds of usability and maintainability also.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.