How to optimize the algorithm for calculating the balance in the warehouse using the LIFO system (last in, first out)?

Question

Python

Greetings! I made a simple algorithm that works as it should, but terribly slows down if more than 500 positions are thrown into it, and even more are planned.
For simplicity, let's take the minimum set of initial data: price, quantity, operation (in/out)

. For example, let's take the following table:

Python generation code

df = pd.DataFrame({'price': [9.8, 9.78, 9.81, 9.76, 9.78, 9.65,], 'quantity': [3,4,5,6,1,4], 'operation': ['in','in','out','in','out','in']})

	price	quantity	operation
0	9.80	3	in
one	9.78	4	in
2	9.81	5	out
3	9.76	6	in
4	9.78	one	out
5	9.65	4	in

And now, after processing this data by LIFO (last in, first out), I get a table with the remainders:

Slow function in Python

def getOstatokLIFO(df):
    try:
        df2 = df.copy()
        df2.loc[df2.operation == 'out', 'quantity'] = -df2.quantity
        df2['needRM'] = False

        for i in df2.index:
            row = df2.iloc[i].copy()
            if row.quantity < 0:
                k = i
                row.needRM = True
                df2.iloc[i] = row
                quantitySell = row.quantity * -1

                while quantitySell > 0:
                    k -= 1
                    if k < 0:
                        break
                    rowBack = df2.iloc[k].copy()
                    if rowBack.quantity < 0:
                        continue
                    quantitySell = rowBack.quantity - quantitySell
                    if quantitySell > 0:
                        rowBack.quantity = quantitySell
                        df2.iloc[k] = rowBack
                        break
                    elif quantitySell < 0:
                        rowBack.quantity = 0
                        rowBack.needRM = True
                        df2.iloc[k] = rowBack
                        quantitySell = quantitySell * -1
                    else:
                        rowBack.quantity = 0
                        rowBack.needRM = True
                        df2.iloc[k] = rowBack
                        break

        return df2[df2.needRM == False].copy()
    except Exception as e:
        raise e

	price	quantity	operation
0	9.80	2	in
3	9.76	5	in
5	9.65	4	in

And everything works well, but slowly ... Tell me how to optimize and, ideally, rewrite to native Pandas methods or vectors. Or even it is possible in another language, if it does not slow down ...

PS Example in google colab for convenience

Answer 1

It must be done in a normal way, without tables, using a stack, which can be made just a stupid list.
Process all entries in chronological order.
When in arrives, you add to the stack (via append on the list) a pair (price, quantity).
When an out comes, you pop off the stack from the top of the record until you hit the right amount and decrement the amount. At the end, convert the list to a table, if necessary.
Something like this (not a pythonist myself, may have to rewrite a bit)

def getOstatokLIFO(df):
  stack = [];
  for index, row in df.iterrows():
    if row.operation == "in":
      stack.append([row.price, row.quantity])
      continue
    left = row.quantity
    while left > 0:
      if left >= stack[-1][1]:
        left -= stack[-1][1]
        stack.pop()
      else:
        stack[-1][1] -= left
        left = 0
        
  return stack

But in general, DataFrame is very slow in this sequential processing, so I would advise you not to create a pandas dataframe natively, and get your data as a list of dictionaries, touples or objects. And the calculation algorithm involves sequential processing.

Answer 2

I'm not strong enough in Python to understand your algorithm. But I think your data is missing a batch id. Without it, it will not be possible to correctly implement LIFO (or FIFO). After all, you have to write off from specific parties, and precisely at the price at which this party came.
To speed up, the standard approach is to store balances for certain moments, and not recalculate them every time all over again.