6

我有以下扩展方法来查找序列中的一个元素，然后返回两个IEnumerable<T>s：一个包含该元素之前的所有元素，一个包含该元素及其后面的所有内容。如果该方法是懒惰的，我会更喜欢，但我还没有找到一种方法来做到这一点。任何人都可以提出解决方案吗？

public static PartitionTuple<T> Partition<T>(this IEnumerable<T> sequence, Func<T, bool> partition)
{
    var a = sequence.ToArray();
    return new PartitionTuple<T>
    {
        Before = a.TakeWhile(v => !partition(v)),
        After = a.SkipWhile(v => !partition(v))
    };
}

立即sequence.ToArray()行动违反了懒惰的要求。然而，如果没有这条线，一个昂贵的迭代sequence可能会被迭代两次。并且，根据调用代码的作用，更多次。

4

4 回答 4

4

您可以使用该Lazy对象来确保在迭代两个分区之一之前源序列不会转换为数组：

public static PartitionTuple<T> Partition<T>(
    this IEnumerable<T> sequence, Func<T, bool> partition)
{
    var lazy = new Lazy<IEnumerable<T>>(() => sequence.ToArray());
    return new PartitionTuple<T>
    {
        Before = lazy.MapLazySequence(s => s.TakeWhile(v => !partition(v))),
        After = lazy.MapLazySequence(s => s.SkipWhile(v => !partition(v)))
    };
}

我们将使用这种方法来推迟评估惰性，直到序列本身被迭代：

public static IEnumerable<TResult> MapLazySequence<TSource, TResult>(
    this Lazy<IEnumerable<TSource>> lazy, 
    Func<IEnumerable<TSource>, IEnumerable<TResult>> filter)
{
    foreach (var item in filter(lazy.Value))
        yield return item;
}
于 2013-11-14T16:30:14.447 回答
1

这是一个有趣的问题，要解决它，你必须知道什么是“正确”。对于操作的语义，我认为这个定义是有道理的：

  • 源序列仅枚举一次，即使结果序列被枚举了多次。
  • 在枚举结果之一之前不会枚举源序列。
  • 每个结果都应该可以独立枚举。
  • 如果源序列发生变化，不确定会发生什么。

我不完全确定我对匹配对象的处理是否正确，但我希望你明白这一点。我将很多工作推迟到PartitionTuple<T>课堂上，以便能够偷懒。

public class PartitionTuple<T>
{
  IEnumerable<T> source;
  IList<T> before, after;
  Func<T, bool> partition;

  public PartitionTuple(IEnumerable<T> source, Func<T, bool> partition)
  {
    this.source = source;
    this.partition = partition;
  }

  private void EnsureMaterialized()
  {
    if(before == null)
    {
      before = new List<T>();
      after = new List<T>();

      using(var enumerator = source.GetEnumerator())
      {
        while(enumerator.MoveNext() && !partition(enumerator.Current))
        {
          before.Add(enumerator.Current);   
        }

        while(!partition(enumerator.Current) && enumerator.MoveNext());

        while(enumerator.MoveNext())
        {
          after.Add(enumerator.Current);
        }
      }
    }
  }

  public IEnumerable<T> Before 
  { 
    get
    {
      EnsureMaterialized();
      return before;
    }
  }

  public IEnumerable<T> After
  {
    get
    {
      EnsureMaterialized();
      return after;
    }
  }
}

public static class Extensions
{
  public static PartitionTuple<T> Partition<T>(this IEnumerable<T> sequence, Func<T, bool> partition)
  {
    return new PartitionTuple<T>(sequence, partition);
  }
}
于 2013-11-14T16:30:36.563 回答
1

这是一个通用的解决方案，它将记住任何IEnumerable<T>内容以确保它只迭代一次，而不会强制整个事物进行迭代：

public class MemoizedEnumerable<T> : IEnumerable<T>, IDisposable
{
   private readonly IEnumerator<T> _childEnumerator;
   private readonly List<T> _itemCache = new List<T>();

   public MemoizedEnumerable(IEnumerable<T> enumerableToMemoize)
   {
       _childEnumerator = enumerableToMemoize.GetEnumerator();
   }

   public IEnumerator<T> GetEnumerator()
   {
       return _itemCache.Concat(EnumerateOnce()).GetEnumerator();
   }

   public void Dispose()
   {
       _childEnumerator.Dispose();
   }

   private IEnumerable<T> EnumerateOnce()
   {
       while (_childEnumerator.MoveNext())
       {
           _itemCache.Add(_childEnumerator.Current);
           yield return _childEnumerator.Current;
       }
   }

   IEnumerator IEnumerable.GetEnumerator()
   {
       return GetEnumerator();
   }
}

public static class EnumerableExtensions
{
    public static IEnumerable<T> Memoize<T>(this IEnumerable<T> enumerable)
    {
        return new MemoizedEnumerable<T>(enumerable);
    }
}

要将它用于您的分区问题，请执行以下操作：

var memoized = sequence.Memoize();
return new PartitionTuple<T>
{
    Before = memoized.TakeWhile(v => !partition(v)),
    After = memoized.SkipWhile(v => !partition(v))
};

这只会迭代sequence最多一次。

于 2013-11-14T16:36:50.100 回答
0

通常，您只需返回自定义类的一些对象，该对象实现IEnumerable<T>但也仅提供枚举需求的结果。

您也可以实现IQueryable<T>(inherits IEnumerable) 而不是IEnumerable<T>，但它更需要使用查询来构建到达功能，例如linq for sql提供：仅在最终枚举请求上执行的数据库查询。

于 2013-11-14T16:25:51.613 回答