8

这是我之前关于Seq模块iter和map功能比Array和List模块等价物慢得多的问题的后续。

查看源代码，我可以看到一些函数，例如isEmpty和length执行一个非常简单的类型检查，以优化数组和列表，然后再使用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

在iter相同的方法可以大大提高其性能的情况下，当我隐藏该iter功能时，它比内置版本提供了显着的收益：

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

我的问题是，鉴于Seq模块中的某些函数已针对特定集合类型（数组、list<T> 等）进行了优化，那么其他函数（例如iter和nth未以类似方式优化）怎么来？

此外，在map函数的情况下，正如@mausch 指出的那样，是否不可能采用类似的方法Enumerable.Select（见下文）并为不同的集合类型构建专门的迭代器？

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

提前谢谢了。

4

2 回答 2

4

在 iter 的情况下，可以采用相同的方法来极大地提高其性能

我认为这就是您问题的答案所在。您的测试是人为的，实际上并没有测试这些方法的任何真实示例。您测试了这些方法的 10,000,000 次迭代，以便在ms.

转换回每件商品的成本，它们是：

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

这些方法通常在每个集合中使用一次，这意味着此成本是算法性能的额外线性因素。在最坏的情况下，您损失的数量少于100 ns列表中的每个项目（如果您非常关心性能，则不应该使用它）。

length将此与在一般情况下始终是线性的情况进行对比。通过添加此优化，您可以为忘记手动缓存长度但幸运的是总是得到一个列表的人提供巨大的好处。

同样，您可能会isEmpty多次调用，如果您可以直接询问，添加另一个对象创建是愚蠢的。（这不是一个强有力的论点）

要记住的另一件事是，这些方法实际上都不会查看多个输出元素。您希望以下代码做什么（不包括语法错误或缺少方法）

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()))
于 2012-06-05T17:39:28.163 回答
1

Seq.length从表面上看， /的类型检查isEmpty似乎是错误的。我假设大多数Seq函数不会对正交性执行此类检查：List/Array模块中已经存在特定于类型的版本。为什么要复制它们？

这些检查在 LINQ 中更有意义，因为它只IEnumerable直接使用。

于 2012-06-04T22:11:08.327 回答