c# - 哪个 .NET 集合更快 : enumerating foreach Dictionary<>. Values 或 List<>？

Question

这些枚举中的一个比另一个快还是差不多？ (C# 中的示例)

案例一:

Dictionary<string, object> valuesDict;

// valuesDict loaded with thousands of objects

foreach (object value in valuesDict.Values) { /* process */ }

案例二:

List<object> valuesList;

// valuesList loaded with thousands of objects

foreach (object value in valuesList) { /* process */ }

更新:

背景:

字典有利于在别处进行键控搜索(与遍历列表相反)，但如果遍历字典比遍历列表慢得多，那么好处就会减少。

更新:听取了很多人的建议，我进行了自己的测试。

首先，这些是结果。以下是程序。

迭代整个集合字典:78关键字:131列表:76

键控搜索集合字典:178关键字:194列表:142800

using System;
using System.Linq;

namespace IterateCollections
{
    public class Data
    {
        public string Id;
        public string Text;
    }

    public class KeyedData : System.Collections.ObjectModel.KeyedCollection<string, Data>
    {
        protected override string GetKeyForItem(Data item)
        {
            return item.Id;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var dict = new System.Collections.Generic.Dictionary<string, Data>();
            var list = new System.Collections.Generic.List<Data>();
            var keyd = new KeyedData();

            for (int i = 0; i < 10000; i++)
            {
                string s = i.ToString();
                var d = new Data { Id = s, Text = s };
                dict.Add(d.Id, d);
                list.Add(d);
                keyd.Add(d);
            }

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                foreach (Data d in dict.Values)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            var dictTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                foreach (Data d in keyd)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            var keydTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                foreach (Data d in list)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            var listTime = sw.ElapsedMilliseconds;

            Console.WriteLine("Iterate whole collection");
            Console.WriteLine("Dict: " + dictTime);
            Console.WriteLine("Keyd: " + keydTime);
            Console.WriteLine("List: " + listTime);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                for (int i = 0; i < 10000; i += 10)
                {
                    string s = i.ToString();
                    Data d = dict[s];
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            dictTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 1000; r++)
            {
                for (int i = 0; i < 10000; i += 10)
                {
                    string s = i.ToString();
                    Data d = keyd[s];
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            keydTime = sw.ElapsedMilliseconds;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < 10; r++)
            {
                for (int i = 0; i < 10000; i += 10)
                {
                    string s = i.ToString();
                    Data d = list.FirstOrDefault(item => item.Id == s);
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            listTime = sw.ElapsedMilliseconds * 100;

            Console.WriteLine("Keyed search collection");
            Console.WriteLine("Dict: " + dictTime);
            Console.WriteLine("Keyd: " + keydTime);
            Console.WriteLine("List: " + listTime);

        }
    }

更新:

@Blam 建议的字典与 KeyedCollection 的比较。

最快的方法是遍历 KeyedCollection 项数组。

但是请注意，在不转换为数组的情况下迭代字典值比在 KeyedCollection 上迭代更快。

请注意，遍历字典值比遍历字典集合要快得多。

 Iterate 1,000 times over collection of 10,000 items
   Dictionary Pair:   519 ms
 Dictionary Values:    95 ms
  Dict Val ToArray:    92 ms
   KeyedCollection:   141 ms
   KeyedC. ToArray:    17 ms

时间来自 Windows 控制台应用程序(发布版本)。这是源代码:

using System;
using System.Collections.Generic;
using System.Linq;

namespace IterateCollections
{
    public class GUIDkeyCollection : System.Collections.ObjectModel.KeyedCollection<Guid, GUIDkey>
    {
        // This parameterless constructor calls the base class constructor 
        // that specifies a dictionary threshold of 0, so that the internal 
        // dictionary is created as soon as an item is added to the  
        // collection. 
        // 
        public GUIDkeyCollection() : base() { }

        // This is the only method that absolutely must be overridden, 
        // because without it the KeyedCollection cannot extract the 
        // keys from the items.  
        // 
        protected override Guid GetKeyForItem(GUIDkey item)
        {
            // In this example, the key is the part number. 
            return item.Key;
        }

        public GUIDkey[] ToArray()
        {
            return Items.ToArray();
        }

        //[Obsolete("Iterate using .ToArray()", true)]
        //public new IEnumerator GetEnumerator()
        //{
        //    throw new NotImplementedException("Iterate using .ToArray()");
        //}
    }
    public class GUIDkey : Object
    {
        private Guid key;
        public Guid Key
        {
            get
            {
                return key;
            }
        }
        public override bool Equals(Object obj)
        {
            //Check for null and compare run-time types.
            if (obj == null || !(obj is GUIDkey)) return false;
            GUIDkey item = (GUIDkey)obj;
            return (Key == item.Key);
        }
        public override int GetHashCode() { return Key.GetHashCode(); }
        public GUIDkey(Guid guid)
        {
            key = guid;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            const int itemCount = 10000;
            const int repetitions = 1000;
            const string resultFormat = "{0,18}: {1,5:D} ms";

            Console.WriteLine("Iterate {0:N0} times over collection of {1:N0} items", repetitions, itemCount);

            var dict = new Dictionary<Guid, GUIDkey>();
            var keyd = new GUIDkeyCollection();

            for (int i = 0; i < itemCount; i++)
            {
                var d = new GUIDkey(Guid.NewGuid());
                dict.Add(d.Key, d);
                keyd.Add(d);
            }

            var sw = new System.Diagnostics.Stopwatch();
            long time;

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (KeyValuePair<Guid, GUIDkey> w in dict)
                {
                    if (null == w.Value) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "Dictionary Pair", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in dict.Values)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "Dictionary Values", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in dict.Values.ToArray())
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "Dict Val ToArray", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in keyd)
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "KeyedCollection", time);

            sw.Reset();
            sw.Start();
            for (int r = 0; r < repetitions; r++)
            {
                foreach (GUIDkey d in keyd.ToArray())
                {
                    if (null == d) throw new ApplicationException();
                }
            }
            sw.Stop();
            time = sw.ElapsedMilliseconds;
            Console.WriteLine(resultFormat, "KeyedC. ToArray", time);
        }
    }

}

Answer 1

用秒表比较容易检查:

var d = new Dictionary<string, object>();
var s = new List<object>();
for (int i =0 ; i != 10000000 ; i++) {
    d.Add(""+i, i);
    s.Add(i);
}
var sw = new Stopwatch();
sw.Start();
foreach(object o in d.Values) {
    if (o == null) throw new ApplicationException();
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
foreach (object o in s) {
    if (o == null) throw new ApplicationException();
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

这会打印出彼此相当接近的数字:

Dict List
---- ----
 136  107
 139  108
 136  108

List 总是赢家，但考虑到两种数据结构的相对复杂性，利润率并不像人们预期的那么大。