LINQ连接HashSet中的实体，Join vs Dictionary vs HashSet性能比较

Question

LINQ连接HashSet中的实体，Join vs Dictionary vs HashSet性能比较

4

我有一些存储T类型的HashSet，我编写了一个测试应用程序来比较我能想到的不同关系算法，但是我对结果并不完全满意。

是否存在更有效的实现对象关系的方法，而不是我正在测试的这些方法？

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace LINQTests
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<User> UserTable = new HashSet<User>();
            HashSet<UserProperty> UserPropertyTable = new HashSet<UserProperty>();

            #region Lets create some dummy data.

            Console.WriteLine("Please wait while creating dummy data, this can take a while...");
            Console.WriteLine("");

            int rows = 1000000;
            for(int x = 0; x < rows; x++)
            {
                Random rnd = new Random();

                // Add new user.
                User user = new User(string.Format("Joachim-{0}", x));
                if(!UserTable.Add(user))
                {
                    // throw new Exception.
                }
                else
                {
                    UserProperty age = new UserProperty(user, "Age", rnd.Next(25, 30).ToString());
                    if(!UserPropertyTable.Add(age))
                    {
                        // throw new Exception.
                    }

                    UserProperty sex = new UserProperty(user, "Sex", "Male");
                    if (!UserPropertyTable.Add(sex))
                    {
                        // throw new Exception.
                    }

                    UserProperty location = new UserProperty(user, "Location", "Norway");
                    if (!UserPropertyTable.Add(location))
                    {
                        // throw new Exception.
                    }
                }
            }

            #endregion

            #region Lets do some query tests.

            IEnumerable<User> Users;
            Stopwatch stopwatch = new Stopwatch();
            int matches = 0;

            // Lets find all users who are of age 29.
            Console.WriteLine("Finding all users who are of age 29");
            Console.WriteLine("");
            Console.WriteLine("---------------------------------------------------");
            Console.WriteLine("{0,-20} | {1,6} | {2,9}", "Search Strategy", "Found", "Time");
            Console.WriteLine("---------------------------------------------------");

            // Join test.
            stopwatch.Start();

            Users = (from user in UserTable
                     join property in UserPropertyTable on user.Id equals property.UserId
                     where property.Key == "Age" && property.Value == "29"
                     select user);

            matches = Users.Count();
            stopwatch.Stop();
            Console.WriteLine("{0,-20} | {1,6} | {2,6} ms.", "Joining Tables", matches, stopwatch.ElapsedMilliseconds);

            // Dictionary test.
            stopwatch.Restart();

            var DictionarySearch = (from t in UserPropertyTable where t.Key == "Age" && t.Value == "29" select t).ToDictionary(x => x.UserId);
            Users = (from t in UserTable where DictionarySearch.ContainsKey(t.Id) select t);

            matches = Users.Count();
            stopwatch.Stop();
            Console.WriteLine("{0,-20} | {1,6} | {2,6} ms.", "Dictionary Contain", matches, stopwatch.ElapsedMilliseconds);

            // HashSet test.
            stopwatch.Restart();

            var HashsetSearch = new HashSet<Guid>(from t in UserPropertyTable where t.Key == "Age" && t.Value == "29" select t.UserId);

            Users = (from t in UserTable where HashsetSearch.Contains(t.Id) select t);

            matches = Users.Count();
            stopwatch.Stop();
            Console.WriteLine("{0,-20} | {1,6} | {2,6} ms.", "HashSet Contain", matches, stopwatch.ElapsedMilliseconds);

            // Following takes so long that we wont run them!

            //// Array test.
            //stopwatch.Restart();

            //var ArrayMatch = (from t in UserPropertyTable where t.Key == "Age" && t.Value == "29" select t.UserId).ToArray();
            //Users = (from t in UserTable where ArrayMatch.Contains(t.Id) select t);

            //matches = Users.Count();
            //stopwatch.Stop();
            //Console.WriteLine("{0,-20} | {1,6} | {2,6} ms.", "Array Contain", matches, stopwatch.ElapsedMilliseconds);


            //// List test.
            //stopwatch.Restart();

            //var ListMatch = (from t in UserPropertyTable where t.Key == "Age" && t.Value == "29" select t.UserId).ToList();
            //Users = (from t in UserTable where ListMatch.Contains(t.Id) select t);

            //matches = Users.Count();
            //stopwatch.Stop();
            //Console.WriteLine("{0,-20} | {1,6} | {2,6} ms.", "List Contain", matches, stopwatch.ElapsedMilliseconds);


            Console.WriteLine("---------------------------------------------------");

            #endregion


            Console.WriteLine("");
            Console.WriteLine("Hit return to exit...");
            Console.Read();
        }
    }

    public class User
    {
        public User(string UserName)
        {
            this.Id = Guid.NewGuid();
            this.UserName = UserName;
        }

        public Guid Id { get; set; }
        public string UserName { get; set; }

        public override bool Equals(object obj)
        {
            User other = obj as User;

            if (other == null)
                return false;

            return this.Id == other.Id;
        }

        public override int GetHashCode()
        {
            return Id.GetHashCode();
        }
    }

    public class UserProperty
    {
        public UserProperty(User user, string key, string value)
        {
            this.Id = Guid.NewGuid();
            this.UserId = user.Id;
            this.Key = key;
            this.Value = value;
        }

        public Guid Id { get; private set; }
        public Guid UserId {get; private set;}
        public string Key { get; set; }
        public string Value { get; set; }

        public override bool Equals(object obj)
        {
            UserProperty other = obj as UserProperty;

            if (other == null)
                return false;

            return this.UserId == other.UserId && this.Key == other.Key;
        }

        public override int GetHashCode()
        {
            return string.Format("{0}-{1}", this.UserId, this.Key).GetHashCode();
        }
    }
}

