C# Array ou Dictionnaire?

Question

Je voulais savoir si le tableau C# a une vitesse d'accès constante?
Je dois stocker 1000 éléments dans un tableau statique, qui sera initialisé au démarrage du serveur. Ce tableau sera utilisé en lecture seule, , donc il n'y aura pas de changements dans le tableau. Doit-on utiliser un simple tableau C# (new MyClass []) ou Dictionary à la place.

Je suis vraiment nouveau pour C# et essayer de comprendre comment fonctionne l'accès C# arrays.
Peuvent-ils être comparés aux tableaux C++ par la vitesse?

Answer 1

Le meilleur choix dépend de la façon dont vous devez accéder aux éléments.

Si vous voulez y accéder par index, puis utilisez un tableau. Les tableaux en C# ont une vitesse d'accès constante et sont très similaires à un tableau C++ en termes de vitesse d'accès.

Dictionnaires, cependant, ont un accès très rapide (le Item propertyapproches O (1) le temps d'accès, mais dépend de la qualité d'une mise en œuvre de la clé stockée a pour GetHashCode). Si vous devez rechercher vos éléments en fonction d'une valeur de clé et non par index, le dictionnaire sera approprié à la place.

Answer 2

Un accès au tableau en C# est une opération d'index simple, alors qu'un dictionnaire est une table de hachage recherche. Les tableaux sont comparables aux tableaux C++, à l'exception d'un petit surcoût de vérification des limites effectué par le langage.

Si vous n'êtes pas va être changer le contenu, j'utiliser un tableau pour la taille des données, si rien d'autre.

Answer 3

Oui, si vous connaissez l'index, la vitesse est la constante O (1), tout comme une recherche dans un dictionnaire soutenu par une table de hachage (par exemple le dictionnaire <>).

Si l'indice est pas connu, vous devrez effectuer une recherche (linéaire si les éléments sont O non triés (n) ou binaire si elles sont O (log n)). Cela dit, en termes réels, la recherche de tableau sera plus rapide car une recherche de hashtable est deux opérations: calculer le hachage de la clé pour obtenir un index et extraire la valeur d'un tableau interne à cet index. Notez également que si le hashcode de la clé est mal implémenté, les propriétés magiques de la table de hachage s'évaporent rapidement et, dans le pire des cas (où chaque clé a le même hash), vous obtiendrez une liste chaînée élaborée dans que chaque recherche sera une recherche linéaire au coût de O (n). Vérifiez ces hashcodes!

Answer 4

Cela dépend de la façon dont vous allez obtenir les éléments du tableau. Si vous allez obtenir des éléments par des positions (index) dans le tableau, alors le tableau sera plus rapide (ou du moins pas plus lent que le dictionnaire). Si vous allez chercher des éléments dans le tableau, le dictionnaire sera plus rapide.

Answer 5

Voici quelque chose que je viens d'écrire. Il peut être étendu assez facilement pour différentes structures de données. Il inclut une classe pour chaque structure de données (actuellement juste array et dictionary).

Le code client est à seulement deux lignes:

IDataStructureTimeTestHandler iDataStructureTimeTestHandler = new DataStructureTimeTestHandler(); iDataStructureTimeTestHandler.PerformTimeTestsForDataStructures();

Le reste du code est:

public interface IStopwatchType 
{ 
    TimeSpan TimeElapsed { get; } 
    void StartTimeTest(); 
    void EndTimeTest(); 
} 

public class StopwatchType : TailoredType, IStopwatchType 
{ 
    private Stopwatch stopwatch; 
    private TimeSpan timeElapsed; 
    public TimeSpan TimeElapsed 
    { 
     get 
     { 
      return timeElapsed; 
     } 
    } 

    public StopwatchType() 
    { 
    } 

    public void StartTimeTest() 
    { 
     ClearGarbage(); 
     stopwatch = Stopwatch.StartNew(); 
    } 

