0

我正在编写一个主要是性能密集型的应用程序。今天写了一个快速基准测试后，我发现字典访问时间比数组访问时间慢得多（最多 100 次），尽管两者都是 O(1)。我尝试在互联网上找到类似的结果，但无济于事。这看起来对吗？这对我来说很有意义，因为字典涉及散列，而不是数组。

我现在正在权衡字典的优缺点，并考虑是否应该尝试更快的实施。在我的应用程序的至少 3 个实例中，我使用 foreach 循环遍历我的所有字典（有很多）。所以现在要回答我的问题，foreach 循环是否必须经过“慢”（我在这里相对而言）散列过程，或者它是否只是维护一个可以快速迭代的内部列表？如果是这种情况，我更有可能坚持使用字典。

对于一些额外的信息，该应用程序是一个简单的 2D 游戏，而字典将存储在游戏实体中。不过确实有很多。是的，我已经有了一个可行的解决方案。这是优化后，而不是优化前。

这是我写的基准。这可能是非常错误的，因为我不是该领域的专家：

        public static int dict(Dictionary<key,int> dict, key k)
        {
            int i;
            //dict.TryGetValue(k,out i);
            i = dict[k];  //both these version yield the same results

            return i;
        }

        public static int arr(int[,] arr, key k)
        {
            int i;
            i = arr[k.x, k.y];

            return i;
        }

        public struct key
        {
            public int x, y;

            public key (int x, int y){
                this.x = x;
                this.y = y;
            }
        }

        public static void Main()
        {
            int dim = 256;
            Dictionary<key,int> dictVar = new Dictionary<key,int>(dim*dim*10);

            int[,] arrVar = new int[dim,dim];

            for (int i = 0; i < dim; ++i)
            {
                for (int j = 0; j < dim; ++j)
                {
                    arrVar[i, j] = i + j * i;
                    dictVar.Add(new key(i, j), i + i * j);
                }  
            }

            const int iterations = 1000000;
            key k = new key(200, 200);
            TestTime(dict, dictVar, k, iterations);
            TestTime(arr, arrVar, k, iterations);
        }

        public static void TestTime<T1, T2, TR>(Func<T1, T2, TR> action, T1 obj1,
                                                T2 obj2, int iterations)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < iterations; ++i)
                action(obj1, obj2);
            Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed);
        }
4

1 回答 1

1

它维护一个循环遍历的内部列表，但该列表的类型为Entry<TKey, TValue>[]，因此每次都必须构造一个 KeyValuePair 。我猜这就是导致放缓的原因。

于 2012-05-17T22:30:02.513 回答