function that counts...
in [Python]
|
From: superpollo on 20 May 2010 10:38 Steven D'Aprano ha scritto: > On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote: > >> ... how many positive integers less than n have digits that sum up to m: >> >> In [197]: def prttn(m, n): > > Does the name "prttn" mean anything? I'm afraid I keep reading it as a > mispelling of "print n". pArtItIOn > > > [...] >> s = str(i) >> sum = 0 >> for j in range(len(s)): >> sum += int(s[j]) > > Rather than iterating over an index j = 0, 1, 2, ... and then fetching > the jth character of the string, you can iterate over the characters > directly. So the inner loop is better written: > > for c in s: > sum += int(c) d'oh! some day i will learn to speak pythonese! thanks bye
From: superpollo on 20 May 2010 10:40 Richard Thomas ha scritto: > For this kind of problem you should avoid all that stringification. I > find it best to deal with sequences of digits of a fixed length and go > from there. For example: > > def count1(m, n, cache={}): > """Number of digit sequences of length `n` summing to `m`.""" > if n < 0 or m < 0: > return 0 > elif n == 0: > return int(m == 0) > elif (m, n) in cache: > return cache[m, n] > # This is an optimisation using the combinatoric choose function. > #elif m < 10: > # result = choose(n + m - 1, n - 1) > else: > result = 0 > for digit in xrange(min(10, m + 1)): > result += count1(m - digit, n - 1) > cache[m, n] = result > return result > > Notice the caching of results. With this we can compute the required > thing quite easily: > > def count2(m, n): > """Number of numbers less than `n` whose digits sum to `m`.""" > result = 0 > digits = map(int, str(n)) > length = len(digits) > for idx, digit in enumerate(digits): > for seq_digit in xrange(digit): > seq_limit = m - seq_digit > seq_length = length - idx - 1 > result += count1(seq_limit, seq_length) > m -= digit > return result > > Essentially we move through the number left to right, choose digits > less than the digit in the number and count digit sequences to fill > the remainder. Then fix the actual digit and step forward. > > An approach like this avoids the relatively slow stringification > process and makes decent use of caching and iteration (both easy and > efficient in Python). > > In [1]: count2(25, 10000) > Out[1]: 348 > > In [2]: timeit count2(25, 10000) > 100000 loops, best of 3: 12.6 us per loop wow. impressive, thanks.
From: Peter Pearson on 20 May 2010 12:06 On Wed, 19 May 2010 21:58:04 +0200, superpollo <utente(a)esempio.net> wrote: > ... how many positive integers less than n have digits that sum up to m: If it's important for the function to execute quickly for large n, you might get a useful speedup by testing only every ninth integer, since any two integers whose digits add up to m differ by a multiple of 9. A simple application of this observation would be to test range( m % 9, n, 9 ) rather than testing range( 1, n ). I suspect that further applications of number theory would provide additional, substantial speedups, but this wanders away from the subject of Python. -- To email me, substitute nowhere->spamcop, invalid->net.
From: superpollo on 20 May 2010 12:33 Peter Pearson ha scritto: > On Wed, 19 May 2010 21:58:04 +0200, superpollo <utente(a)esempio.net> wrote: >> ... how many positive integers less than n have digits that sum up to m: > > If it's important for the function to execute quickly for large n, > you might get a useful speedup by testing only every ninth integer, > since any two integers whose digits add up to m differ by a multiple > of 9. A simple application of this observation would be to test > range( m % 9, n, 9 ) rather than testing range( 1, n ). > > I suspect that further applications of number theory would > provide additional, substantial speedups, but this wanders > away from the subject of Python. > great suggestion, thanks!
From: Grant Edwards on 20 May 2010 12:39
On 2010-05-20, superpollo <utente(a)esempio.net> wrote: > Steven D'Aprano ha scritto: >> On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote: >> >>> ... how many positive integers less than n have digits that sum up to m: >>> >>> In [197]: def prttn(m, n): >> >> Does the name "prttn" mean anything? I'm afraid I keep reading it as a >> mispelling of "print n". > > pArtItIOn One might be tempted to suggest the name "partition". This isn't Fortran-IV. ;) -- Grant Edwards grant.b.edwards Yow! I've got a COUSIN at who works in the GARMENT gmail.com DISTRICT ... |