6

私は持っている：

- 30,000 data points
- each data point is a measurement of type float
- each measurement is associated with a date
- each date has only one measurement
- no dates are without measurements
- the data comes in the form of a text file: 30,000 lines in this form:
    - YYYY-MM-DD I,F (e.g. 1977-02-08 20.74)
- measurement appearing in the source file are already sorted by date

私は欲しい：

- a time-interval T with boundaries (s,e) /* start, end */
- (s - e = 14 days) the time-interval *must* be 2 weeks
- define min as the lowest value in the interval T
- define max as the greatest value in the interval T
- the chosen T needs to have the greatest distance btwn max and min of all possible Ts
- break ties among intervals T by choosing the most recent (with the greatest s value)
- the chosen T must consider all jumps in the 14 days, not just the values @ s and e
- if the overall "variance" in the interval is great but the jump 
  |max-min| is not the greatest in absolute value, T is not the right choice,
  even if it's an "exciting" interval

私は尋ねています：

- which algorithm to employ, considering algorithms are not my specialty
- which data structure to use to keep track of the subtotals

ノート：

- an answer in pseudo code would be preferred, "prose" is fine if pressured for time
- an answer in Python would be... splendid :)

必要に応じて、「ダミー」データを生成し、提案されたアルゴリズムをテストとして実行するか、実際のデータを共有できます。

ここでは、正しいソリューションと正しいアルゴリズムを適用する方法を学ぶために、これを行うための最速の方法を知りたいということを除けば、パフォーマンスにはあまり関心がありません。

今日のコンピューターではデータセットが小さいため、最も単純な反復アルゴリズムでも正確さを「証明」できると思います。

これまでのところ、私は「14 の測定値の 14 のベクトルをトラバースして運ぶ」ことを行っています。小計を使用してこれを段階的に行う方法を教えていただければ、本当にありがたいです。

4

2 に答える 2

2

スライディング ウィンドウは、2 つのスタックを維持することで、実際にここで機能します (おそらく、これは両端キューとして実装するのが最適であるため、少し誤解を招く可能性があります)。minstackと呼ばれるスタックとスタックを保持しますmaxstack。アルゴリズムの要点は、スライドのすべてのポイントでminstack が厳密に非減少であり、maxstack が厳密に非増加である必要があることです。では、どうすればよいのでしょうか。

最初に、最初の 14 ポイントをスタックに追加します。add(point)次のように定義しましょう。

minstack に対してこれを行います。

  • ポイントが minstack の最上位要素よりも小さい間、minstack の最上位要素を削除します。
  • ポイントを minstack に追加します。

同様に、maxstack の場合:

  • 新しいポイントが maxstack の最上位要素よりも大きい場合、maxstack の最上位要素を削除します。
  • ポイントを maxstack に追加します。

上記のプロパティにより、最初の 14 要素の最小値と最大値は、minstack と maxstack の一番下の要素になるはずです。今すぐウィンドウをスライドさせます。スタックのいずれかで左のポイントがまだ「生きている」場合、それは必然的に下のポイントになることに注意する必要があります。したがって、これは簡単なはずです。それは単純です：

slide():
    add(new_point)
    if (left_point == bottom(minstack)) remove_bottom(minstack)
    if (left_point == bottom(maxstack)) remove_bottom(maxstack)

ポイントが尽きるまでこれを行います。探している間隔は、bottom(maxstack) - bottom(minstack)最大のものです。

どのポイントも minstack/maxstack に最大 1 回入り、すべてのポイントがスタックから最大 1 回出ることに注意してください。したがって、これは、目的の間隔のサイズに関係なく、各ポイントに対して最大 4 つの操作を行います。

編集: Python での実装が必要であることに気付きました。私は本当にデータを解析したくなかったので、関数は値のリストを入力として受け取り、その配列のインデックス (s,e) を出力します。

import collections

def add(x, minstack, maxstack):
    while minstack and x < minstack[-1]: minstack.pop()
    while maxstack and x > maxstack[-1]: maxstack.pop()
    minstack.append(x)
    maxstack.append(x)

def get_largest_interval(points):
    minstack = collections.deque()
    maxstack = collections.deque()

    best_diff = -1
    best_interval = None

    for index, elem in enumerate(points):
        add(elem,minstack,maxstack)
        if index >= 14:
            if minstack[0] == points[index-14]: minstack.popleft()
            if maxstack[0] == points[index-14]: maxstack.popleft()

        if index >= 13:
            this_diff = maxstack[0]-minstack[0]
            if best_diff == -1 or this_diff >= best_diff:
                best_interval = (index-13, index)
                best_diff = this_diff

    return best_interval


print get_largest_interval([0, 2, 2,2,2,2,2,2,2,2,2,2,2,2,3])
于 2012-06-15T04:33:44.020 に答える
1

私があなたを理解しているなら、あなたは次のことを持っています：

30,000の異なる順序付けられたデータ値。注文はたまたま日付によるものですが、それは関係ありません。

このセット内には、コンテンツが1つのデータポイントで始まり、その初期ポイントとそれに続く13のデータポイントを含む順序付けられたシーケンスである29,986のサブセットがあります。


非常にゆっくりと：

1）30,000個のデータポイントをサイズ30,000の配列に読み込みます。

2）サイズ29,986の配列を割り当てます。この配列を「潜在的な勝者」と呼びます。

3）サブセットで検出された最大値と最小値を一時的に保持しながら、各14ポイントのサブセットをスキャンして、PotentialWinners配列を埋めます。これらの2つの値が手元にある場合は、勝者候補内の開始点のインデックス位置に（Max-Min）を保存します。スライドウィンドウの最適化は試さないでください。下記参照。

4）勝者候補の線形スキャンを実行し、値と（重要な）それが配置されているインデックスを保存します。

ところで：勝者が1人もいない場合はどうしますか？すべてのデータポイントの値が同じである場合、すべて同じ値の29,986人の候補者が勝者になります。

5）最適化：潜在的な勝者を割り当てて埋めないでください。Current Winnerをタプル（値、インデックス）に（0、-1）として初期化します。上記のように各14ポイントのサブセットの値を計算しますが、{現在の勝者、「この現在のサブセットから取得する値」}の中でより良い値のみを保持します

。6）スライディングウィンドウ：これについては考えていませんが、スライディングウィンドウを維持することは、上記の単純な線形パスよりも手間がかかります。

理由：わかりました。最初の14ポイントの値を計算します。最小値と最大値を取得し、それらの間の間隔を取得します。ただし、次のウィンドウで使用する最小値と最大値が必要です。次に、ウィンドウを1つ上の位置にスライドさせます。左端の値はなくなりました。しかし、それは最小、最大、またはその中間でしたか？それが分だったとしましょう、そしてそれは今なくなっています。2番目に低い最小値はどれくらいですか？その情報はありません。

スライディングウィンドウを維持するには、各14データポイントのサブシーケンスを並べ替え、すべての値のインデックス位置を覚えておく必要があります。次に、スライドすると、左側にドロップアウトした値が古い最小値か古い最大値か、右側に表示された新しい値が新しい最小値か新しい最大値かがわかります。しかし、努力する価値はありません。

（この状況は、Boyer-Mooreの高速部分文字列検索アルゴリズムを少し思い出させます。詳細は覚えていませんが、入力全体を前処理し、各値が発生する場所のテーブルを保持する必要があります。しかし、これはかなり離れています。 -トピック）



お役に立てれば...

于 2012-06-15T03:55:59.147 に答える