Sequenza di partizione lenta con LINQ

Question

Ho il seguente metodo di estensione per trovare un elemento all'interno di una sequenza e quindi restituire due IEnumerable<T> s: uno contenente tutti gli elementi precedenti a quell'elemento e uno contenente l'elemento e tutto ciò che segue. Preferirei se il metodo fosse pigro, ma non ho trovato un modo per farlo. Qualcuno può venire con una soluzione?

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

Facendo sequence.ToArray() sconfigge immediatamente il requisito pigrizia. Tuttavia, senza quella linea, uno sequence costoso da iterare può essere ripetuto due volte. E, a seconda di ciò che fa il codice chiamante, molte più volte.

Answer 1

Questo è un problema interessante e per farlo bene, bisogna sapere che cosa "giusta" è. Per la semantica dell'operazione, penso che questa definizione abbia senso:

• La sequenza di origine viene enumerata solo una volta anche se le sequenze risultanti vengono enumerate più volte.
• La sequenza di origine non viene enumerata finché non viene elencato uno dei risultati.
• Ciascuno dei risultati dovrebbe essere possibile enumerare in modo indipendente.
• Se la sequenza di origine cambia, non è definito cosa succederà.

Non sono del tutto sicuro di aver avuto la corretta gestione dell'oggetto corrispondente, ma spero che tu abbia ottenuto l'idea. Sto rimandando un sacco di lavoro alla classe PartitionTuple<T> per poter essere pigro.

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

Answer 2

Generalmente, si restituisce solo un oggetto della classe personalizzata, che implementa IEnumerable<T> ma fornisce anche i risultati sulla sola richiesta di enumerazione.

È possibile anche implementare IQueryable<T> (eredita IEnumerable) invece di IEnumerable<T>, ma è piuttosto necessario per la costruzione di funzionalità raggiungibili con le query come quella, che linq for sql dispone: query di database in esecuzione solo su richiesta di enumerazione finale.

Answer 3

È possibile utilizzare l'oggetto Lazy per assicurare che la sequenza sorgente non viene convertita in una matrice finché uno dei due partizioni viene iterato:

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

useremo questo metodo di rinviare valutare i pigri fino a quando la sequenza stessa viene iterato:

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

Answer 4

Ecco una soluzione generica che Memoize qualsiasi IEnumerable<T> per garantire è solo iterata una volta, senza forzare il tutto per iterare:

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

di usarlo per il tuo problema di partizionamento, fare questo:

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

Ciò solo iterare sequence un massimo di una volta.