Возьмите N элементов из последовательности с N различными индексами в F #

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

Я мог бы сделать это с помощью seq {yield ...} и иметь счетчик-указатель для отметки, когда какой-то элемент должен быть пропущен, но если 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.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