c# – 如何最大限度地减少大数据集的运行时间(从93,773个对象列表中创建唯一对

我们从EVE Online API中提取大量 JSON对象,并使用Newtonsoft.Json.JsonConvert将它们解压缩为EveObjModel对象.从那里我们想要创建一个唯一对象列表,即每个type_id中最昂贵的对象.我也粘贴了下面的dataContract.

问题：下面的代码可以处理较小的数据集,但是对于较大的数量,它是不可行的.目前,我们正在运行它,它需要超过50分钟(和计数).我们可以做些什么来减少将更大的数据集运行到可承受的水平所需的时间？

感谢您的时间.手指交叉.

// The buyList contains about 93,000 objects. 
    public void CreateUniqueBuyList(List<EveObjModel> buyList)
    {

        List<EveObjModel> uniqueBuyList = new List<EveObjModel>();

        foreach (EveObjModel obj in buyList)
        {
            int duplicateCount = 0;

            for (int i = 0; i < uniqueBuyList.Count; i++)
            {
                if (uniqueBuyList[i].type_id == obj.type_id)
                       duplicateCount++;
            }

            if (duplicateCount == 1)
            {
                foreach (EveObjModel objinUnique in uniqueBuyList)
                {
                    if (obj.type_id == objinUnique.type_id && obj.price > objinUnique.price)
                    {
                        // instead of adding obj, the price is just changed to the price in the obj. 
                        objinUnique.price = obj.price;

                    }
                    else if (obj.type_id == objinUnique.type_id && obj.price == objinUnique.price)
                    {
                        //uniqueBuyList.RemoveAll(item => item.type_id == obj.type_id);

                    }
                    else 
                    {
                        // Hitting this  mean that there are other objects with same type and higher price OR its not the same type_id
                    }

                }
            }
            else if (duplicateCount > 1)
            {
                // shud not happn...
            }
            else
            {

                uniqueBuyList.Add(obj);
            }


            continue;
        }
        foreach (EveObjModel item in uniqueBuyList.OrderBy(item => item.type_id))
        {
            buyListtextField.Text += $"Eve Online Item! Type-ID is: {item.type_id}, Price is {item.price}\n";
        }
    }

这是我们的EveObjModel类

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Runtime.Serialization;
    using System.Text;
    using System.Threading.Tasks;

    namespace EveOnlineApp
    {
    [DataContract]
         public class EveObjModel
    {
    [DataMember]
    public bool is_buy_order { get; set; }

    [DataMember]
    public double price { get; set; }

    [DataMember]
    public int type_id { get; set; }

    }
}

这个过程很慢并不奇怪,因为您使用的算法(使用嵌套循环)至少具有二次O(N * N)时间复杂度,这种数据集的大小非常慢.

一种方法是使用LINQ GroupBy运算符,它在内部使用基于散列的查找,因此理论上具有O(N)时间复杂度.因此,您按type_id进行分组,对于每个组(具有相同键的元素列表),请使用最大价格的一个：

var uniqueBuyList = buyList
    .GroupBy(e => e.type_id)
    .Select(g => g.OrderByDescending(e => e.price).First())
    .ToList();

对于cource,您不需要对列表进行排序以获取具有最大价格的元素.更好的版本是使用Aggregate方法(基本上是foreach循环)：

var uniqueBuyList = buyList
    .GroupBy(e => e.type_id)
    .Select(g => g.Aggregate((e1, e2) => e1.price > e2.price ? e1 : e2))
    .ToList();

另一种非基于LINQ的方法是通过type_id升序,降价来对输入列表进行排序.然后在排序列表上执行一个循环并获取每个type_id组的第一个元素(它将具有最大价格)：

var comparer = Comparer<EveObjModel>.Create((e1, e2) =>
{
    int result = e1.type_id.CompareTo(e2.type_id);
    if (result == 0) // e1.type_id == e2.type_id
        result = e2.price.CompareTo(e1.price); // e1, e2 exchanged to get descending order
    return result;
});
buyList.Sort(comparer);
var uniqueBuyList = new List<EveObjModel>();
EveObjModel last = null;
foreach (var item in buyList)
{
    if (last == null || last.type_id != item.type_id)
        uniqueBuyList.Add(item);
    last = item;
}

这种算法的复杂性是O(N * log(N)),因此它比基于散列的算法更差(但比原始算法要好得多).好处是它使用更少的内存,结果列表已经按type_id排序,因此您不需要使用OrderBy.