Fastest way to loop through each digit in a number?

Bengt Richter 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:

>Hi,
>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 = [[0],[1],[2],...[8],[9],[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]:
        foo(d)

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:
        foo(1)
        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?
>digitize?  sequence?)
>
>Some examples:
>
>n = 12345
>
>#1.
>s = str(n)
>for i in s:
>    d = int(i)
>    foo(d)
>
>#2.
>nl = map(int, str(n)) 
>for d in nl:
>    foo(d)
>
>#3.
>nl = [int(x) for x in str(n)]
>for d in nl:
>    foo(d)
>
>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.

Regards,
Bengt Richter



More information about the Python-list mailing list