I'm working on a problem where I am to create a stack, implement a series of operations on that stack given as an array of strings (3 variations: push x, pop, inc y x), and print out the top of the stack (or EMPTY if the stack is left empty) after each operation. Push and pop are to operate as expected, and inc is to increase the bottom y elements in the stack by x. Seems simple enough.
Additional constraints are as follows:
- 1 <= operations_cnt <= 2 * 10^5
- -10^9 <= x <= 10^9
- 1 <= y <= |z| where z is the size of the stack at the time of operation
- pop is never called on an empty stack
Here is the solution I have written:
def superStack(operations):
# create stack
stack = []
add = stack.append
# loop through operations
for x in range(operations_cnt):
start = operations[x].startswith
# if push command, append number to stack and print top of stack
if start("push"):
add(int(operations[x].split()[1]))
print(stack[-1])
# elif pop command, remove last number appended and print new top of stack or EMPTY if empty
elif start("pop"):
stack.pop()
if not stack:
print("EMPTY")
else:
print(stack[-1])
# elif inc command, increase bottom numbers accordingly and print top of stack
elif start("inc"):
params = operations[x].split()
n = int(params[1])
m = int(params[2])
for y in range(n):
stack[y] += m
print(stack[-1])
My function passes 10/14 test cases, but the last 4 are Terminated due to timeout. Unfortunately, I am only given the inputs and outputs for the first 3 test cases, so I'm at a loss for what exactly is going wrong.
How can I optimize this function to avoid a timeout?
Move redundant computation outside of loops. Those steps take cycles that add into whatever limit is being used for the timeout.
For example, there is no reason to recompute int(operations[x].split()[1] inside the for loop.
You only need to split once, and only need to convert each split element to int once.
You might want to have a look at numpy.
I'm implementing the inc function here:
import time
size=10**8
half=int(size/2)
stack = [1]*size
start_time = time.time()
for y in range(0,half):
stack[y] += 2
print("--- %s seconds ---" % (time.time() - start_time))
import numpy as np
stack = np.asarray([1]*size)
start_time = time.time()
stack[0:half] += 2
print("--- %s seconds ---" % (time.time() - start_time))
This, game me this output:
$ python3 myprog.py
--- 5.146971225738525 seconds ---
--- 0.49752235412597656 seconds ---
Please note that I'm by no means an expert in numpy, and more experienced users would possibly have a better way of writing this. My main point is that for operations on long lists and matrices, numpy is WAY faster than native python.
(Time measurement copied from https://stackoverflow.com/a/1557584/6699433 )
Here is a full blown class that you basically could just inject in your code with very little work:
import numpy as np
class Stack:
def __init__(self):
self.stack = np.arange(0)
def pop(self):
self.stack.resize(len(self.stack)-1)
def push(self, x):
self.stack.resize(len(self.stack)+1)
self.stack[-1]=x
def inc(self, y, x):
self.stack[0:y] += x
def printTop(self):
if(len(self.stack) == 0):
print("EMPTY")
else:
print(self.stack[-1])
It would look like this:
def superStack(operations):
stack = Stack()
for x in range(0,operations_cnt):
if operations[x].startswith("push"):
stack.push(int(operations[x].split()[1]))
elif operations[x].startswith("pop"):
stack.pop()
elif operations[x].startswith("inc"):
stack.inc(int(operations[x].split()[1]), int(operations[x].split()[2]))
stack.printTop()
One thing that might speed things up is utilizing the fact that the number of operations are less than 200000. Since the only operation that expands the stack is push, and this always adds just one element, the stack never needs to be bigger than this value. Note that this idea might be used together with my answer involving numpy as well.
I also changed the inc to utilize list comprehension. It is a bit faster.
class Stack:
def __init__(self):
self.stack = [0]*200000
self.size = 0
def push(self, x):
self.stack[self.size]=x
self.size+=1
def pop(self):
self.size-=1
def inc(self, y, x):
self.stack[0:y] = [e+x for e in self.stack[0:y]]
def printTop(self):
if(self.size == 0):
print("EMPTY")
else:
print(self.stack[self.size-1])
