Должен ли я использовать словарь или список с поиском linq?

Question

Я использую C# для создания сетки, состоящей из ячеек. Ячейки будут использовать «sbyte X» и «sbyte Y» для определения местоположения в сетке (0,0 слева вверху). Ячейка является классом и сохранит свое собственное местоположение в сетке.

мне интересно, если это было бы лучше использовать:

List<Cell> CellList 
//.... 
Cell thisCell = CellList.First(cell => cell.X = thisX && cell.Y = thisY); 

или использовать словарь:

Dictionary<sbyte[], Cell> CellList 
//.... 
Cell thisCell = CellList[new sbyte[2] { thisX , thisY }]; 

Кроме того, коллекция клеток, как правило, от 25 до 50 в каждом направление; поэтому 625 - 2500 записей. Мне интересно знать о скорости и проблемах с памятью. Вероятно, в то же время будет загружено в общей сложности 7 сеток, и каждый цикл каждой сетки будет обрабатываться в каждом цикле.

Answer 1

Второй подход не будет работать, поскольку массивы не переопределяют GetHashCode и Equals таким образом, чтобы использовать данные, хранящиеся в массиве. Однако первый подход был бы медленным для коллекций с большим количеством ячеек из-за линейного поиска.

Лучше было бы использовать Tuple<sbyte,sbyte> вместо массива:

Dictionary<Tuple<sbyte,sbyte>, Cell> CellList; 
//.... 
Cell thisCell = CellList[Tuple.Create(thisX , thisY)]; 

Answer 2

Словарь является гораздо более эффективным, так как он использует HashTable внутренне, в то время как с помощью списка будет искать хоть каждый элемент в список каждый раз, когда вы хотите извлечь ячейку.

Однако я бы рекомендовал использовать Tuple<sbyte, sbyte> в качестве ключа вместо массива:

Dictionary<Tuple<sbyte, sbyte>, Cell> CellList; 
Cell thisCell = CellList[Tuple.Create(thisX, thisY)]; 

Или, возможно, создать свой собственный тип ключа:

struct Point 
{ 
    public sbyte X { get; private set; } 
    public sbyte Y { get; private set; } 

    public Point(sbyte x, sbyte y) 
    { 
     this.X = x; 
     this.Y = y; 
    } 

    public override int GetHashCode() 
    { 
     return this.X << 8 | this.Y; 
    } 

    ... 
} 

Dictionary<Point, Cell> CellList 
Cell thisCell = CellList[new Point(thisX, thisY)]; 

Answer 3

раз сетка была созданный размер останется неизменным (все сетки будут одинакового размера), а объект, связанный с каждой ячейкой, не будет изменение

Тогда тем более эффективным будет многомерный массив:

// Creates array 
Cell[,] array = new Cell[20, 50]; 

// Access to items (get item by X/Y indexes) 
array[10, 12] = ...; 

---

Удивление, как Cell [,] сравнивает словарю, Cell> подход

Cell[,] Безразлично Не нужно выполнять поиск HashTable каждый раз, когда вы хотите получить доступ к элементу, поэтому он более эффективен.Давайте писать некоторые тесты, чтобы дать некоторые идеи (обратите внимание, что это, вероятно, не самый лучший тест можно было бы написать, но, по крайней мере, это дает некоторые идеи):

internal class Program 
{ 
    private static void Main(string[] args) 
    { 
     Stopwatch sw = Stopwatch.StartNew(); 
     int[,] array = null; 
     for (int i = 0; i < 1000; i++) 
     { 
      array = ArrayInit(); 
     } 

     sw.Stop(); 
     Console.WriteLine("ArrayInit: {0}", sw.ElapsedMilliseconds); 

     sw = Stopwatch.StartNew(); 
     Dictionary<Tuple<sbyte, sbyte>, int> dic = null; 
     for (int i = 0; i < 1000; i++) 
     { 
      dic = DictionaryInit(); 
     } 

     sw.Stop(); 
     Console.WriteLine("DictionaryInit: {0}", sw.ElapsedMilliseconds); 

     sw = Stopwatch.StartNew(); 
     int res; 
     for (int i = 0; i < 1000000; i++) 
     { 
      res = ArrayLookup(array); 
     } 

     sw.Stop(); 
     Console.WriteLine("ArrayLookup: {0}", sw.ElapsedMilliseconds); 

     sw = Stopwatch.StartNew(); 
     for (int i = 0; i < 1000000; i++) 
     { 
      res = DictionaryLookup(dic); 
     } 

     sw.Stop(); 
     Console.WriteLine("DictionaryLookup: {0}", sw.ElapsedMilliseconds); 

     Console.Read(); 
    } 

    private static int[,] ArrayInit() 
    { 
     int[,] array = new int[50, 50]; 
     for (sbyte x = 0; x < 50; x++) 
     { 
      for (sbyte y = 0; y < 50; y++) 
      { 
       array[x, y] = x * y; 
      } 
     } 

     return array; 
    } 

    private static int ArrayLookup(int[,] array) 
    { 
     return array[12, 12]; 
    } 

    private static int DictionaryLookup(Dictionary<Tuple<sbyte, sbyte>, int> dic) 
    { 
     return dic[new Tuple<sbyte, sbyte>(12, 12)]; 
    } 

    private static Dictionary<Tuple<sbyte, sbyte>, int> DictionaryInit() 
    { 
     Dictionary<Tuple<sbyte, sbyte>, int> dic = new Dictionary<Tuple<sbyte, sbyte>, int>(); 
     for (sbyte x = 0; x < 50; x++) 
     { 
      for (sbyte y = 0; y < 50; y++) 
      { 
       Tuple<sbyte, sbyte> t = new Tuple<sbyte, sbyte>(x, y); 
       dic[t] = x * y; 
      } 
     } 

     return dic; 
    } 

Результаты:

ArrayInit: 25

DictionaryInit: 528

ArrayLookup: 7

DictionaryLookup: 326