2
\$\begingroup\$

The task that I have to perform is to take an array of a specific length, and figure out which sub-list has the closest sum to another given number. Then, I need to print the index of that sub-array.

For anyone that doesn't understand this problem, we add up indexes of the given list and the moment their sum exceeds or is equal to the required amount of power (the second number in the second line of the input), we append it to another list and then we append the index of the number we started to count from and the index of the number we stopped adding up to a third list. Afterwards, we start from the next index. For example, in this input, if we start counting from the list index 0, we will see that if we keep adding up until index 6, the sum will be 28. We keep repeating this, but this time from the index 1, then 2, 3, 4 etc. When we finish, we will realise that the number with the closest sum to 23 are the numbers 7, 8, 9 which range from 6 to 8 and have a sum of 24. So, we print: 6 8.

And if anyone is wondering, if we end up with multiple ranges that meet the criteria, we will choose, according to the problem statement, the nearest to the entrance, the one with the lowest starting index and the lowest ending index. In our case we have looked out for it, because every time time we append the indexes sum in server_lst we append their indexes too at the same time in index_lst. So, the indexes that are printed are the first ones that have the best sum.

num_of_cases = int(input())
for case in range(num_of_cases):
    num_of_servers, c_power = map(int, input().split())
    server_lst = list(map(int, input().split()))
    server_total = []
    server_index = []
    j = 0
    total = 0
    k = 0

    def servers(lst, k):
        global total
        global j
        for i in range(k, len(lst)):
            if total < c_power:
                total += lst[i]
                j += 1
            else:
                server_total.append(total)
                j += k
                server_index.append([k, j-1])
                j = 0
                total = 0
                break

    def execute(server_lst, k):
        for i in range(len(server_lst)):
            k = i
            servers(server_lst, k)
        min_pow = min(server_total)
        winner = server_total.index(min_pow)
        mf = server_index[winner]
        print('Case #{}:'.format(case+1), *mf )

    execute(server_lst, k)

The problem that I am currently encountering is that, although it works, it takes around 10 minutes to run 10MB inputs. Is there anyway that I can improve it so it runs faster?

Here is a very simple input:

1
10 23
1 2 3 4 5 6 7 8 9 10

and the output to this is:

Case #1: 6 8

The constraints are:

  • 1 ≤ num_of_cases ≤ 20.
  • 1 ≤ servers ≤ 100 000.
  • 1 ≤ amount of power required(c_power) ≤ 1 000 000 000.
  • 1 ≤ power of every server(every index in server_lst) ≤ 1 000 000, for i = 0 … N − 1

