My Python code is slow :/

The problem I’m trying to solve: https://leetcode.com/problems/fancy-sequence/

Here’s my code:

class Fancy:

def __init__(self):
    self.lisst=[]
    
def append(self, val: int) -> None:
    self.lisst.append(val)
        
def addAll(self, inc: int) -> None:
    self.lisst= [x + inc for x in self.lisst]
          
def multAll(self, m: int) -> None:
    self.lisst= [x * m for x in self.lisst]
   
def getIndex(self, idx: int) -> int:
    if idx >= len(self.lisst):
        return -1
    else:
        return self.lisst[idx] % 1000000007

I clear 102/107 test cases- the test case I failed was pretty extensive and I exceeded the time limit. Any pointers regarding what I could do better?

Interesting…

Instead of def append..., do:

def __init__(self):
  self.lisst = []
  self.append = self.lisst.append

Additionally, you’re generating a list and discarding the old list with addAll and multAll.

Maybe it would be faster to do it in place, or maybe try using the map built-in, and mul method.

This is what I got now, answers are incorrect from the get go:
class Fancy:

def __init__(self):
    self.lisst=[]            

def append(self, val: int) -> None:
    self.lisst.append(val)
        
def addAll(self, inc: int) -> None:     
    self.lisst= list(map(self.addList,self.lisst))
         
def multAll(self, m: int) -> None:
    self.lisst= list(map( self.mulList, self.lisst))
        
def getIndex(self, idx: int) -> int:
    if idx >= len(self.lisst):
        return -1
    else:
        return self.lisst[idx] % 1000000007
    
def mulList(self, nom):
    return nom*nom

def addList(self, nom):
    return nom+nom

I don’t get what this does, how is it adding an element to the list?

For the addAll and mulAll functions would just iterate over the array and modify in place. You are creating a new array each call which will be a heavy operation.

for x in range (len (list)):
	list[x] += val
def addAll(self, inc: int) -> None:
    for x in range(len(self.lisst)):
        self.lisst[x]= self.lisst[x]+inc
          

def multAll(self, m: int) -> None:
    for x in range(len(self.lisst)):
        self.lisst[x]= self.lisst[x]*m

Tried before, still failed on time. Thought list comprehension would be quicker.

Since it sais it´s classified ashard difficulty it probably expects you to not actually touch the damn list when you addAll a bajillion times. But only add up the numbers you added together and save that and calculate the result for the individual item that you request with getIndex afterwards. If you have giant lists. Maybe this pais off in a well… measureable way.

Either way, I just don´t understand why this would be hard if you could just loop and add/mult and be done with it. There gotta be some catch to this.

Just did a quick test, was pleasantly surprised your original method was the fastest. Python must have some internal optimization for that.

1.0901215076446533
for x in range (len (lisst)):
	lisst[x] = lisst[x] + 1

0.504676342010498
lisst = [x + 1 for x in lisst]

0.8003110885620117
lisst = list (map (lambda y:y+1, lisst))

collections.deque is a bit faster than list; dunno if it would speed up enough to matter. If you want to get real freaky naughty you can compile with cython (without changing anything) for basically an automatic speed up

Doesn´t the platform compile it and run the tests though? I mean it tests time… You could just throw more CPU and ram at it otherwise. ^^

Yeah… I think actually try that instead. I don´t think you can go faster than looping and adding and loopping and multiplying, when you actually want to change the list.

But you can save two values one for multiplication and one for addition and don´t do anything to the list at all when you addAll/multAll. In the addition you just have to add the values and in the multiplication you gotta multiply both values. I believe you always add first and then mult when you get the value with the index. Though… I would have to maths this out to verify. Im pretty sure if its not quite right there is a way to do this.

It might be that Im just not seeing how you could write this code better in other ways (not much of a python dev). But still either it´s some python magic. Or it´s something similar to that.

Yes you’re right, there’s definitely some trick to this- this was seemingly too easy to be classified as hard. There are a couple of hints though-

  1. Use two arrays to save the cumulative multipliers at each time point and cumulative sums adjusted by the current multiplier.
  2. The function getIndex(idx) ask to the current value modulo 10^9+7. Use modular inverse and both arrays to calculate this value.

I have no idea what they mean but I’m determined to solve it…back to the drawing board for me.

You might be onto something- do all the multiplies and additions only on the index whose value we want to retrieve? hmmmm