    public void EndTimeTest() 
    { 
     stopwatch.Stop(); 
     timeElapsed = stopwatch.Elapsed; 
    } 

    private void ClearGarbage() 
    { 
     GC.Collect(); 
     GC.WaitForPendingFinalizers();    
    } 
} 

public interface IDataStructureTimeTestHandler 
{ 
    void PerformTimeTestsForDataStructures(); 
} 

public class DataStructureTimeTestHandler : IDataStructureTimeTestHandler 
{ 
    private IDataStructureTimeTest[] iDataStructureTimeTests; 
    private TimeSpan[,] testsResults; 


    public DataStructureTimeTestHandler() 
    { 
     iDataStructureTimeTests = new IDataStructureTimeTest[2]; 
     testsResults = new TimeSpan[4, 2]; 
    } 

    public void PerformTimeTestsForDataStructures() 
    { 
     iDataStructureTimeTests[0] = new ArrayTimeTest(); 
     iDataStructureTimeTests[1] = new DictionaryTimeTest(); 
     for (int i = 0; i < iDataStructureTimeTests.Count(); i++) 
     { 
      testsResults[0, i] = iDataStructureTimeTests[0].InstantiationTime(); 
      testsResults[1, i] = iDataStructureTimeTests[0].WriteTime(); 
      testsResults[2, i] = iDataStructureTimeTests[0].ReadTime(LoopType.For); 
      testsResults[3, i] = iDataStructureTimeTests[0].ReadTime(LoopType.Foreach); 
     } 
    } 
} 

public enum LoopType 
{ 
    For, 
    Foreach 
} 

public interface IDataStructureTimeTest 
{ 
    TimeSpan InstantiationTime(); 
    TimeSpan WriteTime(); 
    TimeSpan ReadTime(LoopType loopType); 
} 

protected abstract class DataStructureTimeTest 
{ 
    protected IStopwatchType iStopwatchType; 
    protected long numberOfElements;   
    protected int number; 
    protected delegate void TimeTestDelegate(); 


    protected DataStructureTimeTest() 
    { 
     iStopwatchType = new StopwatchType(); 
     numberOfElements = 100000; 
    } 

    protected void TimeTestDelegateMethod(TimeTestDelegate timeTestMethod) 
    { 
     iStopwatchType.StartTimeTest(); 
     timeTestMethod(); 
     iStopwatchType.EndTimeTest(); 
    } 
} 

public class ArrayTimeTest : DataStructureTimeTest, IDataStructureTimeTest 
{ 
    private int[] integerArray; 


    public TimeSpan InstantiationTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void InstantiationTime_() 
    { 
     integerArray = new int[numberOfElements]; 
    } 

    public TimeSpan WriteTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void WriteTime_() 
    { 
     number = 0; 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      integerArray[i] = number; 
      number++; 
     } 
    } 

    public TimeSpan ReadTime(LoopType dataStructureLoopType) 
    { 
     switch (dataStructureLoopType) 
     { 
      case LoopType.For: 
       ReadTimeFor(); 
       break; 
      case LoopType.Foreach: 
       ReadTimeForEach(); 
       break; 
     } 
     return iStopwatchType.TimeElapsed; 
    } 

    private void ReadTimeFor() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_)); 
    } 

    private void ReadTimeFor_() 
    { 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      number = integerArray[i]; 
     } 
    } 

    private void ReadTimeForEach() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_)); 
    } 

    private void ReadTimeForEach_() 
    { 
     foreach (int i in integerArray) 
     { 
      number = i; 
     } 
    } 
} 

public class DictionaryTimeTest : DataStructureTimeTest, IDataStructureTimeTest 
{ 
    private Dictionary<int, int> integerDictionary; 


    public TimeSpan InstantiationTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void InstantiationTime_() 
    { 
     integerDictionary = new Dictionary<int, int>(); 
    } 

