Fastest way to loop through each digit in a number?

[Rune Strand]

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!

[Roy Smith]

In article <ss********************************@4ax.com>,
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 //.

[Paul Rubin]

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.

[Rune Strand]

Paul Rubin <http://ph****@NOSPAM.invalid> 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 ;-)

[Terry Reedy]

"Rune Strand" <rst@_nospam_.drlug.org._nospam_> wrote in message
news:ss********************************@4ax.com...

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

[Dieter Buys]

n2 = n
while n2 > 0:
d = n2 % 10
n2 /= 10
foo(d)

[Alex Martelli]

Roy Smith <ro*@panix.com> wrote:

In article <ss********************************@4ax.com>,
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

[Rune Strand]

On Mon, 6 Sep 2004 02:32:46 -0400, "Terry Reedy" <tj*****@udel.edu>
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]

;-) 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])

[Bengt Richter]

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