Fastest way to loop through each digit in a number?
bokr at oz.net
Mon Sep 6 18:02:52 CEST 2004
On Mon, 06 Sep 2004 04:56:54 +0200, Rune Strand <rst at _nospam_.drlug.org._nospam_> wrote:
>If I have a lot of integers and want do something with each digit as
>integer, what is the fastest way to get there?
How many is "a lot" ? And what are the bounds on your integers' values? ;-)
Keep in mind that whatever you are computing, it is a mapping from imput to output,
and sometimes it pays to implement a subproblem literally as a mapping.
>Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"
E.g., if you had a bazillion numbers that were all positive and five digits max,
then your fastest mapping from number to digit sequence would probably be a precomputed
list or tuple with data like (untested):
digitseqs = [,,,...,,[1,0],[1,1],[1,2]... [1,2,3,4,5],[1,2,3,4,6], ... [9,9,9,9,9]]
and then there would be no computation of the digits in
for d in digitseqs[number]:
If your numbers are bigger, you can still use the same technique, chunkwise, e.g.,
if you know you have positive 32-bit integers, that's 0<= number <= 1073741824
if number >= 1000000000:
number -= 1000000000
low5 = number % 100000
for d in digitseqs[number//100000]: foo(d)
for d in zdigitseqs[low5]: foo(d)
(zdigitseqs are all 5-digit sequences with leading zeroes included, [[0,0,0,0,0],[0,0,0,0,1], ...])
If your numbers are unbounded, you can still do something along these lines, but
numbers have to be _huge_ before you gain more than you lose in complication.
You could wrap the above in a function like def fooit(number, foo=foofunc): ...
but calls are relatively expensive in time, so you may want to forego the nicer style.
Obviously 100k lists of lists take a fair chunk of memory, and take a little time to
pre-compute, but it may pay off if you have REALLY "a lot" of input numbers ;-)
>(Btw: What is the English term for this process; itemize? tokenize?
>n = 12345
>s = str(n)
>for i in s:
> d = int(i)
>nl = map(int, str(n))
>for d in nl:
>nl = [int(x) for x in str(n)]
>for d in nl:
>Of those, I have, a bit surprised, found that #1 is the fastest, and
>that #2 using map() is faster than #3 using list comprehension. I also
>registered that that repr(n) is about 8% faster than str(n).
>Are there faster ways? Is it possible to avoid casting types?
>Thanks for all answers!
I haven't timed the above (or even tested it), but your gains (if any ;-) will depend on
what you can assume about your input data.
More information about the Python-list