3
\$\begingroup\$

Assume we are given \$ n \$ natural numbers, \$a_{1}, a_{2}, \dots, a_{n} \$ and we are supposed to calculate the following summation:

\$ \sum_{i = 1}^{n}\sum_{j = 1}^{n} \left\lfloor \dfrac{a_{i}}{a_{j}} \right\rfloor\$.

This is a question from a challenge and in only one test, I get time-limit exceeded error.

Can my code become faster?

Here's the question and my code is as follows:

from collections import Counter

numbers = sorted(Counter(int(i) for i in input().split()).items())

sigma = 0
for i in range(len(numbers)):
    for j in range(i, len(numbers)):
        sigma += (numbers[j][0] // numbers[i][0]) * numbers[j][1] * numbers[i][1]

print(sigma)
\$\endgroup\$
5
  • \$\begingroup\$ What's with the sorted Counter? \$\endgroup\$ Jan 18, 2021 at 15:55
  • \$\begingroup\$ @TedBrownlow I didn't understand your question...what do you mean? \$\endgroup\$ Jan 18, 2021 at 16:09
  • \$\begingroup\$ I don't understand what you're using Counter for here. numbers=[int(number) for number in input.split()] should be sufficient unless I'm missing something \$\endgroup\$ Jan 18, 2021 at 16:13
  • \$\begingroup\$ @TedBrownlow I want to count how many same elements exist. For example if you have 4 1's and 10 2's, the summation will be \$ 4 \times 10 \times 2 \$ which is much faster than summing one by one all the floors. \$\endgroup\$ Jan 18, 2021 at 16:18
  • \$\begingroup\$ Please include the link to the challenge. How large can n be? \$\endgroup\$ Jan 18, 2021 at 18:34

3 Answers 3

3
\$\begingroup\$

Your approach takes \$O(n^2)\$ time. Since n can be as large as 100,000, you'll likely need something better. Some benchmarks (inputs are the numbers 1 to n shuffled, and the table shows times in seconds):

     n | original  AJNeufeld  AJ_no_islice  Kelly_Bundy 
-------+------------------------------------------------
  1000 |   0.12       0.07          0.06         0.07   
 10000 |  11.92       7.98          7.23         0.09   
 20000 |  50.82      32.83         29.79         0.11   
100000 |      -          -             -         0.18   

I didn't run the first three solutions on n=100000, they're too slow. AJ_no_islice is the same as AJNeufeld, except with a regular slice instead of islice to demonstrate that islice is not faster but slower.

My solution in a function that takes a list of numbers and returns the result (much better for testing, and for clarity):

def solve(numbers):
    incs = [0] * 100001
    for numerator, freq in Counter(numbers).items():
        for multiple in range(numerator, 100001, numerator):
            incs[multiple] += freq
    incs = list(accumulate(incs))
    return sum(incs[denominator] for denominator in numbers)

It's similar to the sieve of Eratosthenes, though I mark multiples of all numbers, not just of primes. Runtime is O(n log n).

Consider some numerator, let's say 3. Then for every denominator 3 or higher, it contributes 1 to the total. For every denominator 6 or higher, it contributes 2 to the total. And so on. As a table:

incs = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, ...]

So if you then consider some denominator, let's say 7, you simply look up incs[7] to see that it contributes 2 to the total (with the numerator 3).

Now instead consider some other numerator, let's say 4. Its table is:

incs = [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, ...]

Together for numerators 3 and 4:

incs = [0, 0, 0, 1, 2, 2, 3, 3, 4, 5, 5, 5, 7, 7, 7, 8, 9, 9, ...]

How to efficiently compute that table? First only mark the increment spots, e.g., for denominator 3:

incs = [0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, ...]

And for denominators 3 and 4 together:

incs = [0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 2, 0, 0, 1, 1, 0, 1, 0]

And then just accumulate the prefix sums.

Full benchmark code (includes correctness checking):

from timeit import repeat
from random import choices, shuffle
from collections import Counter
from itertools import islice
from itertools import accumulate