    public TimeSpan WriteTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void WriteTime_() 
    { 
     number = 0; 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      integerDictionary.Add(number, number); 
      number++; 
     } 
    } 

    public TimeSpan ReadTime(LoopType dataStructureLoopType) 
    { 
     switch (dataStructureLoopType) 
     { 
      case LoopType.For: 
       ReadTimeFor(); 
       break; 
      case LoopType.Foreach: 
       ReadTimeForEach(); 
       break; 
     } 
     return iStopwatchType.TimeElapsed; 
    } 

    private void ReadTimeFor() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_)); 
    } 

    private void ReadTimeFor_() 
    { 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      number = integerDictionary[i]; 
     } 
    } 

    private void ReadTimeForEach() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_)); 
    } 

    private void ReadTimeForEach_() 
    { 
     foreach (KeyValuePair<int, int> i in integerDictionary) 
     { 
      number = i.Value; 
     } 
    } 
} 

Answer 6

Une mise à jour sur le dernier message ... le code inclut désormais une classe pour la structure de données de liste. J'ai supprimé quelques bogues du code. Il devrait fournir les bons résultats maintenant.

Il semble que pour les structures de données unidimensionnelles, une structure de liste peut en fait être plus rapide qu'un tableau. Mais pour les structures bidimensionnelles, comme dans le code ci-dessous, les tableaux sont sensiblement plus rapides que les listes, et significativement plus rapides que les dictionnaires.

Mais tout dépend de ce que vous voulez utiliser les structures de données. Pour les ensembles de données relativement petits, les dictionnaires et les listes sont souvent des structures plus pratiques à utiliser.

public interface IDataStructureTimeTestHandler 
{ 
    void PerformTimeTestsForDataStructures(); 
} 

public class DataStructureTimeTestHandler : IDataStructureTimeTestHandler 
{ 
    // Example of use: 
    //IDataStructureTimeTestHandler iDataStructureTimeTestHandler = new DataStructureTimeTestHandler(); 
    //iDataStructureTimeTestHandler.PerformTimeTestsForDataStructures(); 

    private IDataStructureTimeTest[] iDataStructureTimeTests; 
    private TimeSpan[,] testsResults; 

    public DataStructureTimeTestHandler() 
    { 
     iDataStructureTimeTests = new IDataStructureTimeTest[3]; 
     testsResults = new TimeSpan[4, 3]; 
    } 

    public void PerformTimeTestsForDataStructures() 
    { 
     iDataStructureTimeTests[0] = new ArrayTimeTest(); 
     iDataStructureTimeTests[1] = new DictionaryTimeTest(); 
     iDataStructureTimeTests[2] = new ListTimeTest(); 
     for (int i = 0; i < iDataStructureTimeTests.Count(); i++) 
     { 
      testsResults[0, i] = iDataStructureTimeTests[i].InstantiationTime(); 
      testsResults[1, i] = iDataStructureTimeTests[i].WriteTime(); 
      testsResults[2, i] = iDataStructureTimeTests[i].ReadTime(LoopType.For); 
      testsResults[3, i] = iDataStructureTimeTests[i].ReadTime(LoopType.Foreach); 
     } 
    } 
} 

public enum LoopType 
{ 
    For, 
    Foreach 
} 

public interface IDataStructureTimeTest 
{ 
    TimeSpan InstantiationTime(); 
    TimeSpan WriteTime(); 
    TimeSpan ReadTime(LoopType loopType); 
} 

public abstract class DataStructureTimeTest 
{ 
    protected IStopwatchType iStopwatchType; 
    protected long numberOfElements;   
    protected int number; 
    protected delegate void TimeTestDelegate(); 


    protected DataStructureTimeTest() 
    { 
     iStopwatchType = new StopwatchType(); 
     numberOfElements = 10000000; 
    } 

    protected void TimeTestDelegateMethod(TimeTestDelegate timeTestMethod) 
    { 
     iStopwatchType.StartTimeTest(); 
     timeTestMethod(); 
     iStopwatchType.EndTimeTest(); 
    } 
} 

