[Ottimizza questo]: LINQ lenta alla query di oggetti

Question

Ho questa query che mi dà fastidio; è incapsulato come un nuovo operatore di query, ne ho fatto due versioni, cercando di vedere quale si comporta meglio. Entrambi eseguono orribilmente.

Primo tentativo; stile dichiarativo

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length) 
{ 
    return source.Any() 
     ? source.Take(length).Cons(source.Skip(length).Section(length)) 
     : Enumerable.Empty<IEnumerable<α>>(); 
} 

Secondo tentativo: imperativo "dei rendimenti" stile

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length) 
{ 
    var fst = source.Take(length); 
    var rst = source.Skip(length); 

    yield return fst; 

    if (rst.Any()) 
     foreach (var section in rst.Section(length)) 
      yield return section; 
} 

Infatti il ​​secondo tentativo è peggio, sia in termini di leggibilità, composizionalità e in termini di velocità.

Eventuali indizi su come ottimizzare questo?

Answer 1

Ho il sospetto che il problema che hai riscontrato è legato al fatto che l'enumerazione il risultato finale è a almeno un'operazione O (n^2), forse peggio; Non ho ancora capito tutto nella mia testa.

Perché è quello? Bene, supponiamo di avere [1, 2, 3, 4, 5, 6] e lo dividi in ciò che pensi sia {{1, 2}, {3, 4}, {5, 6}}

Questo non è quello che hai fatto. In pratica lo hai diviso in {prendi i primi due, prendi i primi due e scartali e poi prendi i due successivi, prendi i primi due e poi scartati e poi prendi i due successivi e scartali e poi prendi il terzo due}

Nota come ogni passo lungo il percorso ricalcola il risultato? Questo perché la matrice potrebbe cambiare tra le chiamate all'enumerazione. LINQ è stato progettato per ottenere sempre risultati aggiornati; scrivi una query che significa "salta i primi quattro e itera i successivi due", è esattamente quello che ottieni - una query che esegue quel codice quando lo enumeri.

La sequenza originale è abbastanza piccola e veloce da poter leggere l'intera cosa in memoria e dividerla tutto in una volta, piuttosto che provare a farlo in modo pigramente? In alternativa, la sequenza è indicizzabile? Se tutto quello che ottieni è l'accesso in avanti alla sequenza ed è troppo grande o lento da leggere in memoria tutto in una volta, allora non c'è molto che tu possa fare qui. Ma se hai una o entrambe queste proprietà allora puoi renderlo almeno lineare.

Answer 2

Ove possibile, cerco di eseguire un'iterazione solo una volta all'interno di un operatore. Se la fonte è qualcosa come il risultato di un operatore Reverse(), chiamare Any, Take e Skip potrebbe causare un sacco di prestazioni brutte.

Non è del tutto chiaro cosa stia tentando di fare il tuo operatore, ma se riesci a farlo senza leggere la sorgente più volte, questo potrebbe essere d'aiuto - sebbene dipenderà molto dall'input.

Answer 3

Se ho compreso correttamente la tua domanda, stai cercando di creare un'implementazione lenta di un enumeratore che divide una più ampia raccolta di elementi in raccolte di oggetti enumerabili più piccole.

Ad esempio, una sequenza di un milione di numeri può essere suddivisa in "sezioni", ognuna delle quali ne produce solo 100, e si desidera che tutto funzioni pigramente, cioè. non raccogliere 100 elementi in una lista prima di produrli.

In primo luogo, i tentativi tenteranno di ripetere la raccolta più volte, il che è negativo, quindi il problema delle prestazioni.

Se si sta cercando di costruire un'implementazione pigro pura, si dovrebbe prendere in considerazione i seguenti aspetti:

• Si vuole iterare l'insieme sottostante solo una volta
• Si dovrebbe tornare enumerables che ri-uso l'enumeratore sottostante
• È necessario gestire che una sezione che si restituisce non sia completamente enumerata (ad esempio, il codice chiamante aveva solo bisogno dei primi 50 di quei 100 elementi).

