Big O equivalenza per LINQ select

Question

Big O equivalenza per LINQ select

#1 da (12 voti)
#2 da (4 voti)

7

Sto provando a determinare se c'è un cambiamento nell'equivalenza di Big O di un ciclo annidato quando uso una selezione LINQ.

public void myFunc(List<Foo> fooList, List<Bar> barList)
{
    foreach(Foo foo in fooList)
    {
        foreach(Bar bar in barList)
        {
            if(foo.PropA == bar.PropA && bar.PropZ.HasValue)
                foo.PropC = foo.PropB * bar.PropZ;
        }
    }
}

Credo che questo esempio di loop annidato sia O (n ^ 2) per complessità.

Ho sostituito il ciclo annidato con una selezione LINQ come questa:

public void myFunc(List<Foo> fooList, List<Bar> barList)
{
    foreach(Foo foo in fooList)
    {
        Bar bar = (from b in barList
                    where foo.PropA == b.PropA
                    select b).FirstOrDefault();

        if(bar.PropZ.HasValue)
            foo.PropC = foo.PropB * bar.PropZ;
    }
}

Se non altro, il codice sembra essere un po 'più pulito da leggere in quanto afferma esplicitamente "stiamo cercando questo particolare Bar con cui lavorare".

La mia domanda è questa : l'uso del LINQ select riduce la complessità del Big O?

c# big-o

posta GlenH7 18.05.2015 - 19:45

fonte

2 risposte

4

Nessuna differenza di complessità, entrambe sono O (n²) perché Linq's Where è O (n).
L'uso di FirstOrDefault è equivalente a questo:

if(foo.PropA == bar.PropA && bar.PropZ.HasValue) 
{
    foo.PropC = foo.PropB * bar.PropZ;
    break;
}

Questo è un miglioramento del tempo di calcolo, ma non della complessità.

Puoi fare di meglio usando una Hashmap per uno dei due elenchi.
L'operatore Join di Linq creerà una Hashmap per uno dei 2 elenchi, in modo da guadagnare su prestazioni durante la ricerca di due elementi corrispondenti:

    public void myFunc(List<Foo> fooList, List<Bar> barList)
    {
        var rows = fooList.Join(
                        barList, 
                        f => f.PropA, 
                        b => b.PropA, 
                        (f, b) => new { Foo = f, Bar = b }
                   );

        foreach (var row in rows)
        {
            if (row.Bar.PropZ.HasValue)
                row.Foo.PropC = row.Foo.PropB * row.Bar.PropZ.Value;
        }
    }

Questo dovrebbe essere eseguito in O (n log (n))

risposta data 20.05.2015 - 08:43

fonte

Leggi altre domande sui tag c# big-o

Come dovrei introdurre uno standard di codifica per il mio team? UML: processore di coda in un diagramma di sequenza

score 12 · Accepted Answer

Big O è lo stesso, poiché entrambi i codici (nel caso peggiore) devono eseguire un confronto per ciascuna combinazione di elementi di entrambi gli elenchi. Ad esempio, se non ci sono corrispondenze tra gli elenchi, nessuna ottimizzazione nell'implementazione di Linq eviterà di dover controllare tutti gli elementi.

Ma hey, non vuoi davvero sapere di big-O, vero? Vuoi sapere se il secondo è più veloce . La risposta è sì, la soluzione basata su linq è più veloce (purché sia abbastanza grande) perché deve solo eseguire il controllo fino a quando non viene trovata la prima corrispondenza nell'elenco, mentre la soluzione nested-for deve sempre visitare tutti gli elementi . Il metodo Where non esegue la scansione dell'intero elenco immediatamente, ma rater crea un iteratore pigro. Il metodo FirstOrDefault esegue quindi l'iteratore finché non viene trovata la prima corrispondenza, il che significa che nel caso comune non deve attraversare l'intera lista. Ovviamente c'è un sovraccarico nella soluzione Linq, quindi se n è abbastanza basso il ciclo nested-for sarà più veloce.

Puoi controllare tu stesso la fonte: link

(Ma se hai aggiunto un break nel primo campione, i due codici sarebbero semanticamente equivalenti, e il primo sarebbe più veloce a causa di un minore overhead.)