C# Array or Dictionary?

Question

¿Quería saber si la matriz C# tiene una velocidad de acceso constante?
Necesito almacenar 1000 elementos en una matriz estática, que se inicializarán durante el inicio del servidor. Esta matriz se usará solo de forma inmediata, , por lo que no habrá cambios en la matriz.
Debo usar una matriz simple C# (nueva MyClass []) o diccionario en su lugar.

Soy realmente nuevo en C# y trato de entender cómo funciona el acceso a las matrices C#.
¿Se pueden comparar con matrices de C++ por velocidad?

Answer 1

La mejor opción depende de cómo necesite acceder a los elementos.

Si desea acceder a ellos por índice, utilice una matriz. Las matrices en C# tienen velocidad de acceso constante, y son muy similares a una matriz de C++ en términos de velocidad de acceso.

Diccionarios, sin embargo, tienen un acceso muy rápido (el Item propertyenfoques O (1) tiempo de acceso, sino que depende de lo bien que la aplicación de una clave almacenada tiene para GetHashCode). Si necesita buscar sus artículos en función de un valor clave y no por índice, entonces el diccionario sería apropiado en su lugar.

Answer 2

Un acceso de matriz en C# es una operación de índice simple, mientras que un diccionario es una búsqueda de tablas hash. Las matrices son comparables a las matrices de C++ a excepción de una pequeña sobrecarga de verificación de límites realizada por el idioma.

Si no va a cambiar los contenidos, utilizaría una matriz para el tamaño de los datos, en todo caso.

Answer 3

Sí, si conoce el índice, la velocidad es constante O (1), muy similar a una búsqueda en un diccionario respaldado por hashtable (por ejemplo, el diccionario <>).

Si no se conoce el índice, deberá realizar una búsqueda (lineal si los elementos no están clasificados O (n) o binarios si son O (log n)).

Dicho esto, en términos reales la búsqueda de matriz será más rápida porque una búsqueda de tabla doble es dos operaciones: calcule el hash de la clave para obtener un índice y recuperar el valor de una matriz interna en ese índice.

También tenga en cuenta que a si el código hash de la clave está mal implementado, las propiedades mágicas de la tabla flotante se evaporan rápidamente y, en el peor de los casos (donde cada clave tiene el mismo código hash) terminará con una compleja lista enlazada que cada búsqueda será una búsqueda lineal a un costo de O (n). ¡Comprueba esos códigos hash!

Answer 4

Depende de la forma en que vaya a obtener elementos de la matriz. Si va a obtener elementos por posiciones (índice) en la matriz, la matriz será más rápida (o al menos no más lenta que el diccionario). Si va a buscar elementos en la matriz, el diccionario será más rápido.

Answer 5

Aquí hay algo que acabo de escribir. Se puede extender con bastante facilidad para diferentes estructuras de datos. Incluye una clase para cada estructura de datos (actualmente solo una matriz y un diccionario).

El código de cliente está a sólo dos líneas:

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

El resto del código es:

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

Una actualización sobre el último mensaje el código ... ahora incluye una clase para la estructura de la lista de datos. He eliminado algunos errores del código. Debería ofrecer los resultados correctos ahora.

Parece que para las estructuras de datos unidimensionales, una estructura de lista en realidad puede ser más rápida que una matriz. Pero para estructuras bidimensionales, como en el siguiente código, las matrices son sustancialmente más rápidas que las listas, y significativamente más rápidas que los diccionarios.

Pero todo depende de para qué desee utilizar las estructuras de datos. Para conjuntos de datos relativamente pequeños, los diccionarios y listas a menudo son estructuras más convenientes para usar.

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