C# Array lub Dictionary?

Question

Chciałem wiedzieć, że tablica C# ma stałą prędkość dostępu?
Potrzebuję przechowywać 1000 elementów w tablicy statycznej, która zostanie zainicjowana podczas uruchamiania serwera. Ta tablica będzie używana tylko do odczytu, , więc nie będzie zmian w tablicy.
Czy powinienem użyć prostej tablicy C# (nowy MyClass []) lub Słownika.

Jestem naprawdę nowy w C# i próbuję zrozumieć, jak działa dostęp do tablic C#.
Czy można je porównywać z tablicami C++ z prędkością?

Answer 1

Najlepszy wybór zależy od sposobu uzyskania dostępu do elementów.

Jeśli chcesz uzyskać do nich dostęp poprzez indeks, użyj tablicy. Tablice w języku C# mają stałą prędkość dostępu i są bardzo podobne do tablicy C++ pod względem szybkości dostępu.

Słowniki mają jednak bardzo szybki dostęp (the Item propertyzbliża O (1) czasu dostępu, ale zależy od tego, jak dobrze z implementacji zapisany klucz ma dla GetHashCode). Jeśli chcesz sprawdzić swoje produkty na podstawie wartości klucza, a nie według indeksu, słownik będzie odpowiedni.

Answer 2

Dostęp do tablicy w języku C# jest prostą operacją indeksu, podczas gdy słownik jest hash sprawdzania tabeli. Tablice są porównywalne z tablicami C++, z wyjątkiem niewielkich narzutów sprawdzania granic wykonywanych przez język.

Jeśli nie zamierzasz zmieniać zawartości, użyłbym tablicy dla rozmiaru danych, jeśli nic innego.

Answer 3

Tak, jeśli znasz indeks, prędkość jest stała O (1), podobnie jak wyszukiwanie w słowniku z funkcją hashtable (np. Słownik <>).

Jeśli indeks nie jest znany, należy przeprowadzić wyszukiwanie (liniowe, jeśli pozycje są nieposortowane O (n) lub binarne, jeśli są O (log n)).

Mówiąc w skrócie, wyszukiwanie tablicy będzie szybsze, ponieważ wyszukiwanie hashtable to dwie operacje: oblicz wartość skrótu klucza, aby uzyskać indeks i pobrać wartość z wewnętrznej tablicy w tym indeksie.

Należy również zauważyć, że jeśli a hashcode klucza jest źle zaimplementowany, magiczne właściwości hashtable szybko wyparują i, w najgorszym przypadku (gdzie każdy klucz ma ten sam kod skrótu), pojawi się skomplikowana połączona lista w co każde wyszukiwanie będzie liniowym wyszukiwaniem kosztem O (n). Dokładnie sprawdź te hashkody!

Answer 4

To zależy od sposobu, w jaki otrzymasz elementy z tablicy. Jeśli chcesz uzyskać elementy według pozycji (indeksu) w tablicy, to tablica będzie szybsza (lub przynajmniej wolniejsza od słownika). Jeśli zamierzasz wyszukiwać elementy w tablicy, to słownik będzie szybszy.

Answer 5

Oto coś, co właśnie napisałem. Można go łatwo rozszerzyć dla różnych struktur danych. Obejmuje klasę dla każdej struktury danych (obecnie tylko tablica i słownik).

Kod klienta jest zaledwie dwie linie:

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

Reszta kodu jest:

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

Aktualizacja ostatniego postu ... kod zawiera teraz klasę dla struktury lista danych. Usunąłem niektóre błędy z kodu. Teraz powinien przynieść właściwe rezultaty.

Wydaje się, że w przypadku jednowymiarowych struktur danych struktura listy może faktycznie być szybsza niż tablica. Ale w przypadku struktur dwuwymiarowych, jak w poniższym kodzie, tablice są znacznie szybsze niż listy i znacznie szybsze niż słowniki.

Wszystko zależy od tego, do czego chcesz użyć struktur danych. W przypadku stosunkowo małych zbiorów danych słowniki i listy są często wygodniejszymi strukturami do wykorzystania.

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