Как оптимизировать алгоритм подсчёта остатка на складе по системе LIFO (последний пришел первый ушел)?

Question

[Кирилл Петров]

Приветствую! Сделал простенький алгоритм, который работает как надо, но жутко тормозит, если в него закинуть больше 500 позиций, а планируется ещё больше.
Для простоты возьмём минимальный набор исходных данных: цена, количество, операция (приход/уход)

К примеру возьмём такую таблицу:

Код генерации Python

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
1	9.78	4	in
2	9.81	5	out
3	9.76	6	in
4	9.78	1	out
5	9.65	4	in

И вот после обработки этих данных по LIFO (последний пришел первый ушел) получаю таблицу с остатками:

Медленная функция на 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][['price', 'quantity', 'operation']].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

И всё работает хорошо, но медленно... Подскажите как оптимизировать и в идеале переписать на нативные методы Pandas или векторами. Или даже можно на другом языке, если это не будет тормозить...

P.S. Пример в google colab для удобства

Answer 1

[Wataru]

Надо сделать по нормальному, без таблиц, с использованием стека, который можно сделать просто тупо списком.

Обрабатывайте все записи в хронологическом порядке.

При приходе in, вы добавляете в стек (через append у list-а) пару (цена, количество).

При приходе out, вы берете из стека с верхушки записи, пока не наберете нужное количество и уменьшаете количество. В конце пеобразуйте список в таблицу, если надо.

Что-то вроде такого (сам не питонист, возможно придется переписать немного)

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

Но вообще, DataFrame очень медленно работет при такой последовательной обработке, поэтому я бы посоветовал вам не создавать pandas dataframe изначально, и получить ваши данные в виде списка словарей, touples или объектов. А алгоритм расчета предполагает последовательную обработку.

Answer 2

[ComodoHacker]

Я не настолько силен в Питоне, чтобы понять ваш алгоритм. Но, по-моему, в ваших данных не хватает идентификатора партии. Без него не получится правильно реализовать LIFO (или FIFO). Вы ведь должны списывать с конкретных партий, и именно по той цене, по которой эта партия пришла.

Для ускорения же стандартный подход — хранить остатки на определенные моменты, а не пересчитывать их каждый раз все заново.

Comments

[Кирилл Петров]

Благодарю за ответ. Но идентификаторов нету, всё в перемешку в данный момент. За секуду может прийти от 20 до 1000 новых позиций. И требуется в идеале расчёт в реалтайме. Способ с сохранением остатоков уже сделан...

Ну и в данном варианте всё правильно работает) Вопрос только в скорости...

[ComodoHacker]

Кирилл Петров, Если у вас есть идентификаторы партий и вы можете получить остатки по ним, то вы просто упорядочиваете их нужным образом и за один проход в цикле списываете. Должно быть быстро.

[Кирилл Петров]

ComodoHacker, к сожалению идентификаторов нет. Но если их даже сделать (придумать самому) при уходе со склада одной операцией большого количества, а партия уже закончилась, придётся брать часть из другой партии, а это дробить операцию... Не, в данной задаче, как мне кажется, это избыточная информация.

[ComodoHacker]

Кирилл Петров, В этом "дроблении" и есть смысл LIFO. Вы, похоже, задачу плохо понимаете.
Ну или я не понимаю вашу задачу. :)

В любом случае, если у вас действительно может быть 1000 операций в секунду, вам нужен человек с опытом и в теме. С помощью Хабра вы эту задачу не решите.