class Fancy:
  def __init__(self):
    self.lisst=[]
    self.append=self.lisst.append

f = Fancy()
f.append(1)
f.append(2)

In the old days this used to skip a __dict__ lookup.
It works as long as you don’t reassign the list, or as long as you keep .append bound method pointed to the the correct append.

Another optimization from the old days could perhaps be to try using slots for lisst and append, this would make Python turn a dict lookup into an blind offset struct read, not 100% certain that modern Python doesn’t do this for methods anyway.

1 Like

I don’t think deque isn’t faster than list, it’s faster for queue operations like pop-ing/inserting from from left or right, with trade offs: it’s slower for almost every other list operations. But it’s still bulit on top of list. The cpython docstring said so
* deque: list-like container with fast appends and pops on either end

related, the collections.deque module was built from collections.ABC

I think you’re misinterpreting this part, although tbf they did a poor job at writing it. I believe what they meant by

of the sequence modulo 109 + 7

is that number is the upper bound limit of the indexing operation. As later seen in the example there’s no mod involved when calling getIndex(idx)

fancy.append(10);  // fancy sequence: [13, 17, 10]
fancy.multAll(2);  // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20

Any chance of copy pasting the test case so I can take a look? Might be better to use generator if it’s really big. Although optimized and probably still more efficient up to certain size, listcomp is essentially calling a lambda within a dynamic list that also has to keep track its growth inside the memory, since it can’t deterministically resulting list size until it is finished, unlike list().

Alright, new, faster code:

class Fancy:

def __init__(self):
    self.lisst=[]   #list where numbers are appended to        
    self.opz=[]     #list where we store the operations and numbers and from which 
                    #index we need to do those operations to

def append(self, val: int) -> None:
    self.lisst.append(val)
        
def addAll(self, inc: int) -> None:     
    self.opz.append((inc, 0, len(self.lisst)))   
         
def multAll(self, m: int) -> None:
    self.opz.append((m, 1, len(self.lisst)))

def getIndex(self, idx: int) -> int:
    
    if idx > len(self.lisst)-1:
        return -1
    else:
        temp=self.lisst[idx]        #get the number from lisst on which we do the
				                    #operations on
        
        for opzItem in self.opz:    #cycle through all potential operations
            
            opnum,opcode,starting= opzItem
            
            if starting > idx:      #if index of the number(idx) is lesser than 
                                    #the length of the lisst (starting) when the op was supposed
                                    #to be performed, we do the op on it.
                
                if opcode==0:
                    temp+=opnum
                    
                elif opcode==1:
                    temp*=opnum
                    
        return temp % 1000000007

Still fails the 103rd test (out of 107), but is decently quicker than my previous algorithms. 32ms vs 56ms of

class Fancy:

def __init__(self):
    self.lisst=[]            

def append(self, val: int) -> None:
    self.lisst.append(val)
        
def addAll(self, inc: int) -> None:     
    for x in range(len(self.lisst)):
        self.lisst[x] +=inc
         
def multAll(self, m: int) -> None:
    for x in range(len(self.lisst)):
        self.lisst[x] *=m
        
def getIndex(self, idx: int) -> int:
    if idx >= len(self.lisst):
        return -1
    else:
        return self.lisst[idx] % 1000000007

vs 44ms of the version using list comprehension (see above, post #3). The above “metrics” are on a standard testcase for the interactive leetcode shell(?)

Here is test103.txt (530.7 KB)
Kind of out of ideas, perhaps there’s a better way of doing the modulo operation?

Didn’t wanna do this but I have spent too much time on this and looked at how other other people at leetcode did it. In case anyone was interested here’s the link-

1 Like

huh, it does involves a modulo & its inverse… no wonder i never pass medium level

Couldn’t you just keep track of the operation that need to be performed instead of actually performing them, and just calculate the values in the read function? preventing unnecesary calcs from being performed ?

Edit: add explenation.

The reason this works:

  • You can only append values to the array, so you always know which values to operate on based on the current lenght
  • when you execute operations you can mark them executed (pop em of the stack), preventing double execution

How would i implement this?:

  • keep an array with the following data: operation, value, currLenght
    -Everytime a append is called, just append it directly
    -everytime addAll multAll is called add it to the array
  • when getIndex is called you execute and invalidate the stack till the requested index (or the whole stack)