3

我正在使用 C# 创建一个由单元格组成的网格。单元格将使用“sbyte X”和“sbyte Y”来确定网格中的位置（0,0 位于左上角）。Cell 是一个类，它将在网格中存储它自己的位置。

我想知道使用它是否会更好：

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 个网格，每个周期将处理每个网格中的几个单元格。

4

3 回答 3

2

第二种方法不起作用，因为数组不会覆盖GetHashCodeandEquals以使用存储在数组中的数据。然而，由于线性搜索，第一种方法对于具有大量单元格的集合会很慢。

更好的方法是使用Tuple<sbyte,sbyte>而不是数组：

Dictionary<Tuple<sbyte,sbyte>, Cell> CellList;
//....
Cell thisCell = CellList[Tuple.Create(thisX , thisY)];
于 2013-07-22T16:58:53.003 回答
2

创建网格后，大小将保持不变（所有网格的大小相同），并且与每个单元格关联的对象不会改变

那么更有效的是多维数组：

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

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

想知道 Cell[,] 与 Dictionary, 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;
    }

结果：

数组初始化：25

字典初始化：528

数组查找：7

字典查找：326

于 2013-07-22T17:01:05.623 回答
1

字典效率更高，因为它在HashTable内部使用 a，而使用列表时，每次要提取单元格时都必须搜索列表中的每个项目。

但是，我建议使用 aTuple<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)];
于 2013-07-22T16:59:14.660 回答