- Joachim

如果你在搜索哈希集合方面遇到了问题，可以在stackoverflow上找到相关的大量讨论。 - Callum Linington

2

由于您在循环内实例化随机类，许多项目由于时间而具有完全相同的数据，这可能会导致测量误差。 - usr

1

你为什么认为结果不好？UserProperty.GetHashcode 可能比必要的慢10倍，这是我能发现的唯一问题。 - usr

1

永远不要使用类中非只读字段/属性计算GetHashCode()。GetHashCode()的值必须在对象的生命周期内保持不变。 - Enigmativity

哦，是的，我很快就打出了这个代码，因为我在使用的“真实世界”代码中，为HashSet存储库使用了通用的T接口。但是，是的，每个具有GetHashCode的类都是从只读属性计算出来的。 - Joachim

@usr，你是在想string.Format吗？但这不仅适用于我向哈希集添加实体时吗？我遇到的主要问题是能够快速解决对象关系。 - Joachim

2个回答

2

这将使linq/join与其他方法相媲美：

var properties = UserPropertyTable
    .Where(p=>p.Key == "Age" && p.Value == "29")
    .ToArray();

Users = (from user in UserTable
         join property in properties
         on user.Id equals property.UserId
         select user);

这是我能够实现的最快速度（约为2倍）：

var filteredUserIds = new HashSet<Guid>(
        UserPropertyTable
            .Where(p=>p.Key == "Age" && p.Value == "29")
            .Select(p=>p.UserId));

Users = (from user in UserTable
         where filteredUserIds.Contains(user.Id)
         select user);

输出结果如下：

---------------------------------------------------
搜索策略             |  找到 |      时间
---------------------------------------------------
我的方法            | 210366 |    157 毫秒.
字典包含            | 210366 |    325 毫秒.
哈希集合包含        | 210366 |    325 毫秒.
---------------------------------------------------

- Andrei Tătar

非常好的想法。我得到的结果基本相同 - 用join函数仍然需要一些更长的时间，但由于需要进行线性连接，这是有意义的。 - Enigmativity

1

@Enigmativity：使用哈希集合和 where 语句检查其他方法。 - Andrei Tătar

我的字典包含和哈希集合都没有从延迟的LINQ语句中获益。然而，以下代码似乎比Dict和Hash包含慢一点（5-10％），但有延迟的LINQ的好处：

Users = (from user in UserTable
         join property in UserPropertyTable.Where(x => x.Key == "Age" && x.Value == "29")
         on user.Id equals property.UserId
         select user);

通过注释掉 maches = Users.Count(); 进行测试。 - Joachim

进一步的测试表明，使用经过筛选的linq join在许多情况下甚至优于dict和hashset方法。然而，在某些大小的hashset之后，所有方法最终都会变慢，也许存在更好的存储和查找实体的方式？ - Joachim

您可以根据您想要查找的内容（如年龄）将它们进行索引。 - Andrei Tătar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- usr · Accepted Answer

以下是您可以采取的一些措施：

对于每个添加的元素和每个被探测的元素，都会调用 GetHashCode（否则哈希表如何比较两个哈希码？）。对于每个探测操作，至少会调用一次 Equals。优化这些操作。不要使用 string.Format！它需要解析格式字符串并分配内存。使用 UserId.GHC() * 37 ^ Name.GHC() 就可以了。
不要使用 LINQ。编写手动循环。LINQ 对于每个处理的项都有多个 vcall 或委托调用。这会增加指令、使 CPU 停滞并阻止内联。
你能预计算数据结构吗？预计算哈希表或排序列表。合并两个排序列表可能比使用哈希表更快。这不是框架内置的功能。需要编写大量的自定义代码来实现合并连接。
为什么在测量中包括 property.Key == "Age" && property.Value == "29" 谓词？每次执行都需要运行吗？您可以尝试使用整数值而不是字符串来优化它。也许您可以预先计算 UserPropertyTable 的索引，以便可以在常数时间内获取匹配的元素。

这些措施可以使您的程序速度提高 1-10 倍，具体取决于您实施了多少。如果您需要更快的速度，我需要先询问一些问题。通常情况下，您可以找到仅适用于特定情况的专业技巧。