c# - length - python array count




Array.Count() molto più lento di List.Count() (3)

Quando si utilizza il metodo di estensione di IEnumerable<T> Count() , una matrice è almeno due volte più lenta di una lista.

Function                      Count()
List<int>                     2,299
int[]                         6,903

Da dove viene la differenza?

Capisco che entrambi chiamino la proprietà Count di ICollection :

Se il tipo di sorgente implementa ICollection, tale implementazione viene utilizzata per ottenere il conteggio degli elementi. Altrimenti, questo metodo determina il conteggio.

Per la lista restituisce List<T>.Count e per array, Array.Length . Inoltre, Array.Length dovrebbe essere più veloce di List<T>.Count .

Indice di riferimento:

class Program
{
    public const long Iterations = (long)1e8;

    static void Main()
    {
        var list = new List<int>(){1};
        var array = new int[1];
        array[0] = 1;

        var results = new Dictionary<string, TimeSpan>();
        results.Add("List<int>", Benchmark(list, Iterations));
        results.Add("int[]", Benchmark(array, Iterations));

        Console.WriteLine("Function".PadRight(30) + "Count()");
        foreach (var result in results)
        {
            Console.WriteLine("{0}{1}", result.Key.PadRight(30), Math.Round(result.Value.TotalSeconds, 3));
        }
        Console.ReadLine();
    }

    public static TimeSpan Benchmark(IEnumerable<int> source, long iterations)
    {
        var countWatch = new Stopwatch();
        countWatch.Start();
        for (long i = 0; i < iterations; i++) source.Count();
        countWatch.Stop();

        return countWatch.Elapsed;
    }
}

Modificare:

leppie risposte di leppie e Knaģis sono piuttosto sorprendenti, ma voglio aggiungere un commento.
Come ha detto Jon Skeet:

Esistono effettivamente due blocchi equivalenti, solo test per i diversi tipi di interfaccia di raccolta e l'utilizzo di quello che trova per primo (se esiste). Non so se i test di implementazione .NET per ICollection o ICollection <T> per primi - potrei testarlo implementando entrambe le interfacce ma restituendo conteggi diversi da ciascuno, ovviamente, ma probabilmente è eccessivo. Non importa per collezioni ben educate oltre alla leggera differenza di prestazioni - vogliamo testare prima l'interfaccia "più probabile", che credo sia quella generica.

Quello generico potrebbe essere il più probabile, ma se si invertono i due, vale a dire chiamare il cast non generico prima di quello generico, Array.Count () diventa un po 'più veloce di List.Count (). D'altra parte, la versione non generica è più lenta per List.

Buono a sapersi se qualcuno vuole chiamare Count() in un ciclo iterazioni 1e8!

Function       ICollection<T> Cast     ICollection Cast
List                1,268                   1,738         
Array               5,925                   1,683

Analisi di profilazione a 32 bit (tutto in ms, solo bit interessanti, inlining JIT disabilitato):

Name    Count   'Inc Time'  'Ex Time'   'Avg Inc Time'  'Avg Ex Time'
System.Linq.Enumerable::Count(<UNKNOWN>):int32 <System.Int32>   
        20000000    13338.38    7830.49 0.0007  0.0004
System.SZArrayHelper::get_Count():int32 <System.Int32>  
        10000000    4063.9      2651.44 0.0004  0.0003
System.Collections.Generic.List<System.Int32>::get_Count():int32    
        10000000    1443.99     1443.99 0.0001  0.0001
System.Runtime.CompilerServices.JitHelpers::UnsafeCast(Object):System.__Canon <System.__Canon>  
        10000004    1412.46     1412.46 0.0001  0.0001

System.SZArrayHelper::get_Count() sembra chiamare System.Runtime.CompilerServices.JitHelpers::UnsafeCast per il caso dell'array.

Per l'elenco, List<int>.Count restituisce semplicemente la dimensione.

Inc time è un costo che include le chiamate figlio. Ex time è il costo del solo metodo body.

Quando l'inlining è disabilitato, Array.Count() è due volte più lento.

Potrebbe essere dovuto al fatto menzionato la risposta ora cancellata. Sembrerebbe che gli attributi applicati ( ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success) e SecuritySafeCritical ) impediscano al runtime di inlining della chiamata, quindi la grande differenza (38 volte più lento nel mio caso in modalità 32 bit).

Per dare un profilo a te stesso:

Ottieni https://github.com/leppie/IronScheme/raw/master/IronScheme/tools/IronScheme.Profiler.x86.dll Esegui l'app (solo x86 build) come:

regsvr32 IronScheme.Profiler.x86.dll
set COR_PROFILER={9E2B38F2-7355-4C61-A54F-434B7AC266C0}
set COR_ENABLE_PROFILING=1
ConsoleApp1.exe

Quando l'app termina, viene creato un file report.tab che può quindi essere utilizzato in Excel.


Il motivo è che Enumerable.Count<T>() esegue un cast su ICollection<T> per recuperare il conteggio sia dall'elenco che dall'array.

Utilizzando questo codice di esempio:

