¿Por qué se optimizan algunas funciones en el módulo Seq mientras que otras no están en F #?

Question

Ésta es una continuación de mi anterior question con respecto a los módulos de Seqiter y map funciones siendo mucho más lento en comparación con los Array y List equivalentes módulo.

En cuanto a la fuente, puedo ver que algunas funciones, como isEmpty y length realiza una comprobación de tipo muy simple para optimizar para las matrices y listas antes de recurrir al uso de IEnumerator.

[<CompiledName("IsEmpty")>] 
let isEmpty (source : seq<'T>) = 
    checkNonNull "source" source 
    match source with 
    | :? ('T[]) as a -> a.Length = 0 
    | :? list<'T> as a -> a.IsEmpty 
    | :? ICollection<'T> as a -> a.Count = 0 
    | _ -> 
     use ie = source.GetEnumerator() 
     not (ie.MoveNext()) 

[<CompiledName("Length")>] 
let length (source : seq<'T>) = 
    checkNonNull "source" source 
    match source with 
    | :? ('T[]) as a -> a.Length 
    | :? ('T list) as a -> a.Length 
    | :? ICollection<'T> as a -> a.Count 
    | _ -> 
     use e = source.GetEnumerator() 
     let mutable state = 0 
     while e.MoveNext() do 
      state <- state + 1; 
     state 

En el caso de la iter el mismo enfoque se puede hacer para mejorar notablemente su rendimiento, cuando shadowed la función iter que presenta mejores resultados que la versión incorporada:

[<CompiledName("Iterate")>] 
let iter f (source : seq<'T>) = 
    checkNonNull "source" source 
    use e = source.GetEnumerator() 
    while e.MoveNext() do 
     f e.Current; 

Mi La pregunta es, dado que algunas de las funciones en el módulo Seq se optimizaron para su uso con tipos de colección específicos (matrices, lista < T>, etc.) cómo otras funciones tales como iter y nth no fueron opcionales timized de manera similar?

Además, en el caso de la función map, como señaló @mausch, ¿no es posible utilizar un enfoque similar al Enumerable.Select (ver a continuación) y crear iteradores especializados para diferentes tipos de colecciones?

public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector) 
    { 
     if (source == null) 
     throw Error.ArgumentNull("source"); 
     if (selector == null) 
     throw Error.ArgumentNull("selector"); 
     if (source is Enumerable.Iterator<TSource>) 
     return ((Enumerable.Iterator<TSource>) source).Select<TResult>(selector); 
     if (source is TSource[]) 
     return (IEnumerable<TResult>) new Enumerable.WhereSelectArrayIterator<TSource, TResult>((TSource[]) source, (Func<TSource, bool>) null, selector); 
     if (source is List<TSource>) 
     return (IEnumerable<TResult>) new Enumerable.WhereSelectListIterator<TSource, TResult>((List<TSource>) source, (Func<TSource, bool>) null, selector); 
     else 
     return (IEnumerable<TResult>) new Enumerable.WhereSelectEnumerableIterator<TSource, TResult>(source, (Func<TSource, bool>) null, selector); 
    } 

Muchas gracias de antemano.

Answer 1

En la superficie, los controles de tipo en Seq.length/isEmpty parecen errores. Supongo que la mayoría de las funciones Seq no realizan tales comprobaciones de ortogonalidad: ya existen versiones específicas del tipo en los módulos List/Array. ¿Por qué duplicarlos?

Esos controles tienen más sentido en LINQ ya que solo usa IEnumerable directamente.

Answer 2

En el caso del iter el mismo enfoque se puede hacer para mejorar notablemente su rendimiento

creo que esto es cuando la respuesta a su pregunta es. Su prueba es artificial, y en realidad no prueba ningún ejemplo del mundo real de estos métodos. Probaste 10,000,000 iteraciones de estos métodos para obtener diferencias en el tiempo en ms.

convierte de nuevo a por costos de artículos, aquí están:

  Array List 
Seq.iter 4 ns 7 ns 
Seq.map 20 ns 91 ns 

Estos métodos se utilizan normalmente una vez por recogida, es decir, este costo es un factor lineal adicional a su rendimiento algoritmos. En el peor de los casos, está perdiendo menos de 100 ns por artículo en una lista (que no debería usar si le importa tanto el rendimiento).

Contraste esto con el caso de length que es siempre lineal en el caso general. Al agregar esta optimización, brinda un enorme beneficio a alguien que olvidó almacenar manualmente la longitud, pero afortunadamente recibe siempre una lista.

De manera similar, puede llamar al isEmpty muchas veces, y agregar otra creación de objetos es una tontería si puede simplemente preguntar directamente. (Este no es un argumento tan fuerte)

Otra cosa a tener en cuenta es que ninguno de esos métodos realmente analiza más de un elemento de la salida. ¿Qué esperaría que hiciera el siguiente código (excluyendo errores de sintaxis o métodos faltantes)

type Custom() = 
    interface IEnumerable with 
    member x.GetEnumerator() = 
     return seq { 
     yield 1 
     yield 2 
     } 
    interface IList with 
    member x.Item with 
     get(index) = index 
    member x.Count = 12 

let a = Custom() 
a |> Seq.iter (v -> printfn (v.ToString()))