3 ms·
I think the primes kata has a hidden lesson about where TDD doesn't work. TDD, in its modern incarnation of "red-green-refactor", leaves out essential step, wh
by dalke 12y ago
I think the primes kata has a hidden lesson about where TDD doesn't work.
TDD, in its modern incarnation of "red-green-refactor", leaves out essential step, which I call "blue". These are tests that you know are supposed to pass, but which serve to double-check the assumptions in the code. (I use coverage testing to make sure that blue tests actually run; otherwise it's possible in some languages for a test to be shadowed by another test with the same name.)
Neither the original Martin implementation nor this one spend time analyzing the code for failure cases. For example, this function takes an i64, but the only justification is 'I do indeed want the function to take 1 integer parameter'. If the input were 2^63-25 then it would take a very long time to very that it's a prime number.
In this case, but also with Martin's original case, the worst-case time is O(N):
while num != 1 {
for i in 2..num + 1 {
if num % i == 0 {
result.push(i);
num = num / i;
break;
}
}
(Also, I think there's an overflow if 'num' is at the maximum value for i64.)
The temptation should not be to assume you know what you are doing. The first step should have been to better quantify the input range. Otherwise, why choose an i64 instead of an i32 or even i8? Why not put a hard limit of, say, 1 million?
One hand-wavy answer is to say that the solution given is good enough. The problem is, this means that TDD doesn't have a mechanism for identifying and resolving ambiguities in the spec. Either they have to be identified before hand ("big design up front") or afterwards and entail possible code changes ("test-last design").
Another is to argue that no one expects prime factorization to be fast. The problem is that, well, people do expect just that. Prime factorization algorithms are well understood:
# pyecm from http://sourceforge.net/projects/pyecm/
# via http://stackoverflow.com/questions/23708035/most-efficient-way-to-find-all-factors-with-gmpy2-or-gmp
>>> import time
>>> if 1:
... t1 = time.time()
... print(list(pyecm.factors(2**63-25, False, True, 10, 1)))
... t2 = time.time()
... print(t2-t1)
...
[mpz(9223372036854775783)]
0.00698018074036
It's certainly hard to get that performance, but you should know your limitations, not ignore them.
I have reviewed a half-dozen prime kata implementations. All end up with horrible run-times. None seem aware of limitations in their code.
Then again, even Beck's original Fibonacci example, which used a recursive implementation which is slow and leads to a stack overflow, omitted any discussion about how to add tests to working code which are supposed to excersise its full range.