def original(numbers):
    numbers = sorted(Counter(numbers).items())
    sigma = 0
    for i in range(len(numbers)):
        for j in range(i, len(numbers)):
            sigma += (numbers[j][0] // numbers[i][0]) * numbers[j][1] * numbers[i][1]
    return sigma

def AJNeufeld(numbers):
    numbers = sorted(Counter(numbers).items())
    sigma = sum((a_j // a_i) * a_j_count * a_i_count
                for i, (a_i, a_i_count) in enumerate(numbers)
                for a_j, a_j_count in islice(numbers, i, None))
    return sigma

def AJ_no_islice(numbers):
    numbers = sorted(Counter(numbers).items())
    sigma = sum((a_j // a_i) * a_j_count * a_i_count
                for i, (a_i, a_i_count) in enumerate(numbers)
                for a_j, a_j_count in numbers[i:])
    return sigma

def Kelly_Bundy(numbers):
    incs = [0] * 100001
    for numerator, freq in Counter(numbers).items():
        for multiple in range(numerator, 100001, numerator):
            incs[multiple] += freq
    incs = list(accumulate(incs))
    return sum(incs[denominator] for denominator in numbers)

funcs = original, AJNeufeld, AJ_no_islice, Kelly_Bundy

# Correctness
numbers = choices(range(1, 100001), k=1000)
expect = funcs[0](numbers)
for func in funcs:
    result = func(numbers)
    print(result == expect, func.__name__,)
print()

# Speed
names = [f' {func.__name__} ' for func in funcs]
print('     n |' + ''.join(names))
print('-------+' + '-' * sum(map(len, names)))
for n in 1000, 10000, 20000, 100000:
    print(f'{n:6} |', end='')
    numbers = list(range(1, n+1))
    shuffle(numbers)
    for func in funcs:
        if n <= 20000 or func is Kelly_Bundy:
            t = min(repeat(lambda: func(numbers), number=1, repeat=1))
            t = '%.2f' % t
        else:
            t = '-'
        print(f'{t:>{len(func.__name__)-1}}   ', end='')
    print()
\$\endgroup\$
4
  • \$\begingroup\$ Now the output of your function is wrong... \$\endgroup\$ Jan 19, 2021 at 14:16
  • \$\begingroup\$ @MohammadAliNematollahi I doubt that. For what input? Note that it computes the same as yours in my correctness check, which I'd expect to catch mistakes. \$\endgroup\$ Jan 19, 2021 at 14:19
  • \$\begingroup\$ Now it's correct... I think you made some edits... Thank you. It passed all the tests... I learned a lot here... \$\endgroup\$ Jan 19, 2021 at 14:22
  • \$\begingroup\$ @MohammadAliNematollahi Ok... yeah I did make some edits, but only renaming variables, not affecting the results. Oh well. \$\endgroup\$ Jan 19, 2021 at 14:24
1
\$\begingroup\$

Indexing in Python is relatively slow. If you have several thousand numbers, you are looking up number[i][0], and number[i][1] repeatedly in the j loop, despite those values being unchanged:

You should find the following reworked code to be faster:

from collections import Counter

numbers = sorted(Counter(int(i) for i in input().split()).items())

sigma = 0
for i in range(len(numbers)):
    a_i, a_i_count = numbers[i]
    for j in range(i, len(numbers)):
        sigma += (numbers[j][0] // a_i) * numbers[j][1] * a_i_count

print(sigma)

Not only is it faster, it is also clearer. It takes a lot of reasoning to determine numbers[i][0] is a count of the number of occurrences of numbers[i][0], where as the reader will have an easier time understanding a_i_count as the number of occurrences of a_i, and can even see a_i in the question text.

We can even remove the indexing of numbers[i], to speed things up slightly more:

from collections import Counter

numbers = sorted(Counter(int(i) for i in input().split()).items())

sigma = 0
for i, (a_i, a_i_count) in enumerate(numbers):
    for j in range(i, len(numbers)):
        sigma += (numbers[j][0] // a_i) * numbers[j][1] * a_i_count

print(sigma)

Can we do the same thing in the second loop? Conditionally yes:

from collections import Counter

numbers = sorted(Counter(int(i) for i in input().split()).items())

sigma = 0
for i, (a_i, a_i_count) in enumerate(numbers):
    for a_j, a_j_count in numbers[i:]:
        sigma += (a_j // a_i) * a_j_count * a_i_count

print(sigma)

It looks cleaner, but is it faster? The problem is numbers[i:], which will copy the data as it realizes the values. This copy takes time, and increases the memory footprint. What you want is just an iterator over the slice, without generating copies of the data. For that, we need to use itertools.islice:

from collections import Counter
from itertools import islice

numbers = sorted(Counter(int(i) for i in input().split()).items())

sigma = 0
for i, (a_i, a_i_count) in enumerate(numbers):
    for a_j, a_j_count in islice(numbers, i, None):
        sigma += (a_j // a_i) * a_j_count * a_i_count

print(sigma)

Lastly, we can ask Python to perform the summing for us:

from collections import Counter
from itertools import islice

numbers = sorted(Counter(int(i) for i in input().split()).items())

sigma = sum((a_j // a_i) * a_j_count * a_i_count
            for i, (a_i, a_i_count) in enumerate(numbers)
            for a_j, a_j_count in islice(numbers, i, None))

print(sigma)

Note: // has the same precedence as *, so parenthesis are unnecessary in the (a_j // a_i) * a_j_count * a_i_count expression.

\$\endgroup\$
6
  • \$\begingroup\$ Except islice(numbers, i, None) does not just iterate over the slice but over the entire list (it just doesn't pass on the first i elements to its consumer). See a benchmark where it's slower. \$\endgroup\$ Jan 18, 2021 at 18:27
  • \$\begingroup\$ Even islice(a, i) is appears to be slower than a[:i]. The extra layer of iteration does cost extra time. \$\endgroup\$ Jan 18, 2021 at 18:33
  • 1
    \$\begingroup\$ Benchmarks of your various solutions would be good. And maybe itertools.combinations_with_replacement would really be the proper tool here. \$\endgroup\$ Jan 18, 2021 at 18:40
  • \$\begingroup\$ @KellyBundy Maybe you are right. The only time-limit-exceded test hasn't been handled yet. The link of challenge has been included in my question. \$\endgroup\$ Jan 18, 2021 at 18:55
  • \$\begingroup\$ @MohammadAliNematollahi Since n can be as large as 100,000, you might need something better than quadratic time. \$\endgroup\$ Jan 18, 2021 at 19:29
0
\$\begingroup\$

Not competing with @KellyBundy's linearithmic solution, but optimizing the quadratic approach:

     n | original  AJ_no_islice  superb_rain  superb_rain_2 
-------+----------------------------------------------------
  1000 |    0.13         0.07        0.05          0.04 
 10000 |   13.65         8.02        4.66          6.15 
 20000 |   60.31        35.07       19.16         25.86 

Code for the fastest one (superb_rain):

def solve(numbers):
    sigma = 0
    counted = []
    for a_j, a_j_count in sorted(Counter(numbers).items()):
        sigma += a_j_count * sum([(a_j // a_i) * a_i_count
                                  for a_i, a_i_count in counted],
                                 a_j_count)
        counted.append((a_j, a_j_count))
    return sigma

Things that make it faster:

  • Inner iteration directly over the list counted instead of a slice or islice. An append is cheaper than those.
  • List comprehension instead of generator.
  • Taking the multiplication with a_j_count out of the sum.
  • Combine \$a_j\$ with itself not with (a_j // a_j) * a_j_count but by initializing sum with a_j_count).

My superb_rain_2 is the same, but instead of building another list, it shrinks the one from sorted. I thought it might be faster, but oddly it's significantly slower.

Benchmark code (mostly @KellyBundy's):

from timeit import repeat
from random import choices, shuffle
from collections import Counter
from itertools import islice
from itertools import accumulate

def original(numbers):
    numbers = sorted(Counter(numbers).items())
    sigma = 0
    for i in range(len(numbers)):
        for j in range(i, len(numbers)):
            sigma += (numbers[j][0] // numbers[i][0]) * numbers[j][1] * numbers[i][1]
    return sigma

def AJ_no_islice(numbers):
    numbers = sorted(Counter(numbers).items())
    sigma = sum((a_j // a_i) * a_j_count * a_i_count
                for i, (a_i, a_i_count) in enumerate(numbers)
                for a_j, a_j_count in numbers[i:])
    return sigma

def superb_rain(numbers):
    sigma = 0
    counted = []
    for a_j, a_j_count in sorted(Counter(numbers).items()):
        sigma += a_j_count * sum([(a_j // a_i) * a_i_count
                                  for a_i, a_i_count in counted],
                                 a_j_count)
        counted.append((a_j, a_j_count))
    return sigma

def superb_rain_2(numbers):
    sigma = 0
    counted = sorted(Counter(numbers).items())
    while counted:
        a_j, a_j_count = counted.pop()
        sigma += a_j_count * sum([(a_j // a_i) * a_i_count
                                  for a_i, a_i_count in counted],
                                 a_j_count)
    return sigma

funcs = original, AJ_no_islice, superb_rain, superb_rain_2

# Correctness
numbers = choices(range(1, 100001), k=1000)
expect = funcs[0](numbers)
for func in funcs:
    result = func(numbers)
    print(result == expect, func.__name__)
print()

# Speed
names = [f' {func.__name__} ' for func in funcs]
print('     n |' + ''.join(names))
print('-------+' + '-' * sum(map(len, names)))
for n in 1000, 10000, 20000:
    print(f'{n:6} |', end='')
    numbers = list(range(1, n+1))
    shuffle(numbers)
    for func in funcs:
        if n <= 200000 or func is Kelly_Bundy:
            t = min(repeat(lambda: func(numbers), number=1, repeat=1))
            t = '%.2f' % t
        else:
            t = '-'
        print(f'{t:>{len(func.__name__)}} ', end='')
    print()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.