Thanks in advance.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Please link to the page you got the programming challenge from. \$\endgroup\$
    – Peilonrayz
    Mar 10 at 11:12
  • \$\begingroup\$ of course. here is the link and here if you want to download the problem statement without going through the link first (it's the cloud server problem) \$\endgroup\$
    – geoka
    Mar 10 at 11:16
  • 2
    \$\begingroup\$ A login is required to view the problem statement. Please edit your question to directly embed the problem, instead of requiring reviewers to jump through hurdles just to understand the task. Important details like the range of inputs: what is the limit of number of servers? What is the range of individual server numerical values? You say you're looking for the closest sum to the target value, but ignore values that exceed it? That isn't the closest, then. Please clarify the problem. \$\endgroup\$
    – AJNeufeld
    Mar 10 at 22:33
  • \$\begingroup\$ Just edited the post. I dont think that i haven't explained now everything in detail but still tell me if you need any more clarifications. \$\endgroup\$
    – geoka
    Mar 11 at 19:02
1
\$\begingroup\$

Ah ha! Your example output showed the result 6 8. Using 1-based indexes (common in certain programming challenges), server_lst had in that sub-list the values [6, 7, 8] whose sum is 21, which is close to the target value of 23. I was looking at total < c_power, and thought I was looking at a bug since it would be ignoring a sub-list that totalled exactly 23 as too large.

Your "very simple input" is actually confusing, since server powers and indices are not distinct values. Similarly, the sorted order gives no clear indication of whether 0-based or 1-based indices are returned.

The lack of good comments, an inaccessible problem statement, and confusing code made it hard to tell what the code was intended to do, which made "reviewing the code" a difficult and error-prone task.

Now that I understand what is going on, let's do both: review the code and optimize it.


Code Review

Naming

Your functions and variables are a mix of understandable names (num_of_cases, and num_of_servers) and completely opaque names that don't convey any meaning (execute, and mf).

Globals

Global variables have their place. This isn't it.

The function servers returns nothing, but calls out total and j as global variables it will be reading and writing. It turns out that it is actually modifying server_total and server_index as well.

More likely that not, the total and j variables need not have been global, and could simply have been initialized to zero at the start of the function. Except that if the loop inside servers reaches the end of the loop without exceeding c_power, then j and total are not cleared, and the next call to servers will continue where they left off. Was this intentional? Some kind of wrap-around? It doesn't seem likely, since the starting point k on the next call is not the start of the list, so odds are this is actually a bug.

Unnecessary parameters and variables

    def execute(server_lst, k):
        for i in range(len(server_lst)):
            k = i
            servers(server_lst, k)

What is the point of k? Both of them.

The execute function requires a k argument, but whatever value is given will be ignored, overwritten by k = i before it is ever used.

Inside the for loop, the value of i is stored in k. Then, neither I nor k is modified inside the body of the loop, nor used outside of the loop. i == k remains true as long as both variables are in scope. Which begs the question of: why use k instead of i?

Don't define functions inside of loops

This one can really result in strange behaviour.

for _ in range(2):
    try:
        f()
    except NameError:
        print("f() didn't exist")

    def f():
        print("Hello world")

Output:

f() didn't exist
Hello world

Write for testing

If you structured your code as a function which solved the problem, and used a main guard to run the code when submitted to the programming challenge site ...


def find_minimum_power_sublist(server_powers, required_power):
    # ... implementation omitted ...
    return start, end

def main():
    num_cases = int(input())

    for case in range(1, num_cases+1):
        num_servers, required_power = map(int, input().split())
        server_powers = list(map(int, input().split()))

        start, end = find_minimum_power_sublist(server_powers, required_power)
        print('Case #{}:'.format(case), start, end)

if __name__ == '__main__':
    main()

... then you could write a test program which runs sample cases, something like:

from solution import find_minimum_power_sublist

def test(test_name, powers, required_power, expected):
    actual = find_minimum_power_sublist(powers, required_power)
    if expected == actual:
        print(test_name, "passed.")
    else:
        print(test_name, "failed!  Expected:", expected, actual)

def run_tests():
    test("1-10", [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 23, (6, 8))
    # ... more test cases here ...

if __name__ == '__main__':
    run_tests()

There are test frameworks which make testing easier. Look into pytest, unittest, and doctest. Those will get you started, but there are many others you can try.

Optimization

Partial Sums

Whenever you see a problem where you are adding up a sequence of numbers, starting and ending at different points, you should stop and ask if there is a better way.

In your example, you have the numbers 1 2 3 4 5 6 7 8 9 10, and you first start with 1, then 1+2, then 1+2+3, and so on, until you arrive at the total of 1+2+3+4+5+6+7 or 28. Then you reset and start 2, 2+3, 2+3+4, and so on until you reach 2+3+4+5+6+7 or 27. Then you reset and start at 3 and compute 3+4, 3+4+5, 3+4+5+6, 3+4+5+6+7 or 25. Then you reset and start 4, 4+5, 4+5+6, 4+5+6+7, 4+5+6+7+8 or 30.

How many times have you added 4 and 5 together? Or phrased a better way, how many times have you added 5 to a previous sum that included the four term? Only four times. Not a lot. But this is an example with only 10 servers. You could have one hundred thousand servers and a fairly high power threshold to exceed. You could be repeatedly add a specific server value to a previous total thousands of times, and since you can have thousands of individual server values, you've got an \$O(N^2)\$ algorithm.

Instead, consider a running total of the values: 1 3 6 10 15 21 28 36 45 55. We've added the server value to the previous total exactly once. From that list, you can get the sum of any sublist of servers. For instance the sum of server values from index 6 to index 8 would be the sum of server values up to index 8, 45, less the sum of server values up to index 5, 21. 45-21=24. After processing the list of N servers, doing a total of N additions, you can get the sum of any sublist with at most one subtraction!

As exciting as this sounds, this hasn't actually improved anything. Using the same steps above, algorithm would still start with 1-0, 3-0, 6-0, 10-0, 15-0, 21-0, 28-0, then reset to 3-1, 6-1, 10-1, 15-1, 21-1, 28-1, and then reset to 6-3, up to 28-3, then reset to 10-6 up to 36-6, and so on. Instead of doing one addition per loop step, we're doing one subtraction per loop step.

Why reset to the beginning?

After adding the server power values until you exceeded the requirement, why reset the sequence and walk up to the threshold again? Why not simply advance the starting point of the sublist until the threshold is no longer reached?

  • We move the end-point forward until the difference is greater than or equal to the requirement: 1-0, 3-0, 6-0, 10-0, 15-0, 21-0, 28-0.
  • Then we walk the start-point forward until we dip below the requirement: 28-1, 28-3, 28-6.
  • Then we return to walking the end-point forward until the requirement is met again: 36-6.
  • Then we return to walking the start-point forward: 36-10, 36-15.
  • Walk end-point forward: 45-15.
  • Walk start-point forward: 45-21, 45-28.
  • Walk end-point forward: 55-28.
  • Walk start-point forward: 55-36
  • Walk end-point forward: end-of-list

More concisely,

  • While the total power requirement is not satisfied,
    • walk the end-point forward
  • While the total power requirement is satisfied,
    • If total power is smaller than the smallest found so far:
      • update the smallest found so far, and memorize the start and end points.
    • walk the start-point forward

Note we're only walking the start-point and end-point forward through the list once. This is \$O(N)\$.

Running totals

You don't have to precompute and store the running totals. You could just keep two running totals as you move the starting point and ending point forward.

You don't even need two totals. Just add or subtract from a single running total. Or consider the total a surplus, and initialize it with the negative of the power requirement. When surplus >= 0, the power requirement is satisfied; when surplus < 0, the power requirement is not satisfied.

\$\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.