10

バックグラウンド：

連続したタイムスタンプ付きのデータのシーケンスがあります。データ シーケンスには、データが連続していないギャップがあります。各サブシーケンスに連続したデータが含まれるように、シーケンスをシーケンスのシーケンスに分割するメソッドを作成したい (入力シーケンスをギャップで分割する)。

制約:

  • 要素が必要に応じてのみ生成されるように、戻り値は一連のシーケンスでなければなりません(リスト/配列/キャッシュは使用できません)。
  • 解は O(n^2) であってはならず、おそらく Seq.take - Seq.skip パターンを除外します ( Brian の投稿を参照) 。
  • 関数型の慣用的なアプローチにはボーナス ポイントがありますが (関数型プログラミングに習熟したいので)、必須ではありません。

メソッド署名

let groupContiguousDataPoints (timeBetweenContiguousDataPoints : TimeSpan) (dataPointsWithHoles : seq<DateTime * float>) : (seq<seq< DateTime * float >>)= ...

一見問題は些細なことに見えましたが、Seq.pairwise、IEnumerator<_>、シーケンス内包表記、yield ステートメントを使用しても、解決策はわかりません。これは、F# イディオムを組み合わせた経験がまだないためか、まだ触れていない言語構造がいくつかあるためだと確信しています。

// Test data
let numbers = {1.0..1000.0}
let baseTime = DateTime.Now
let contiguousTimeStamps = seq { for n in numbers ->baseTime.AddMinutes(n)}

let dataWithOccationalHoles = Seq.zip contiguousTimeStamps numbers |> Seq.filter (fun (dateTime, num) -> num % 77.0 <> 0.0) // Has a gap in the data every 77 items

let timeBetweenContiguousValues = (new TimeSpan(0,1,0))

dataWithOccationalHoles |> groupContiguousDataPoints timeBetweenContiguousValues |> Seq.iteri (fun i sequence -> printfn "Group %d has %d data-points: Head: %f" i (Seq.length sequence) (snd(Seq.hd sequence)))
4

8 に答える 8

3

これはあなたが望むことだと思います

dataWithOccationalHoles 
|> Seq.pairwise
|> Seq.map(fun ((time1,elem1),(time2,elem2)) -> if time2-time1 = timeBetweenContiguousValues then 0, ((time1,elem1),(time2,elem2)) else 1, ((time1,elem1),(time2,elem2)) )
|> Seq.scan(fun (indexres,(t1,e1),(t2,e2)) (index,((time1,elem1),(time2,elem2))) ->  (index+indexres,(time1,elem1),(time2,elem2))  ) (0,(baseTime,-1.0),(baseTime,-1.0))
|> Seq.map( fun (index,(time1,elem1),(time2,elem2)) -> index,(time2,elem2) )
|> Seq.filter( fun (_,(_,elem)) -> elem <> -1.0)
|> PSeq.groupBy(fst)
|> Seq.map(snd>>Seq.map(snd))

このクールな質問をしてくれてありがとう

于 2010-09-30T10:48:01.920 に答える
2

Alexey の Haskell を F# に翻訳しましたが、F# ではきれいではなく、まだ 1 つの要素が熱心すぎます。

もっと良い方法があると思いますが、後でもう一度試す必要があります。

let N = 20
let data =  // produce some arbitrary data with holes
    seq {
        for x in 1..N do
            if x % 4 <> 0 && x % 7 <> 0 then
                printfn "producing %d" x
                yield x
    }

let rec GroupBy comp (input:LazyList<'a>) : LazyList<LazyList<'a>> = 
    LazyList.delayed (fun () ->
    match input with
    | LazyList.Nil -> LazyList.cons (LazyList.empty()) (LazyList.empty())
    | LazyList.Cons(x,LazyList.Nil) -> 
        LazyList.cons (LazyList.cons x (LazyList.empty())) (LazyList.empty())
    | LazyList.Cons(x,(LazyList.Cons(y,_) as xs)) ->
        let groups = GroupBy comp xs
        if comp x y then
            LazyList.consf 
                (LazyList.consf x (fun () -> 
                    let (LazyList.Cons(firstGroup,_)) = groups
                    firstGroup)) 
                (fun () -> 
                    let (LazyList.Cons(_,otherGroups)) = groups
                    otherGroups)
        else
            LazyList.cons (LazyList.cons x (LazyList.empty())) groups)

let result = data |> LazyList.of_seq |> GroupBy (fun x y -> y = x + 1)
printfn "Consuming..."
for group in result do
    printfn "about to do a group"
    for x in group do
        printfn "  %d" x
于 2009-08-24T16:46:20.187 に答える
1

シグネチャを持つ関数が必要なようです

(`a -> bool) -> seq<'a> -> seq<seq<'a>>

つまり、関数とシーケンスの場合、関数の結果に基づいて、入力シーケンスをシーケンスのシーケンスに分割します。

値を IEnumerable を実装するコレクションにキャッシュするのが最も簡単でしょう (厳密には厳密ではありませんが、入力を複数回反復することは避けます。これにより、入力の遅延の多くが失われます)。

let groupBy (fun: 'a -> bool) (input: seq) =
  配列 {
    let cache = ref (新しい System.Collections.Generic.List())
    for e in 入力 do
      (!cache).Add(e)
      そうでない場合 (fun e) then
        利回り!キャッシュ
        キャッシュ := 新しい System.Collections.Generic.List()
    cache.Length > 0 の場合
     利回り!キャッシュ
  }

別の実装では、関数にキャッシュ コレクションを (としてseq<'a>) 渡すことができるため、ブレーク ポイントを選択するために複数の要素を確認できます。

于 2009-08-24T10:47:49.947 に答える
1

(編集: これはブライアンのソリューションと同様の問題に悩まされています。内側の各シーケンスを反復せずに外側のシーケンスを反復すると、物事がひどく台無しになります!)

シーケンス式をネストするソリューションを次に示します。ここでは、.NET の命令的な性質IEnumerable<T>がかなり明白であり、この問題に対して慣用的な F# コードを記述するのが少し難しくなっていますが、何が起こっているのかはまだ明らかであることを願っています。

let groupBy cmp (sq:seq<_>) =
  let en = sq.GetEnumerator()
  let rec partitions (first:option<_>) =
    seq {
      match first with
      | Some first' ->             //'
        (* The following value is always overwritten; 
           it represents the first element of the next subsequence to output, if any *)
        let next = ref None

        (* This function generates a subsequence to output, 
           setting next appropriately as it goes *)
        let rec iter item = 
          seq {
            yield item
            if (en.MoveNext()) then
              let curr = en.Current
              if (cmp item curr) then
                yield! iter curr
              else // consumed one too many - pass it on as the start of the next sequence
                next := Some curr
            else
              next := None
          }
        yield iter first' (* ' generate the first sequence *)
        yield! partitions !next (* recursively generate all remaining sequences *)
      | None -> () // return an empty sequence if there are no more values
    }
  let first = if en.MoveNext() then Some en.Current else None
  partitions first

let groupContiguousDataPoints (time:TimeSpan) : (seq<DateTime*_> -> _) = 
  groupBy (fun (t,_) (t',_) -> t' - t <= time)
于 2009-08-24T21:11:52.647 に答える
1

わかりました、再試行します。F# で最適な量の遅延を達成するのは少し難しいことがわかりました... 明るい面では、ref セルを使用しないという点で、これは前回の試みよりもいくらか機能的です。

let groupBy cmp (sq:seq<_>) =
  let en = sq.GetEnumerator()
  let next() = if en.MoveNext() then Some en.Current else None
  (* this function returns a pair containing the first sequence and a lazy option indicating the first element in the next sequence (if any) *)
  let rec seqStartingWith start =
    match next() with
    | Some y when cmp start y ->
        let rest_next = lazy seqStartingWith y // delay evaluation until forced - stores the rest of this sequence and the start of the next one as a pair
        seq { yield start; yield! fst (Lazy.force rest_next) }, 
          lazy Lazy.force (snd (Lazy.force rest_next))
    | next -> seq { yield start }, lazy next
  let rec iter start =
    seq {
      match (Lazy.force start) with
      | None -> ()
      | Some start -> 
          let (first,next) = seqStartingWith start
          yield first
          yield! iter next
    }
  Seq.cache (iter (lazy next()))
于 2009-08-25T23:30:30.520 に答える
1

私は F# の構文をよく知らないため、Haskell のソリューションですが、翻訳するのは簡単なはずです。

type TimeStamp = Integer -- ticks
type TimeSpan  = Integer -- difference between TimeStamps

groupContiguousDataPoints :: TimeSpan -> [(TimeStamp, a)] -> [[(TimeStamp, a)]]

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]プレリュードには次の機能があります。

グループ関数はリストを受け取り、結果の連結が引数と等しくなるようなリストのリストを返します。さらに、結果の各サブリストには等しい要素のみが含まれます。例えば、

group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]

これは groupBy の特殊なケースであり、プログラマが独自の等価性テストを提供できるようにします。

リスト内の各要素を現在のグループの最初の要素と比較し、連続した要素を比較する必要があるため、これは私たちが望んでいるものとはまったく異なります。そのような関数があればgroupBy1、簡単に書くことができgroupContiguousDataPointsます:

groupContiguousDataPoints maxTimeDiff list = groupBy1 (\(t1, _) (t2, _) -> t2 - t1 <= maxTimeDiff) list

それでは書いてみましょう！

groupBy1 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy1 _    []            = [[]]
groupBy1 _    [x]           = [[x]]
groupBy1 comp (x : xs@(y : _))
  | comp x y  = (x : firstGroup) : otherGroups
  | otherwise = [x] : groups
  where groups@(firstGroup : otherGroups) = groupBy1 comp xs

更新: F# では でパターン マッチができないようですseq。ただし、HubFS のこのスレッドは、必要に応じて変換することで一致シーケンスをパターン化する方法を示していLazyListます。

UPDATE2: Haskell のリストは遅延しており、必要に応じて生成されるため、F# に対応しますLazyList(seq生成されたデータはキャッシュされるため (および、それへの参照を保持しなくなった場合はもちろんガベージ コレクションが行われるため)、F# には対応しません)。

于 2009-08-24T13:26:26.377 に答える
0

以下は、私があなたが望むと思うことをするいくつかのコードです。慣用的な F# ではありません。

（ブライアンの答えに似ているかもしれませんが、LazyListのセマンティクスに慣れていないのでわかりません。）

しかし、それはあなたのテスト仕様と正確には一致しません: Seq.length は入力全体を列挙します。あなたの「テストコード」が呼び出しSeq.lengthてから呼び出しますSeq.hd。これにより、列挙子が 2 回生成されます。また、キャッシュがないため、問題が発生します。キャッシュせずに複数の列挙子を許可するクリーンな方法があるかどうかはわかりません。率直に言って、seq<seq<'a>>この問題に最適なデータ構造ではないかもしれません。

とにかく、ここにコードがあります：

type State<'a> = Unstarted | InnerOkay of 'a | NeedNewInner of 'a | Finished

// f() = true means the neighbors should be kept together
// f() = false means they should be split
let split_up (f : 'a -> 'a -> bool) (input : seq<'a>) =
    // simple unfold that assumes f captured a mutable variable
    let iter f = Seq.unfold (fun _ -> 
        match f() with
        | Some(x) -> Some(x,())
        | None -> None) ()

    seq {
        let state = ref (Unstarted)
        use ie = input.GetEnumerator()

        let innerMoveNext() = 
            match !state with
            | Unstarted -> 
                if ie.MoveNext()
                then let cur = ie.Current
                     state := InnerOkay(cur); Some(cur)
                else state := Finished; None 
            | InnerOkay(last) ->
                if ie.MoveNext()
                then let cur = ie.Current
                     if f last cur
                     then state := InnerOkay(cur); Some(cur)
                     else state := NeedNewInner(cur); None
                else state := Finished; None
            | NeedNewInner(last) -> state := InnerOkay(last); Some(last)
            | Finished -> None 

        let outerMoveNext() =
            match !state with
            | Unstarted | NeedNewInner(_) -> Some(iter innerMoveNext)
            | InnerOkay(_) -> failwith "Move to next inner seq when current is active: undefined behavior."
            | Finished -> None

        yield! iter outerMoveNext }


open System

let groupContigs (contigTime : TimeSpan) (holey : seq<DateTime * int>) =
    split_up (fun (t1,_) (t2,_) -> (t2 - t1) <= contigTime) holey


// Test data
let numbers = {1 .. 15}
let contiguousTimeStamps = 
    let baseTime = DateTime.Now
    seq { for n in numbers -> baseTime.AddMinutes(float n)}

let holeyData = 
    Seq.zip contiguousTimeStamps numbers 
        |> Seq.filter (fun (dateTime, num) -> num % 7 <> 0)

let grouped_data = groupContigs (new TimeSpan(0,1,0)) holeyData


printfn "Consuming..."
for group in grouped_data do
    printfn "about to do a group"
    for x in group do
        printfn "  %A" x
于 2009-08-24T20:05:06.183 に答える
0

わかりました、これが私が不満ではない答えです。

（編集：私は不満です-それは間違っています！今すぐ修正を試みる時間はありません。）

少し命令的な状態を使用していますが、理解するのはそれほど難しくありません (「!」は F# の逆参照演算子であり、「not」ではないことを思い出してください)。これは可能な限り怠惰で、入力として seq を取り、出力として seq の seq を返します。

let N = 20
let data =  // produce some arbitrary data with holes
    seq {
        for x in 1..N do
            if x % 4 <> 0 && x % 7 <> 0 then
                printfn "producing %d" x
                yield x
    }
let rec GroupBy comp (input:seq<_>) = seq {
    let doneWithThisGroup = ref false
    let areMore = ref true
    use e = input.GetEnumerator()
    let Next() = areMore := e.MoveNext(); !areMore
    // deal with length 0 or 1, seed 'prev'
    if not(e.MoveNext()) then () else
    let prev = ref e.Current
    while !areMore do
        yield seq {
            while not(!doneWithThisGroup) do
                if Next() then
                    let next = e.Current 
                    doneWithThisGroup := not(comp !prev next)
                    yield !prev 
                    prev := next
                else
                    // end of list, yield final value
                    yield !prev
                    doneWithThisGroup := true } 
        doneWithThisGroup := false }
let result = data |> GroupBy (fun x y -> y = x + 1)
printfn "Consuming..."
for group in result do
    printfn "about to do a group"
    for x in group do
        printfn "  %d" x
于 2009-08-25T00:38:12.367 に答える