Найти максимальный выход за период переменной длины

Question

У меня есть гипотетический набор данных с 3 столбцами, в котором есть данные о месячной прибыли для набора машин виджетов. Я пытаюсь определить максимальный период прибыли в течение двухлетнего периода.

3 столбца:
name : идентификатор машины виджета (их может быть 100)
дата : месяц / год за двухлетний период
прибыль : доллары, сделанные из виджетов в этом месяце (могут быть отрицательными, если расходы превышают выручку)

Период максимальной прибыли - это одновременный набор месяцев продолжительностью не менее 3 месяцев (может охватывать все данные).

Очевидно, я мог бы грубо заставить это и просто протестировать каждую комбинацию: январь-март, январь-апрель, январь-май, февраль-апрель и т. Д., Но я ищу лучшее решение, чем создание всего этого вручную. Кажется, что данные слишком велики, чтобы их можно было переносить и превращать месяцы в столбцы, поэтому я хотел бы иметь возможность работать с набором данных в стеке, как описано.

Я бы предпочел шаг данных sas, но SQL-запрос, который работает в proc SQL, тоже подойдет (но наборы подзапросов, которые могут потребоваться, находятся за пределами моих возможностей).

Пример данных:

data max(drop=dt);
 length name dt $50;
 infile datalines delimiter=','; 
 input name $ dt profit;
 date=input(dt,mmddyy10.);
 format date mmddyy10.;
 datalines;                      
  Widget1,01/01/2011,1000
  Widget1,02/01/2011,2000
  Widget1,03/01/2011,500
  Widget2,01/01/2011,100
  Widget2,02/01/2011,200
  Widget2,03/01/2011,-50
  Widget2,04/01/2011,250
  Widget2,05/01/2011,-150
  Widget2,06/01/2011,-250
  Widget2,07/01/2011,400
  Widget2,08/01/2011,0
  Widget2,03/01/2011,-200
;

Может быть, лучше сформулировать вопрос: «Как мне найти все возможные последовательные комбинации значений?» В таком запросе я мог бы взять максимум комбинаций, где # значений> = 3.

