F＃中有N個不同索引的序列取N個元素

Question

我是F＃的新手，正在尋找一個取N *個索引和一個序列並給出N個元素的函數。如果我有N個索引，它應該等於concat Seq.nth index0，Seq.nth index1 .. Seq.nth indexN，但它應該只掃描序列中的indexN元素（O（N）），而不是index0 + index1 +。 。+ indexN（O（N^2））。

綜上所述，我在尋找類似：

//For performance, the index-list should be ordered on input, be padding between elements instead of indexes or be ordered when entering the function 
seq {10 .. 20} |> Seq.takeIndexes [0;5;10] 
Result: 10,15,20 

我可以使用了序列{產量...}使這個，有一個指數計數器打勾當一些元素應該傳遞但如果F＃提供了一個很好的標準方式，我寧願使用它。

感謝：）...

增加：我做了以下內容。它有效，但並不漂亮。歡迎提出建議

let seqTakeIndexes (indexes : int list) (xs : seq<int>) = 
    seq { 
     //Assume indexes is sorted 
     let e = xs.GetEnumerator() 
     let i = ref indexes 
     let curr = ref 0 

     while e.MoveNext() && not (!i).IsEmpty do 
      if !curr = List.head !i then 
       i := (!i).Tail 
       yield e.Current 

      curr := !curr + 1 
    } 

Answer 1

當你想通過索引訪問元素，那麼使用序列並不是什麼好主意。序列被設計爲允許順序迭代。我想序列的必要組成部分轉換爲數組，然後指數挑選要素：

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] 

Answer 2

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] 

這種解決方案的缺點是，它將枚舉序列結束時，即使它已經累積的所有所需的元素已經。

Answer 3

這是我拍的照片。這個解決方案只會按照需要進入序列並將元素作爲列表返回。

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] 

這裏唯一的假設是您提供的索引列表已排序。否則，該功能將無法正常工作。

Answer 4

這是一個問題，返回的結果是排序？ 該算法將在輸入序列上線性工作。只需要對索引進行排序。如果序列很大，但索引不是很多 - 它會很快。 複雜性是：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。跳過創建新的統計員並且讓事情變得很慢。

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