改进双for循环的性能

本文关键字：性能 循环 for | 更新日期: 2023-09-27 18:15:43

我正在研究一种向客户推荐餐厅的算法。这些推荐是基于一些过滤器，但主要是通过比较人们对餐馆的评论。(我就不告诉你细节了。)

为了计算pearson相关性(一个决定用户彼此适合程度的数字)，我必须检查用户在同一家餐厅留下评论的位置。为了增加匹配的数量，我在主题的价格范围内包含了一个匹配。我来解释一下，这是我的餐厅类:

public class Restaurant
{
    public Guid Id { get; set; }
    public int PriceRange { get; set; }
}

这是一个简化的版本，但对于我的例子来说已经足够了。pricerange可以是1-5的整数，它决定了餐厅的价格。

这里是for循环，我用它来检查他们是否对同一家餐厅留下了评论，或者对具有相同价格范围的餐厅留下了评论。

//List<Review> user1Reviews is a list of all reviews from the first user
//List<Review> user2Reviews is a list of all reviews from the second user
Dictionary<Review, Review> shared_items = new Dictionary<Review, Review>();
    foreach (var review1 in user1Reviews)
        foreach (var review2 in user2Reviews)
            if (review1.Restaurant.Id == review2.Restaurant.Id || 
                review1.Restaurant.PriceRange == review2.Restaurant.PriceRange)
                if (!shared_items.ContainsKey(review1))
                    shared_items.Add(review1, review2);

现在我的实际问题是。您可以看到，我正在为第一个用户留下的每条评论循环第二个列表。有没有办法提高这些循环的性能?我尝试使用哈希集和.contains()函数，但我需要包括更多的标准(即价格范围)。我不知道如何将其包含在hashset中。

我希望这不是太混乱，并提前感谢任何帮助!

编辑:在测试了linq和for循环之后，我得出结论，for循环的速度是使用linq的两倍。谢谢你的帮助!

改进双for循环的性能

您可以尝试使用外部循环的条件用Linq查询替换内部循环:

foreach (var review1 in user1Reviews)
{
    var review2 = user2Reviews.FirstOrDefault(r2 => r2.Restaurant.Id == review1.Restaurant.Id ||
                                            r2.Restaurant.PriceRange == review1.Restaurant.PriceRange);
    if (review2 != null)
    {
        if (!shared_items.ContainsKey(review1))
            shared_items.Add(review1, review2);
    }
}

如果有多个匹配，您应该使用Where并处理潜在的结果列表。

我不确定它是否会更快，因为你仍然需要检查所有user2评论和user1评论。

然而，如果你为你的餐厅类编写了一个自定义比较器，你可以使用这个超载的Intersect来返回你的共同评论:

var commonReviews = user1Reviews.Intersect(user2Reviews, new RestaurantComparer());

其中RestaurantComparer看起来像这样:

// Custom comparer for the Restaurant class
class RestaurantComparer : IEqualityComparer<Restaurant>
{
    // Products are equal if their ids and price ranges are equal.
    public bool Equals(Restaurant x, Restaurant y)
    {
        //Check whether the compared objects reference the same data.
        if (Object.ReferenceEquals(x, y)) return true;
        //Check whether any of the compared objects is null.
        if (Object.ReferenceEquals(x, null) || Object.ReferenceEquals(y, null))
            return false;
        //Check whether the properties are equal.
        return x.Id == y.Id && x.PriceRange == y.PriceRange;
    }
    // If Equals() returns true for a pair of objects 
    // then GetHashCode() must return the same value for these objects.
    public int GetHashCode(Product product)
    {
        //Check whether the object is null
        if (Object.ReferenceEquals(product, null)) return 0;
        //Get hash code for the Id field.
        int hashId product.Id.GetHashCode();
        //Get hash code for the Code field.
        int hashPriceRange = product.PriceRange.GetHashCode();
        //Calculate the hash code for the product.
        return hashId ^ hashPriceRange;
    }
}

您基本上需要一种快速的方法来定位Id 或 PriceRange的审查。通常情况下，您会对单个键使用快速哈希查找结构，如Dictionary<TKey, TValue>，如果匹配操作是和，则使用复合键。不幸的是你的是或，所以Dictionary不工作。

嗯，不完全是。单个字典不能工作，但您可以使用两个字典，并且由于字典查找是O(1)，因此操作仍然是O(N)(而不是像内部循环/naïve LINQ那样的O(N * M))。

由于键不是唯一的，您可以使用查找而不是字典，保持相同的效率:

var lookup1 = user2Reviews.ToLookup(r => r.Restaurant.Id);
var lookup2 = user2Reviews.ToLookup(r => r.Restaurant.PriceRange);
foreach (var review1 in user1Reviews)
{
    var review2 = lookup1[review.Restaurant.Id].FirstOrDefault() ??
                  lookup2[review.Restaurant.PriceRange].FirstOrDefault();
    if (review2 != null)
    {
        // do something
    }
}
相关文章：