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.
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
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.
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.
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)
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().
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-
