f# - F# - 如何在循环序列中对上一个、这个和下一个元素进行分组

Question

在 F# 中，如何最好地将有限序列类seq [0; 1; 2; 3; 4]转换为元组序列，如seq [4,0,1 ; 0,1,2 ; 1,2,3 ; 2,3,4 ; 3,4,0]？

补充： My Seq 代表循环数据。在这种情况下，闭合多段线的顶点。我需要相邻元素来计算每个角的角度。

Answer 1

这是一个仅使用序列的简单解决方案。请注意，如果输入和输出总是一个列表，则有一个稍微复杂但更快的解决方案，它只使用列表并只遍历输入一次。

// Example usage: neighbors [0..4]
let neighbors input =
    let inputLength = Seq.length input
    input
    // The sequence needs to be looped three times;
    // the first and last time handle the previous value for the first
    // element in the input sequence and the next value for the last
    // element in the input sequence, respectively.
    |> Seq.replicate 3
    // Start at the previous element of the first element in the input sequence.
    |> Seq.skip (inputLength - 1)
    // Take the same number of elements as the tuple.
    |> Seq.windowed 3
    // Only keep the same number of elements as the original sequence.
    |> Seq.take inputLength
    // Convert the arrays to tuples
    |> Seq.map (fun values ->
        values.[0], values.[1], values.[2])
    // Return the result as a list of tuples.
    |> Seq.toList

Answer 2

如果您不需要惰性，则使用中间数组可能更有效，例如

// get items (i-1, i, i+1) from arr; wrap around at the boundaries
let adj3 i (arr: 'a[]) =
    // modulo operator that works correctly
    let inline (%%) x y = ((x % y) + y) % y
    let len = arr.Length
    arr.[(i - 1) %% len], arr.[i], arr.[(i + 1) %% len]

let windowed3 s = seq { 
    let sarr = s |> Seq.toArray    
    for i = 0 to sarr.Length do 
        yield adj3 i sarr }

时间复杂度为 O( n )。

Answer 3

这给出了正确的答案，尽管您现在拥有的第一个元素排在最后，但这不是问题，您仍然可以找到每组三点的角度。

let cycle s =
    Seq.append s (Seq.take 2 s) // append the first two elements to the and
    |> Seq.windowed 3           // create windows of 3
    |> Seq.map (fun a -> (a.[0], a.[1], a.[2])) // create tuples


// test
[0;1;2;3;4] |> cycle

// returns:
>
  val it : seq<int * int * int> =
  seq [(0, 1, 2); (1, 2, 3); (2, 3, 4); (3, 4, 0); ...]

Answer 4

这里有一些很好的答案，这里还有一个。对我来说，它看起来最易读，复杂度为O(n)，并且还保留了一些错误检查：

// Returns the last element of a sequence.
// Fails on empty sequence
let last xs =
    let len = Seq.length xs - 1
    if len < 0 then failwith "Sequence must be non-empty"
    xs
    |> Seq.skip len
    |> Seq.head

// Converts an array into a tuple
let toTuple = function
    | [|a; b; c|] -> (a, b, c)
    | _ -> failwith "Must be an array with exactly 3 elements"

let windowedBy3 xs =
    seq {
        yield last xs;
        yield! xs;
        yield Seq.head xs
    }
    |> Seq.windowed 3
    |> Seq.map toTuple

// Usage
Seq.init 5 id
|> windowedBy3
|> Seq.iter (printf "%A; ")

Answer 5

let windowedEx n (s: seq<_>) =
  let r = ResizeArray(s)
  if r.Count > 1 then
    let last = r.[r.Count-1]
    r.Add(r.[0])
    r.Insert(0, last)
  Seq.windowed n r

Answer 6

我会这样做：

let neighbors xs =
  match Array.ofSeq xs with
  | [||] -> [||]
  | [|x|] -> [|x, x, x|]
  | xs ->
      let n = xs.Length
      [|yield xs.[n-1], xs.[0], xs.[1]
        for i=1 to n-2 do
          yield xs.[i-1], xs.[i], xs.[i+1]
        yield xs.[n-2], xs.[n-1], xs.[0]|]

比较通常比模整数运算快得多。为了使其更快，请预先分配数组并填充元素，而不是使用序列表达式。

Answer 7

一个通用的解决方案是Seq.circularWindowed什么样的？给定窗口大小n，它需要预先消耗第一个n - 1元素，同时保持其余元素的惰性。如果源中的元素不超过n - 1元素，它会生成一个空序列。

所以它是一个用于缓存的 ResizeArray 和一个将它们拼接在一起的序列表达式。

module Seq =
    let circularWindowed n (xs : seq<_>) =
        let en = xs.GetEnumerator()
        let ra = ResizeArray()
        while ra.Count < n - 1 && en.MoveNext() do
            ra.Add en.Current
        seq{
            if en.MoveNext() then 
                yield! ra
                yield en.Current
                while en.MoveNext() do
                    yield en.Current
                yield! ra }
        |> Seq.windowed n

seq [0; 1; 2; 3; 4]
|> Seq.circularWindowed 3
|> Seq.toList
// val it : int [] list =
//   [[|0; 1; 2|]; [|1; 2; 3|]; [|2; 3; 4|]; [|3; 4; 0|]; [|4; 0; 1|]]