"Time Limit Exceeded" error for python file-CodePudding

I have a question about how to improve my simple Python file so that it does not exceed the time limit. My code should run in less than 2 seconds, but it takes a long time. I will be glad to know any advice about it. Code receives (n) as an integer from the user, then in n lines, I have to do the tasks. If the input is "Add" I have to add the given number and then arrange them from smallest to largest. If the input is "Ask", I have to return the asked index of added numbers.

For this input: 7 Add 10 Add 2 Ask 1 Ask 2 Add 5 Ask 2 Ask 3

I need the outputs in separate lines: 2 10 5 10

I guess the code works well for other examples, but the only problem is time ...

n = int(input())

def arrange(x):
    for j in range(len(x)):
        for i in range(len(x) - 1):
            if x[i] > x[i   1]:
                x[i], x[i   1] = x[i   1], x[i]

tasks=[]
for i in range(n):
    tasks.append(list(input().split()))

ref = []
for i in range(n):
    if tasks[i][0] == 'Add':
        ref.append(int(tasks[i][1]))
        arrange(ref)
    elif tasks[i][0] == 'Ask':
        print(ref[int(tasks[i][1]) - 1])

For given example, I get "Time Limit Exceeded" Error.

CodePudding user response：

First-off: Reimplementing list.sort will always be slower than just using it directly. If nothing else, getting rid of the arrange function and replacing the call to it with ref.sort() would improve performance (especially because Python's sorting algorithm is roughly O(n) when the input is largely sorted already, so you'll be reducing the work from the O(n**2) of your bubble-sorting arrange to roughly O(n), not just the O(n log n) of an optimized general purpose sort).

If that's not enough, note that list.sort is still theoretically O(n log n); if the list is getting large enough, that may cost more than it should. If so, take a look at the bisect module, to let you do the insertions with O(log n) lookup time (plus O(n) insertion time, but with very low constant factors) which might improve performance further.

Alternatively, if Ask operations are going to be infrequent, you might not sort at all when Adding, and only sort on demand when Ask occurs (possibly using a flag to indicate if it's already sorted so you don't call sort unnecessarily). That could make a meaningfully difference, especially if the inputs typically don't interleave Adds and Asks.

Lastly, in the realm of microoptimizations, you're needlessly wasting time on list copying and indexing you don't need to do, so stop doing it:

tasks=[]
for i in range(n):
    tasks.append(input().split())  # Removed list() call; str.split already returns a list

ref = []
for action, value in tasks:  # Don't iterate by index, iterate the raw list and unpack to useful
                             # names; it's meaningfully faster
    if action == 'Add':
        ref.append(int(value))
        ref.sort()
    elif action == 'Ask':
        print(ref[int(value) - 1])

CodePudding user response：

For me it runs in less than 0,005 seconds. Are you sure that you are measuring the right thing and you don't count in the time of giving the input for example?

python3 timer.py
Input:
7
Add 10
Add 2
Ask 1
Ask 2
Add 5
Ask 2
Ask 3
Output:
2
10
5
10
Elapsed time: 0.0033 seconds

My code:

import time

n = int(input('Input:\n'))

def arrange(x):
    for j in range(len(x)):
        for i in range(len(x) - 1):
            if x[i] > x[i   1]:
                x[i], x[i   1] = x[i   1], x[i]

tasks=[]
for i in range(n):
    tasks.append(list(input().split()))

tic = time.perf_counter()

ref = []
print('Output:')
for i in range(n):
    if tasks[i][0] == 'Add':
        ref.append(int(tasks[i][1]))
        arrange(ref)
    elif tasks[i][0] == 'Ask':
        print(ref[int(tasks[i][1]) - 1])

toc = time.perf_counter()
print(f"Elapsed time: {toc - tic:0.4f} seconds")