public class ArrayTimeTest : DataStructureTimeTest, IDataStructureTimeTest 
{ 
    private int[,] integerArray; 


    public TimeSpan InstantiationTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void InstantiationTime_() 
    { 
     integerArray = new int[numberOfElements, 2]; 
    } 

    public TimeSpan WriteTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void WriteTime_() 
    { 
     number = 0; 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      integerArray[i, 0] = number; 
      integerArray[i, 1] = number; 
      number++; 
     } 
    } 

    public TimeSpan ReadTime(LoopType dataStructureLoopType) 
    { 
     switch (dataStructureLoopType) 
     { 
      case LoopType.For: 
       ReadTimeFor(); 
       break; 
      case LoopType.Foreach: 
       ReadTimeForEach(); 
       break; 
     } 
     return iStopwatchType.TimeElapsed; 
    } 

    private void ReadTimeFor() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_)); 
    } 

    private void ReadTimeFor_() 
    { 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      number = integerArray[i, 1]; 
     } 
    } 

    private void ReadTimeForEach() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_)); 
    } 

    private void ReadTimeForEach_() 
    { 
     foreach (int i in integerArray) 
     { 
      number = i; 
     } 
    } 
} 

public class DictionaryTimeTest : DataStructureTimeTest, IDataStructureTimeTest 
{ 
    private Dictionary<int, int> integerDictionary; 


    public TimeSpan InstantiationTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void InstantiationTime_() 
    { 
     integerDictionary = new Dictionary<int, int>(); 
    } 

    public TimeSpan WriteTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void WriteTime_() 
    { 
     number = 0; 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      integerDictionary.Add(number, number); 
      number++; 
     } 
    } 

    public TimeSpan ReadTime(LoopType dataStructureLoopType) 
    { 
     switch (dataStructureLoopType) 
     { 
      case LoopType.For: 
       ReadTimeFor(); 
       break; 
      case LoopType.Foreach: 
       ReadTimeForEach(); 
       break; 
     } 
     return iStopwatchType.TimeElapsed; 
    } 

    private void ReadTimeFor() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_)); 
    } 

    private void ReadTimeFor_() 
    { 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      number = integerDictionary[i]; 
     } 
    } 

    private void ReadTimeForEach() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_)); 
    } 

    private void ReadTimeForEach_() 
    { 
     foreach (KeyValuePair<int, int> i in integerDictionary) 
     { 
      number = i.Key; 
      number = i.Value; 
     } 
    } 
} 

public class ListTimeTest : DataStructureTimeTest, IDataStructureTimeTest 
{ 
    private List<int[]> integerList; 


    public TimeSpan InstantiationTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(InstantiationTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void InstantiationTime_() 
    { 
     integerList = new List<int[]>(); 
    } 

    public TimeSpan WriteTime() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(WriteTime_)); 
     return iStopwatchType.TimeElapsed; 
    } 

    private void WriteTime_() 
    { 
     number = 0; 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      integerList.Add(new int[2] { number, number }); 
      number++; 
     } 
    } 

    public TimeSpan ReadTime(LoopType dataStructureLoopType) 
    { 
     switch (dataStructureLoopType) 
     { 
      case LoopType.For: 
       ReadTimeFor(); 
       break; 
      case LoopType.Foreach: 
       ReadTimeForEach(); 
       break; 
     } 
     return iStopwatchType.TimeElapsed; 
    } 

    private void ReadTimeFor() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeFor_)); 
    } 

    private void ReadTimeFor_() 
    { 
     for (int i = 0; i < numberOfElements; i++) 
     { 
      number = integerList[i].ElementAt(1); 
     } 
    } 

    private void ReadTimeForEach() 
    { 
     TimeTestDelegateMethod(new TimeTestDelegate(ReadTimeForEach_)); 
    } 

    private void ReadTimeForEach_() 
    { 
     foreach (int[] i in integerList) 
     { 
      number = i.ElementAt(1); 
     } 
    } 
}