Warum sind einige Funktionen im Seq-Modul optimiert, während andere nicht in F # waren?

Question

Dies ist ein Follow-up zu meinem vorherigen question in Bezug auf die iter des Seq Modul und map Funktionen langsamer sind viel im Vergleich zu dem Array und List Modul-Äquivalente.

an der Quelle der Suche, kann ich sehen, dass einige Funktionen wie isEmpty und length eine sehr einfache Art Prüfung durchführt, um für Arrays und Listen zu optimieren, bevor greifen IEnumerator verwenden.

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

Im Fall der iter der gleiche Ansatz in beträchtlichem Ausmaß getan werden kann, um seine Leistung zu verbessern, wenn ich die iter Funktion es, erhebliche Gewinne über die integrierte Version shadowed:

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

Mein Die Frage ist, dass einige der Funktionen im Seq Modul für die Verwendung mit bestimmten Sammlungstypen (Arrays, Liste < T> usw.) optimiert wurden, wie andere Funktionen wie iter und nth nicht op waren ähnlich timized?

Auch im Fall von map Funktion, wie @mausch darauf hingewiesen, ist es nicht möglich, einen ähnlichen Ansatz zu Enumerable.Select (siehe unten) und bauen spezielle Iteratoren für verschiedene Sammlungstypen zu verwenden?

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); 
    } 

Vielen Dank im Voraus.

Answer 1

Auf der Oberfläche erscheinen die Typprüfungen in Seq.length/isEmpty wie Fehler. Ich nehme an, die meisten Seq Funktionen führen solche Prüfungen auf Orthogonalität nicht durch: typspezifische Versionen existieren bereits in den List/Array Modulen. Warum duplizieren sie?

Diese Prüfungen sind in LINQ sinnvoller, da sie nur IEnumerable direkt verwendet.

Answer 2

Im Fall des iter des gleichen Ansatzes kann in beträchtlichem Ausmaß getan werden, um seine Leistung zu verbessern

Ich denke, das ist, wo die Antwort auf Ihre Frage. Ihr Test ist künstlich und testet keine realen Beispiele dieser Methoden. Sie haben 10.000.000 Iterationen dieser Methoden getestet, um Timing-Unterschiede in ms zu erhalten.

Umbau zurück pro Stückkosten, hier sind sie: ein zusätzlicher linearer Faktor für Ihre Algorithmen Leistung

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

werden einmal Diese Verfahren, die typischerweise verwendet pro Sammlung, ist es, diese Kosten bedeuten. Im schlimmsten Fall verlieren Sie weniger als 100 ns pro Artikel in einer Liste (die Sie nicht verwenden sollten, wenn Sie sich um die Leistung kümmern).

Vergleichen Sie dies mit dem Fall von length, die im allgemeinen immer linear ist. Durch das Hinzufügen dieser Optimierung bieten Sie einen enormen Vorteil für jemanden, der vergessen hat, die Länge manuell zu cachen, aber zum Glück erhält er immer eine Liste.

In ähnlicher Weise können Sie isEmpty oft anrufen, und das Hinzufügen einer anderen Objekt-Erstellung ist albern, wenn Sie einfach direkt fragen können. (Dieser ist nicht so stark ein Argument)

Eine andere Sache zu beachten ist, dass keine dieser Methoden tatsächlich sieht mehr als ein Element der Ausgabe. Was würden Sie von dem folgenden Code erwarten (mit Ausnahme von Syntaxfehlern oder fehlenden Methoden)