Recosh
@Recosh
Программист студент

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

Приветствую! Сделал простенький алгоритм, который работает как надо, но жутко тормозит, если в него закинуть больше 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 для удобства
  • Вопрос задан
  • 109 просмотров
Решения вопроса 1
wataru
@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 или объектов. А алгоритм расчета предполагает последовательную обработку.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@ComodoHacker
Я не настолько силен в Питоне, чтобы понять ваш алгоритм. Но, по-моему, в ваших данных не хватает идентификатора партии. Без него не получится правильно реализовать LIFO (или FIFO). Вы ведь должны списывать с конкретных партий, и именно по той цене, по которой эта партия пришла.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы