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# 中并不漂亮，而且还有一个元素过于急切。

我希望有更好的方法，但我必须稍后再试。

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

（编辑：这与布赖恩的解决方案存在类似的问题，即在不迭代每个内部序列的情况下迭代外部序列将会把事情搞砸！）

这是一个嵌套序列表达式的解决方案。.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# 中实现最佳的懒惰程度有点困难......从好的方面来说，这比我上次的尝试更实用，因为它不使用任何参考单元。

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

你似乎想要一个有签名的函数

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

即一个函数和一个序列，然后根据函数的结果将输入序列分解为一个序列序列。

将值缓存到实现 IEnumerable 的集合中可能是最简单的（尽管不完全是纯粹的，但要避免多次迭代输入。它将失去输入的大部分惰性）：

让 groupBy (fun: 'a -> bool) (输入: seq) =
  序列{
    让缓存 = ref (new System.Collections.Generic.List())
    for e in input do
      (!cache).Add(e)
      如果不是（fun e）那么
        产量！缓存
        缓存 := 新 System.Collections.Generic.List()
    如果 cache.Length > 0 那么
     产量！缓存
  }

另一种实现可以将缓存集合（as seq<'a>）传递给函数，以便它可以看到多个元素来选择断点。

于 2009-08-24T10:47:49.947 回答
1

一个 Haskell 解决方案，因为我不太了解 F# 语法，但它应该很容易翻译：

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

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

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]Prelude中有一个功能：

group 函数接受一个列表并返回一个列表列表，使得结果的串联等于参数。此外，结果中的每个子列表仅包含相等的元素。例如，

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，因为生成的数据被缓存（当然，如果您不再持有对它的引用，则会收集垃圾））。

于 2009-08-24T13:26:26.377 回答
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 回答
0

下面是一些我认为你想要的代码。它不是惯用的 F#。

（它可能类似于 Brian 的回答，虽然我不知道，因为我不熟悉 LazyList 语义。）

但它与您的测试规范不完全匹配： Seq.length 枚举其整个输入。您的“测试代码”调用Seq.length然后调用Seq.hd. 这将生成一个枚举器两次，并且由于没有缓存，所以事情变得一团糟。我不确定是否有任何干净的方法可以允许多个枚举器不缓存。坦率地说，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 回答