---

Edit: Prima di andare nella mia soluzione semplicistica, ecco alcune precisazioni al riguardo:

• Non è possibile salvare ogni sezione per dopo, vale a dire. non puoi fare: collection.Sequence(10).ToArray() per ottenere una serie di sezioni.
• Non è possibile enumerare su ciascuna sezione più di una volta, perché quando lo si fa, cambia una struttura di dati sottostante nascosta.

In sostanza: mia soluzione non è di uso generale.Dovresti andare con il commento di @LBushkin su MoreLinq Batch se ne hai bisogno, e esiterei a mettere il mio codice in una libreria di classi, dovrebbe essere locale dove è necessario, o rinominato in qualcosa che ti avvisa chiaramente del problemi con esso.

---

Ecco un'implementazione semplicistico, sono abbastanza sicuro che ci sono bug qui, così si potrebbe desiderare di guardare ad attuare una tonnellata di unit test per edgecases:

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace ConsoleApplication20 
{ 
    class SectionEnumerable<T> : IEnumerable<T> 
    { 
     private readonly IEnumerator<T> _Enumerator; 

     public SectionEnumerable(IEnumerator<T> enumerator, int sectionSize) 
     { 
      _Enumerator = enumerator; 
      Left = sectionSize; 
     } 

     public IEnumerator<T> GetEnumerator() 
     { 
      while (Left > 0) 
      { 
       Left--; 
       yield return _Enumerator.Current; 
       if (Left > 0) 
        if (!_Enumerator.MoveNext()) 
         break; 
      } 
     } 

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

     public int Left { get; private set; } 
    } 

    static class SequenceExtensions 
    { 
     public static IEnumerable<IEnumerable<T>> Section<T>(this IEnumerable<T> collection, int sectionSize) 
     { 
      if (collection == null) 
       throw new ArgumentNullException("collection"); 
      if (sectionSize < 1) 
       throw new ArgumentOutOfRangeException("sectionSize"); 

      using (IEnumerator<T> enumerator = collection.GetEnumerator()) 
      { 
       while (enumerator.MoveNext()) 
       { 
        SectionEnumerable<T> enumerable = new SectionEnumerable<T>(enumerator, sectionSize); 
        yield return enumerable; 
        for (int index = 0; index < enumerable.Left; index++) 
         if (!enumerator.MoveNext()) 
          yield break; 
       } 
      } 
     } 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      var sequence = Enumerable.Range(0, 100); 
      var sections = sequence.Section(10); 
      foreach (var section in sections) 
      { 
       Console.WriteLine(
        String.Join(", ", 
        section.Take(5).ToArray().Select(i => i.ToString()).ToArray())); 
      } 
      Console.ReadLine(); 
     } 
    } 
} 

uscita:

0, 1, 2, 3, 4 
10, 11, 12, 13, 14 
20, 21, 22, 23, 24 
30, 31, 32, 33, 34 
40, 41, 42, 43, 44 
50, 51, 52, 53, 54 
60, 61, 62, 63, 64 
70, 71, 72, 73, 74 
80, 81, 82, 83, 84 
90, 91, 92, 93, 94 

cose che si dovrebbero unità-test:

• raccolta ingresso vuoto non produce sezioni
• Una collezione che ha appena il giusto numero di elementi, produce solo una sezione
• Una collezione che contiene una multiplum degli elementi sezione dimensioni, (cioè. 10, 20, 30, ecc. Numero di elementi con una sezione di 5 o 10), non produce una sezione vuota dopo tutti quelli attesi
• Che in realtà è pigro, se si enumera il primo 10- sezione elemento, ma solo i primi 5 della seconda sezione, solo i primi 15 elementi della raccolta sottostante sono enumerati su

Answer 4

È più veloce? Dovrebbe essere, perché ha bisogno solo di una singola iterazione attraverso la sequenza sorgente.

