Fastest way to loop through each digit in a number?

Discussion in 'Python' started by Rune Strand, Sep 6, 2004.

  1. Rune Strand

    Rune Strand Guest

    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?

    Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"

    (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!
    Rune Strand, Sep 6, 2004
    #1
    1. Advertising

  2. Rune Strand

    Roy Smith Guest

    In article <>,
    Rune Strand <rst@_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?
    >
    > Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"


    Does it matter what order you process the digits, i.e. least-significant
    first vs. most-significant first? If you can do least first, then you
    might be best off doing something straight-forward like:

    i = 12345
    while i:
    digit = i % 10
    i = i / 10
    print digit

    although, with the new-style division, I'm not sure if you want / or //.
    Roy Smith, Sep 6, 2004
    #2
    1. Advertising

  3. Rune Strand

    Paul Rubin Guest

    Rune Strand <rst@_nospam_.drlug.org._nospam_> writes:
    You could try timing something like

    while n:
    n,d = divmod(n, 10)
    foo(d)

    That processes the digits in reverse order, of course.
    Paul Rubin, Sep 6, 2004
    #3
  4. Rune Strand

    Rune Strand Guest

    Paul Rubin <http://> wrote:

    >You could try timing something like
    >
    > while n:
    > n,d = divmod(n, 10)
    > foo(d)
    >
    >That processes the digits in reverse order, of course.


    Thanks!
    It's faster! But Roy Smiths modulus (%) method is even faster. The
    order does matter, but even when appending d to a list inside the loop
    and reversing it when done, your methods are faster than my initial
    groks ;-)
    Rune Strand, Sep 6, 2004
    #4
  5. Rune Strand

    Terry Reedy Guest

    "Rune Strand" <rst@_nospam_.drlug.org._nospam_> wrote in message
    news:...
    > 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?
    >
    > Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"
    >
    > (Btw: What is the English term for this process; itemize? tokenize?
    > digitize? sequence?)
    >
    > Some examples:

    You might also look at

    zero = ord('0')

    and then ord(i)-zero in loop

    tjr
    Terry Reedy, Sep 6, 2004
    #5
  6. Rune Strand

    Dieter Buys Guest

    n2 = n
    while n2 > 0:
    d = n2 % 10
    n2 /= 10
    foo(d)
    Dieter Buys, Sep 6, 2004
    #6
  7. Roy Smith <> wrote:

    > In article <>,
    > Rune Strand <rst@_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?
    > >
    > > Eg. Make 12345 into an iterable object, like [1,2,3,4,5] or "12345"

    >
    > Does it matter what order you process the digits, i.e. least-significant
    > first vs. most-significant first? If you can do least first, then you
    > might be best off doing something straight-forward like:
    >
    > i = 12345
    > while i:
    > digit = i % 10
    > i = i / 10
    > print digit
    >
    > although, with the new-style division, I'm not sure if you want / or //.


    He'd surely want truncation, so I don't understand why he could possibly
    want / (which in new-style division means true, non-truncating
    division), it's surely gotta be //. divmod looks like it might be
    better, but from some q&d timeit.py'ing, it seems this approach is
    fastest (30% faster than divmod) if these semantics are OK (when i is 0
    you get nothing rather than a single 0...) -- map(int, str(i)) is midway
    in speed through these purely numeric approaches (with % and // vs with
    divmod).


    Alex
    Alex Martelli, Sep 6, 2004
    #7
  8. Rune Strand

    Rune Strand Guest

    On Mon, 6 Sep 2004 02:32:46 -0400, "Terry Reedy" <>
    wrote:

    > You might also look at
    >
    >zero = ord('0')
    >
    >and then ord(i)-zero in loop


    Thanks! That seems like the fastest solution.
    When looping through 1000000, I get these results:
    ord : 4.703 (Terry Reedy)
    divmod : 10.469 (Paul Rubin)
    modulo : 7.625 (Roy Smith)
    lst comp: 11.750
    map : 9.062
    str : 8.219

    The modulo and divmod methods includes list.append(d) and
    list.reverse() (list.append mapped to list_append).
    Rune Strand, Sep 6, 2004
    #8
  9. Rune Strand

    Rune Strand Guest

    ;-) Somtimes the solition is too obvious... faster than using ord()
    is to look up the value in a map:

    dictmap = {
    '0' : 0,
    '1' : 1,
    '2' : 2,
    '3' : 3,
    '4' : 4,
    '5' : 5,
    '6' : 6,
    '7' : 7,
    '8' : 8,
    '9' : 9
    }

    def each_dig_in_num(n):
    dm = dictmap #faster if local
    s = repr(n) #repr is faster than str
    for char in s:
    foo(dm[char])
    Rune Strand, Sep 6, 2004
    #9
  10. On Mon, 06 Sep 2004 04:56:54 +0200, Rune Strand <rst@_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
    Bengt Richter, Sep 6, 2004
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Fangs
    Replies:
    3
    Views:
    9,766
    darshana
    Oct 26, 2008
  2. Benjamin Joldersma
    Replies:
    4
    Views:
    470
    Steven Cheng[MSFT]
    Jan 30, 2004
  3. Chaos
    Replies:
    30
    Views:
    1,162
    Chaos
    Aug 6, 2006
  4. Steven
    Replies:
    8
    Views:
    456
    Arndt Jonasson
    Feb 3, 2006
  5. Isaac Won
    Replies:
    9
    Views:
    354
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page