Возьмите элементы N от последовательности с различными индексами N в F#
Я плохо знаком с F# и поиском функции, которые берут N*indexes и последовательность, и дает мне элементы 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 {урожаем...} и имеют индекс - в противоречии с галочкой, когда некоторый элемент должен быть роздан, но если 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
}
4 ответа
Если вы хотите получить доступ к элементам по индексу, то использование последовательностей не является хорошей идеей. Последовательности предназначены для обеспечения последовательной итерации. Я бы преобразовал необходимую часть последовательности в массив, а затем выбрал бы элементы по индексу:
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 -> Max (индексы), 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