public static IEnumerable<IEnumerable<T>> Section<T>(
    this IEnumerable<T> source, int length) 
{ 
    return source 
     .Select((x, i) => new { Value = x, Group = i/length }) 
     .GroupBy(x => x.Group, y => y.Value); 
} 

Answer 5

Ecco un altro approccio non utilizzando LINQ che è stato molto più veloce il tuo secondo metodo:

public static IEnumerable<IEnumerable<a>> Section<a>(this IEnumerable<a> source, int length) 
     { 


      var enumerator = source.GetEnumerator(); 
      var continueLoop = true; 
      do 
      { 
       var list = new List<a>(); 
       var index = 0; 
       for (int i = 0; i < length; i++) 
       { 
        if (enumerator.MoveNext()) 
        { 
         list.Add(enumerator.Current); 
         index++; 
        } 
        else 
        { 
         continueLoop = false; 
         break; 
        } 
       } 
       if (list.Count > 0) 
       { 
        yield return list; 
       } 
      } while (continueLoop); 


     } 

Answer 6

ho avuto un'idea oggi; controllare questo

public static IEnumerable<α> Take<α>(this IEnumerator<α> iterator, int count) 
{ 
    for (var i = 0; i < count && iterator.MoveNext(); i++) 
     yield return iterator.Current; 
} 

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerator<α> iterator, int length) 
{ 
    var sct = Enumerable.Empty<α>(); 
    do 
    { 
     sct = iterator.Take(length).ToArray(); 
     if (sct.Any()) 
      yield return sct; 
    } 
    while (sct.Any()); 
} 

Questo non è ancora super elegante ma almeno l'implementazione è molto breve e leggibile.

Può essere molto interessante indagare operatori di query su IEnumerator.

E per comodità

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length) 
{ 
    using (var iterator = source.GetEnumerator()) 
     foreach (var e in iterator.Section(length)) 
      yield return e; 
} 

Answer 7

Avete bisogno di mantenere la vostra fonte originale in giro per qualche motivo, come si procede? Se no, perché non usi la ricorsione e utilizzare lo stile HD :: tl per tirare la testa, passare il TL nella chiamata ricorsiva, e su qualsiasi numero pari ricorsione unire i due si è seduti intorno in una sezione?

Con la versione aggiornata delle estensioni sperimentali Ix, è possibile utilizzare il Window o Buffer operatori per creare un sliding window, che dovrebbe raggiungere ciò che si sta dopo.

Answer 8

Che ne dite di un metodo di estensione

public static class IEnumerableExtensions 
{ 
    public static IEnumerable<List<T>> InSetsOf<T>(this IEnumerable<T> source, int max) 
    { 
     List<T> toReturn = new List<T>(); 
     foreach(var item in source) 
     { 
       toReturn.Add(item); 
       if (toReturn.Count == max) 
       { 
         yield return toReturn; 
         toReturn = new List<T>(); 
       } 
     } 
     if (toReturn.Any()) 
     { 
       yield return toReturn; 
     } 
    } 
} 

alcuni test:

[TestFixture] 
public class When_asked_to_return_items_in_sets 
{ 
    [Test] 
    public void Should_return_the_correct_number_of_sets_if_the_input_contains_a_multiple_of_the_setSize() 
    { 
     List<string> input = "abcdefghij".Select(x => x.ToString()).ToList(); 
     var result = input.InSetsOf(5); 
     result.Count().ShouldBeEqualTo(2); 
     result.First().Count.ShouldBeEqualTo(5); 
     result.Last().Count.ShouldBeEqualTo(5); 
    } 

    [Test] 
    public void Should_separate_the_input_into_sets_of_size_requested() 
    { 
     List<string> input = "abcdefghijklm".Select(x => x.ToString()).ToList(); 
     var result = input.InSetsOf(5); 
     result.Count().ShouldBeEqualTo(3); 
     result.First().Count.ShouldBeEqualTo(5); 
     result.Last().Count.ShouldBeEqualTo(3); 
    } 
}