4 ms·

Why not: def digit_len(n): return len(str(n))

crummy 7y ago
That's mentioned in the article, at the bottom, under the topic "Alternative, invalid solution": > As a result, solutions using strings are disallowed on problem sets and quizzes until they are taught.
- lvncelot 7y ago
  Also as a result, even the proposed solution is wrong for certain cases, takes longer, and doesn't convey what it's achieving as elegantly as `len(str(n))`. Because the length of the string representation is - exactly - what is being asked here. I get that sometimes the simplest solution to a problem is not teaching the right stuff, but in almost all cases that is a fault in the problem, not the solution.
gnuvince 7y ago
For people who, like me, thought that this would be slower than repeated division: my crappy benchmark indicates that allocating a new string and taking its length is faster by a factor of 2–2.5x. Edit: In C, the version that loops is 15 times faster than the version that allocates a new string. Python is weird.
- kragen 7y ago
  It's a common feature of interpreters that they impose a large slowdown on whatever is done in interpreted code; Python's is about 40×, although better interpreters like GhostScript and Lua are more like 10×. It's surprising the difference isn't bigger in this case, but I can mostly confirm your results, getting 3× except for small numbers: In [1]: dl = lambda n: 1 if n < 10 else 1 + dl(n // 10) In [3]: map(dl, [0, 1, 9, 10, 99, 1000, 15432, 32, 801]) Out[3]: [1, 1, 1, 2, 2, 4, 5, 2, 3] In [4]: %timeit dl(15322) 100000 loops, best of 3: 4.64 µs per loop In [5]: %timeit len(str(15322)) 1000000 loops, best of 3: 1.41 µs per loop In [6]: %timeit dl(0) 1000000 loops, best of 3: 721 ns per loop In [7]: %timeit len(str(0)) 1000000 loops, best of 3: 1.24 µs per loop
  - kragen 7y ago
    Upon thinking about this further, I guess it's sort of obvious why this happens. dl(0) does a constant, a function invocation, a comparison, a conditional, and a return of a constant (although if you look at the bytecode you'll see a few more steps in there). len(str(0)) does a constant and two built-in function invocations, which (as it happens) involve lookups in the global namespace at runtime in case you have redefined len or str. So, basically, it's only interpreting a very small number of interpreter bytecodes either way, so the small number it has to interpret to use the builtins is comparable to the small number it has to interpret to run the recursive definition, and so the interpretive overhead is comparable (and it swamps the overhead of things like allocating a new string). This machine is kind of slow. This took 54 CPU seconds in LuaJIT: > function dl(n) if n < 10 then return 1 else return 1 + dl(n/10) end end > for i = 1, 1000*1000*100 do dl(15322) end That means that approach took 540 ns per invocation rather than Python's 4640 ns --- only about 9× slower instead of the usual 40×. Or maybe this is a case where LuaJIT isn't really coming through the way it usually does.
- ben-schaaf 7y ago
  Having done a fair amount of python, this is exactly the result I'd expect. `len`, `str` are essentially implemented in C, thus avoiding the massive interpreter overhead compared to a simple loop in python.
- StreamBright 7y ago
  Yes but performance was not part of the question. Any correct solution would do. I see this a lot that people go an extra mile trying to optimize the solution and introducing bugs along the way instead having a simple certainly correct solution and optimize it later if necessary. It is funny that the string version is faster in Python.
- soVeryTired 7y ago
  Python uses a String conversion to implement rounding, so why not? :) https://github.com/python/cpython/blob/master/Objects/floatobject.c#L965-L972 https://github.com/python/cpython/blob/master/Objects/floato...
TomGullen 7y ago
You need to minus 1 if the number is < 0

That's mentioned in the article, at the bottom, under the topic "Alternative, invalid solution": > As a result, solutions using strings are disallowed on problem sets and quizzes until they are taught.

lvncelot 7y ago
Also as a result, even the proposed solution is wrong for certain cases, takes longer, and doesn't convey what it's achieving as elegantly as `len(str(n))`. Because the length of the string representation is - exactly - what is being asked here. I get that sometimes the simplest solution to a problem is not teaching the right stuff, but in almost all cases that is a fault in the problem, not the solution.

gnuvince 7y ago

For people who, like me, thought that this would be slower than repeated division: my crappy benchmark indicates that allocating a new string and taking its length is faster by a factor of 2–2.5x. Edit: In C, the version that loops is 15 times faster than the version that allocates a new string. Python is weird.

kragen 7y ago
It's a common feature of interpreters that they impose a large slowdown on whatever is done in interpreted code; Python's is about 40×, although better interpreters like GhostScript and Lua are more like 10×. It's surprising the difference isn't bigger in this case, but I can mostly confirm your results, getting 3× except for small numbers: In [1]: dl = lambda n: 1 if n < 10 else 1 + dl(n // 10) In [3]: map(dl, [0, 1, 9, 10, 99, 1000, 15432, 32, 801]) Out[3]: [1, 1, 1, 2, 2, 4, 5, 2, 3] In [4]: %timeit dl(15322) 100000 loops, best of 3: 4.64 µs per loop In [5]: %timeit len(str(15322)) 1000000 loops, best of 3: 1.41 µs per loop In [6]: %timeit dl(0) 1000000 loops, best of 3: 721 ns per loop In [7]: %timeit len(str(0)) 1000000 loops, best of 3: 1.24 µs per loop
- kragen 7y ago
  Upon thinking about this further, I guess it's sort of obvious why this happens. dl(0) does a constant, a function invocation, a comparison, a conditional, and a return of a constant (although if you look at the bytecode you'll see a few more steps in there). len(str(0)) does a constant and two built-in function invocations, which (as it happens) involve lookups in the global namespace at runtime in case you have redefined len or str. So, basically, it's only interpreting a very small number of interpreter bytecodes either way, so the small number it has to interpret to use the builtins is comparable to the small number it has to interpret to run the recursive definition, and so the interpretive overhead is comparable (and it swamps the overhead of things like allocating a new string). This machine is kind of slow. This took 54 CPU seconds in LuaJIT: > function dl(n) if n < 10 then return 1 else return 1 + dl(n/10) end end > for i = 1, 1000*1000*100 do dl(15322) end That means that approach took 540 ns per invocation rather than Python's 4640 ns --- only about 9× slower instead of the usual 40×. Or maybe this is a case where LuaJIT isn't really coming through the way it usually does.
ben-schaaf 7y ago
Having done a fair amount of python, this is exactly the result I'd expect. `len`, `str` are essentially implemented in C, thus avoiding the massive interpreter overhead compared to a simple loop in python.
StreamBright 7y ago
Yes but performance was not part of the question. Any correct solution would do. I see this a lot that people go an extra mile trying to optimize the solution and introducing bugs along the way instead having a simple certainly correct solution and optimize it later if necessary. It is funny that the string version is faster in Python.
soVeryTired 7y ago
Python uses a String conversion to implement rounding, so why not? :) https://github.com/python/cpython/blob/master/Objects/floatobject.c#L965-L972 https://github.com/python/cpython/blob/master/Objects/floato...

TomGullen 7y ago

You need to minus 1 if the number is < 0