public static int Count<TSource>(IEnumerable<TSource> source)
{
    ICollection<TSource> collection = source as ICollection<TSource>;
    if (collection != null)
    {
        return 1; // collection.Count;
    }
}

puoi determinare che il cast impiega molto più tempo per l'array, infatti la maggior parte del tempo impiegato per il conteggio proviene da questo cast:

Function                      Count()
List<int>                     1,575
int[]                         5,069

La chiave potrebbe essere questa affermazione dalla documentation (sottolineatura mia):

In .NET Framework versione 2.0, la classe Array implementa System.Collections.Generic.IList, System.Collections.Generic.ICollection e System.Collections.Generic.IEnumerable interfacce generiche. Le implementazioni vengono fornite agli array in fase di esecuzione e pertanto non sono visibili agli strumenti di documentazione. Di conseguenza, le interfacce generiche non vengono visualizzate nella sintassi della dichiarazione per la classe Array e non vi sono argomenti di riferimento per i membri dell'interfaccia accessibili solo mediante il cast di una matrice al tipo di interfaccia generico (implementazioni esplicite dell'interfaccia).


Sto postando questo, non come risposta, ma per fornire un ambiente più testabile.

Ho preso una copia dell'attuale implementazione di Enumerable<T>.Count() e Enumerable<T>.Count() cambiato il programma di test originale per usarlo, così le persone possono Enumerable<T>.Count() single step nel debugger.

Se si esegue una versione di rilascio del codice qui sotto, si avranno tempi simili all'OP.

Sia per List<T> che per int[] il primo cast assegnato a is2 sarà non nullo, quindi verrà chiamato.

Quindi sembrerebbe che la differenza provenga dall'implementazione interna di .Count .

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        public const long Iterations = (long)1e8;

        static void Main()
        {
            var list = new List<int>() { 1 };
            var array = new int[1];
            array[0] = 1;

            var results = new Dictionary<string, TimeSpan>();
            results.Add("int[]", Benchmark(array, Iterations));
            results.Add("List<int>", Benchmark(list, Iterations));

            Console.WriteLine("Function".PadRight(30) + "Count()");
            foreach (var result in results)
            {
                Console.WriteLine("{0}{1}", result.Key.PadRight(30), Math.Round(result.Value.TotalSeconds, 3));
            }
            Console.ReadLine();
        }

        public static TimeSpan Benchmark(IEnumerable<int> source, long iterations)
        {
            var countWatch = new Stopwatch();
            countWatch.Start();
            for (long i = 0; i < iterations; i++) Count(source);
            countWatch.Stop();

            return countWatch.Elapsed;
        }

        public static int Count<TSource>(IEnumerable<TSource> source)
        {
            ICollection<TSource> is2 = source as ICollection<TSource>;

            if (is2 != null)
                return is2.Count;  // This is executed for int[] AND List<int>.

            ICollection is3 = source as ICollection;

            if (is3 != null)
                return is3.Count;

            int num = 0;

            using (IEnumerator<TSource> enumerator = source.GetEnumerator())
            {
                while (enumerator.MoveNext())
                    num++;
            }

            return num;
        }
    }
}

Date queste informazioni, possiamo semplificare il test per concentrarci solo sulle differenze temporali tra List.Count e Array.Count :

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            int dummy = 0;
            int count = 1000000000;

            var array = new int[1] as ICollection<int>;
            var list = new List<int> {0};

            var sw = Stopwatch.StartNew();

            for (int i = 0; i < count; ++i)
                dummy += array.Count;

            Console.WriteLine("Array elapsed = " + sw.Elapsed);

            dummy = 0;
            sw.Restart();

            for (int i = 0; i < count; ++i)
                dummy += list.Count;

            Console.WriteLine("List elapsed = " + sw.Elapsed);

            Console.ReadKey(true);
        }
    }
}

Il codice precedente fornisce i seguenti risultati per un'esecuzione di build di rilascio all'esterno del debugger:

Array elapsed = 00:00:02.9586515
List elapsed = 00:00:00.6098578

A questo punto, ho pensato a me stesso "sicuramente possiamo ottimizzare Count() per riconoscere T[] e restituire .Length diretta. Così ho cambiato l'implementazione di Count() come segue:

public static int Count<TSource>(IEnumerable<TSource> source)
{
    var array = source as TSource[];

    if (array != null)        // Optimised for arrays.
        return array.Length;  // This is executed for int[] 

    ICollection<TSource> is2 = source as ICollection<TSource>;

    if (is2 != null)
        return is2.Count;  // This is executed for List<int>.

    ICollection is3 = source as ICollection;

    if (is3 != null)
        return is3.Count;

    int num = 0;

    using (IEnumerator<TSource> enumerator = source.GetEnumerator())
    {
        while (enumerator.MoveNext())
            num++;
    }

    return num;
}

Sorprendentemente, anche dopo aver apportato questa modifica, gli array erano ancora più lenti sul mio sistema, nonostante i non-array dovessero fare il cast extra!

I risultati (build di rilascio) per me erano:

Function                      Count()
List<int>                     1.753
int[]                         2.304

Sono a una perdita totale per spiegare questo ultimo risultato ...







ienumerable