Tome N elementos de la secuencia con N índices diferentes en F #

Question

Soy nuevo en F # y busco una función que tome N * índices y una secuencia y me da N elementos. Si tengo N índices, debería ser igual a concat Seq.nth index0, Seq.nth index1 ... Seq.nth indexN, pero solo debería escanear sobre indexN elementos (O (N)) en la secuencia y no index0 + index1 + .. . + indexN (O (N^2)).

En resumen, estoy buscando algo como:

//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 

que podría hacer esto mediante el uso ss {...} rendimiento y tienen un índice de venta libre que marque cuando algún elemento debe ser pasado pero si F # ofrece una buena forma estándar, preferiría usar eso.

Gracias:) ...

adición : me han hecho lo siguiente. Funciona pero no es bonito. Sugerencias bienvenidas

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

Cuando quiera acceder a los elementos por índice, entonces usar secuencias no es tan buena idea. Las secuencias están diseñadas para permitir la iteración secuencial. Me gustaría convertir la parte necesaria de la secuencia de una matriz y luego recoger los elementos por el índice:

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] 

En cuanto a su aplicación - Creo que no se puede hacer mucho más elegante. Este es un problema general cuando se implementan funciones que necesitan tomar valores de múltiples fuentes de manera intercalada. ¡Simplemente no hay una manera elegante de escribirlas!

Sin embargo, puede escribir esto de una manera funcional utilizando la recursividad como esto:

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

Cuando necesite escanear una secuencia y suma los resultados en O (n), siempre se puede recurrir a 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] 

el inconveniente de esta solución es que va a enumerar la secuencia hasta el final, incluso si se ha acumulado todos los elementos deseados ya.

Answer 3

Aquí está mi oportunidad para esto. Esta solución solo irá tan lejos como sea necesario en la secuencia y devolverá los elementos como una lista.

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] 

La única suposición que se realiza aquí es que la lista de índices que proporciona está ordenada. La función no funcionará correctamente de lo contrario.

Answer 4

¿Hay algún problema con la clasificación del resultado devuelto? Este algoritmo funcionará linealmente sobre la secuencia de entrada. Solo los índices deben ser ordenados. Si la secuencia es grande, pero los índices no son tantos, será rápido. La complejidad es: N -> Máx. (Índices), M -> número de índices: O (N + MlogM) en el peor de los casos.

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 

Aquí hay una variante de List.fold, pero es más compleja de leer. Yo prefiero la primera:

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 

adjuntos: La Aún más lento que su variante, pero mucho más rápido que el mío variantes mayores. Debido a no usar Seq.omita eso, está creando nuevos enumeradores y está frenando mucho las cosas.

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