Запрос строит каждую комбинацию последовательных строк в таблице, удаляет те, в которых меньше 3 строк, и затем возвращает максимальное значение (конечно, сгруппированное по Widget #). Я полагаю, было бы также полезно знать начальный и конечный ряд для каждой комбинации. Я пытаюсь понять, как это можно сделать в SQL-запросе (на мой взгляд, это не похоже на шаг sas)

Образец Python:
Вот пример с некоторыми составленными данными, которые я написал на Python. Это не самая эффективная вещь, но она дает тот результат, который я ищу - я просто не могу понять, как воспроизвести его в SQL или SAS:

from itertools import groupby

data = []
data.append(['Widget1','Jan',5])
data.append(['Widget1','Feb',1])
data.append(['Widget1','Mar',-2])
data.append(['Widget1','Apr',0])
data.append(['Widget1','May',-3])
data.append(['Widget1','Jun',8])
data.append(['Widget1','Jul',-2])
data.append(['Widget1','Aug',1])
data.append(['Widget2','Jan',-1])
data.append(['Widget2','Feb',1])
data.append(['Widget2','Mar',-3])
data.append(['Widget2','Apr',1])
data.append(['Widget2','May',-60])
data.append(['Widget2','Jun',9])
data.append(['Widget2','Jul',-2])
data.append(['Widget2','Aug',20])

results = []
for key, group in groupby(data, lambda g: g[0]):
    max = -999999
    for i,v in enumerate(data):
        if key <> v[0]:
            continue
        runningtotal = 0
        for j,w in enumerate(data):
            if key <> w[0]:
                continue
            if i <= j:
                runningtotal = runningtotal + w[2]
            if i+2 <= j and runningtotal > max:
                max = runningtotal
                maxstart = v[1]
                maxend = w[1]           
    results.append([key, maxstart, maxend, max])
print results

Это дает мне результат [['Widget1', 'Jan', 'Jun', 9], ['Widget2', 'Jun', 'Aug', 27]] для поддельных данных Python, которые я сделал.

Answer 1

Я думаю, что у меня есть метод работы здесь.Кажется, что сочетание перекрестного объединения процедур SQL и быстрого шага данных дает все, что я хочу (хотя, вероятно, это можно сделать в одном большом запросе SQL).Вот он на примере данных из моего примера на Python.

data one;
 length name $50;
 infile datalines delimiter=','; 
 input name $ dt profit;
 datalines;                      
  Widget1,1,5
  Widget1,2,1
  Widget1,3,-2
  Widget1,4,0
  Widget1,5,-3
  Widget1,6,8
  Widget1,7,-2
  Widget1,8,1
  Widget2,1,-1
  Widget2,2,1
  Widget2,3,-3
  Widget2,4,1
  Widget2,5,-60
  Widget2,6,9
  Widget2,7,-2
  Widget2,8,20
;

proc sql;
create table two as
  select a.name, a.dt as start, b.dt as end, b.profit
    from one as a cross join one as b
    where start <= end and a.name = b.name
  order by name, start, end;
quit;
run;

data two; set two;
  by name start;
  if first.start then sum=0;
  sum+profit;
  months = (end-start)+1;
run;

proc means noprint data=two(where=(months>=3));
  by name;
  output out=three(drop=_:) maxid(sum(start) sum(end))=start end max(sum)=;
run;

Заставить его работать с конструкциями даты вместо нумерованных месяцев будет тривиально (просто измените переменную 'months', основываясь на фактических датах).

Answer 2

Ваша основная проблема заключается в том, что вы видите комбинаторно много периодов, но вам нужно решение, которое не требует комбинаторного объема работы.

К счастью для вас, если у вас есть N месяцев, вы можете решить эту проблему за O (N ^ 2) времени с O (N) пробелом.

Хитрость в том, что вам на самом деле не нужно сохранять все значения периода; вам нужен только максимальный. Итак, давайте разберем большую проблему на более мелкие куски.

Сначала создайте два массива длины N и заполните их нулями. Теперь вы читаете в первый месяц и (если он заработал прибыль) помещаете его в первую ячейку каждой - это «лучший прогон длины 1», а также «текущий прогон длины 1». Если оно отрицательное, оставьте «best» в нуле, но все равно заполните «текущую» ячейку.

Далее вы читаете на втором месяце. Если второй месяц заработал больше прибыли, чем первый, вы заменяете первую ячейку каждого массива значением второго месяца (в противном случае просто замените «текущий», но оставьте «лучший» в покое). Затем, если первый месяц плюс второй месяц имеет положительное значение, поместите это значение во вторую ячейку каждой - это «самый длинный пробег длины 2» и «текущий пробег длины 2» - текущий цикл двух плюс самая последняя ячейка - текущий трио.

Когда вы читаете в третий месяц, вещи начинают становиться интересными. Сначала вы проверяете первую ячейку - если третий месяц больше текущего значения, замените его. Далее вы проверяете вторую ячейку. Если сложение третьего месяца и вычитание первого увеличит это значение, сделайте это. В противном случае просто поместите его в «текущий» массив, но не в «лучший» массив. Наконец, заполните третьи ячейки значением «текущий пробег длины 2» плюс третья ячейка.

Продолжайте в том же духе. Когда вы достигнете строки i, у вас будут сохранены текущие серии, имеющие длину 1..i, а также лучшие из каждой длины.

Когда вы достигнете конца массива, вы можете отбросить «текущие» значения и просто взять максимум «лучшего» массива!

Поскольку для этого требуется 1 + 2 + 3 + ... + N операций, это O (N ^ 2). Необходим только один проход через входные данные, и хранилище равно 2N, что равно O (N). Если вы хотите узнать , какой период был наиболее прибыльным, просто сохраните ячейку, с которой начинается пробег, а также сумму пробега.

Answer 3

Шаг данных (и Proc SQL) будет считывать данные последовательно, однако, чтобы имитировать некоторые функции решения массива из других языков программирования, вы можете использовать функцию LAG для просмотра предыдущих наблюдений..

Если вы сортируете свои данные по ИМЯ и ДАТА, тогда вы можете использовать оператор BY на шаге данных и иметь доступ к FIRST.и ПОСЛЕДНЕЕ.чтобы узнать, когда ИМЯ изменилось.

Как только вы разработаете алгоритм, который, очевидно, является самой сложной частью, а у меня его пока нет, вы можете ВЫХОДИТЬ каждую сумму прибыли за последовательность дат, а затем отсортировать новыйнабор данных по имени и итоговой прибыли, который должен поставить наибольшую сумму в начале группы BY (First.Name).

Возможно, это подстегнет некоторые дополнительные идеи от вас или других программистов SAS.