在f中取n个不同索引的序列中的n个元素#

当你想通过索引访问元素时,使用序列并不是一个好主意。序列的设计允许顺序迭代。我将把序列的必要部分转换为数组,然后按索引选择元素:

let takeIndexes ns input = 
  // Take only elements that we need to access (sequence could be infinite)
  let arr = input |> Seq.take (1 + Seq.max ns) |> Array.ofSeq
  // Simply pick elements at the specified indices from the array
  seq { for index in ns -> arr.[index] }

seq [10 .. 20] |> takeIndexes [0;5;10]  

关于您的实现——我认为它不能显著地变得更优雅。当实现需要以交错的方式从多个源获取值的函数时,这是一个普遍的问题——没有优雅的方式来编写这些值!

但是,您可以使用如下递归以函数方式编写:

let takeIndexes indices (xs:seq<int>) = 
  // Iterates over the list of indices recursively
  let rec loop (xe:IEnumerator<_>) idx indices = seq {
    let next = loop xe (idx + 1)
    // If the sequence ends, then end as well
    if xe.MoveNext() then
      match indices with
      | i::indices when idx = i -> 
        // We're passing the specified index 
        yield xe.Current
        yield! next indices
      | _ -> 
        // Keep waiting for the first index from the list
        yield! next indices }
  seq {
    // Note: 'use' guarantees proper disposal of the source sequence
    use xe = xs.GetEnumerator()
    yield! loop xe 0 indices }

seq [10 .. 20] |> takeIndexes [0;5;10]  

当需要扫描序列并将结果累积到 o(n) ,您始终可以返回到seq.fold:

let takeIndices ind sq =
    let selector (idxLeft, currIdx, results) elem =
        match idxLeft with
            | []                               -> (idxLeft, currIdx, results)
            | idx::moreIdx when idx =  currIdx -> (moreIdx, currIdx+1, elem::results)
            | idx::_       when idx <> currIdx -> (idxLeft, currIdx+1, results)
            | idx::_                           -> invalidOp "Can't get here."
    let (_, _, results) = sq |> Seq.fold selector (ind, 0, [])
    results |> List.rev

seq [10 .. 20] |> takeIndices [0;5;10]

这个解决方案的缺点是它将枚举序列到最后,即使它已经积累了所有需要的元素。

这是我的照片。此解决方案将只按需要进入序列,并以列表形式返回元素。

let getIndices xs (s:_ seq) =
    let enum = s.GetEnumerator()
    let rec loop i acc = function
        | h::t as xs ->
            if enum.MoveNext() then
                if i = h then
                    loop (i+1) (enum.Current::acc) t
                else
                    loop (i+1) acc xs
            else
                raise (System.IndexOutOfRangeException())
        | _ -> List.rev acc
    loop 0 [] xs

[10..20]
|> getIndices [2;4;8]
// Returns [12;14;18]

这里唯一的假设是对您提供的索引列表进行排序。否则,该功能将无法正常工作。

对返回的结果进行排序是否有问题? 该算法将在输入序列上线性工作。只需要对索引进行排序。如果序列很大,但索引不多,那么速度会很快。 复杂性是:n->最大(索引),m->索引计数:o(n+mlogm),在最坏的情况下。

let seqTakeIndices indexes = 
    let rec gather prev idxs xs =
        match idxs with
        | [] -> Seq.empty
        | n::ns ->  seq { let left = xs |> Seq.skip (n - prev)
                          yield left |> Seq.head
                          yield! gather n ns left }
    indexes |> List.sort |> gather 0

这里有一个list.fold变量,但阅读起来更复杂。我喜欢第一个:

let seqTakeIndices indices xs = 
    let gather (prev, xs, res) n =
        let left = xs |> Seq.skip (n - prev)
        n, left, (Seq.head left)::res
    let _, _, res = indices |> List.sort |> List.fold gather (0, xs, [])
    res

附加:仍然比你的变种慢,但比我的旧变种快得多。因为没有使用seq.skip,这就创建了新的枚举器,并且大大降低了速度。

let seqTakeIndices indices (xs : seq<_>) = 
    let enum = xs.GetEnumerator()
    enum.MoveNext() |> ignore
    let rec gather prev idxs =  
        match idxs with
        | [] -> Seq.empty
        | n::ns -> seq { if [1..n-prev] |> List.forall (fun _ -> enum.MoveNext()) then 
                            yield enum.Current
                            yield! gather n ns }
    indices |> List.sort |> gather 0