python - 可変長期間の最大出力を見つける

python sql sas

一連のウィジェットマシンの月ごとの利益データを含む、3列の架空のデータセットがあります。私は、2年間の最大利益期間を把握しようとしています。

3つの列は次のとおりです。
名前:ウィジェットマシンの識別子(おそらく100個あります)
日付:2年間の月/年
利益:その月にウィジェットから作成されたドル(コストが収益を超える場合はマイナスになる可能性があります)

最大利益期間は、少なくとも3か月の同時実行セットです(すべてのデータを含めることができます)。

明らかに、私はこれをブルートフォースして、すべての組み合わせをテストすることができます。データが大きすぎて転置して数か月を列にしたくないので、説明したように積み上げデータセットを操作できるようにしたいと思います。

私はsasデータステップを好みますが、proc SQLで機能する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]]
私が作ったニセのパイソンデータのために。
答え
あなたの中心的な問題は、組み合わせで多くの期間を見ることですが、組み合わせの量の作業を必要としないソリューションが必要です。

幸いにも、Nか月ある場合は、O(N)スペースを使用してO(N ^ 2)時間でこの問題を解決できます。

秘訣は、実際にはすべての期間の値を保存する必要がないということです。必要なのは最大のものだけです。それでは、大きな問題を小さなチャンクに分解しましょう。

最初に、長さNの2つの配列を作成し、それらをゼロで埋めます。ここで、最初の1か月を読んで(利益を得た場合)それぞれの最初のセルにそれを入れます。これは「長さ1の最良の実行」であり、「長さ1の現在の実行」でもあります。負の場合は、「最高」をゼロのままにしますが、「現在の」セルをとにかく塗りつぶします。

次に2か月目に読みます。 2番目の月が最初の月よりも多くの利益を得た場合は、各配列の最初のセルを2番目の月の値に置き換えます(そうでない場合は、「現在の」セルを置き換えるだけで、「最高」はそのままにします)。次に、最初の月と2か月目の合計が正の場合、その値をそれぞれの2番目のセルに入力します。これは、「長さ2の最長ラン」と「長さ2の現在のラン」です-current-run-of-twoさらに、最新のセルは現在の3つのランです。

3か月目に読むと、物事が面白くなってきます。最初に、最初のセルを確認します。3か月目が現在そこにある値より大きい場合は、それを置き換えます。次に、2番目のセルを確認します。 3番目の月を追加して最初の月を引くと、その値が大きくなる場合は、それを実行します。それ以外の場合は、「現在の」配列に入れますが、「最良の」配列には入れません。最後に、3番目のセルに「現在の長さ2のラン」の値と3番目のセルを追加します。

このように続けてください。行iに到達すると、長さ1..iの現在の実行と、これまでの各長さの最適なものが格納されます。

配列の最後に到達したら、「現在の」値を破棄して、「最良の」配列の最大値を取得できます。

これには1 + 2 + 3 + ... + Nの演算が必要なため、O(N ^ 2)です。入力データの1回のパスのみが必要であり、ストレージは2N、つまりO(N)です。最も収益性の高い期間を知りたい場合は、実行を開始するセルと実行の合計を保存してください。
関連記事

python - Python Forループはタプルを返します-これを行うより良い方法はありますか

python - すべての接続について、別のスレッドで無期限にコンテンツを作成しますか?

python - Python 2.6をOSI PIに接続するにはどうすればよいですか?

python - pipインストールに関する問題

python - SQLAlchemy-エラーを回避する方法:UnicodeEncodeError: 'latin-1'コーデックは文字をエンコードできません

python - メールアドレスの正規表現[終了]

python - Python Twisted Deferred:説明が必要

python - Django 1.3で重複をマージする最良の方法は?

python - jccのインポート、DLLの読み込みに失敗しました

python - python、すべてのファイルをディレクトリツリーの3番目、4番目、5番目から2番目のレベルに移動します