C# List<> Add() 方法性能

Question

我正在使用 List<> 集合，在 2 个嵌套循环内将新对象添加到集合中。循环结束执行后，集合中添加了大约 500000 个项目。

一开始，加法运算运行良好，但很快就可以注意到性能下降，最后几千个元素，延迟时间难以忍受。

我尝试了各种技巧(将集合初始化为特定大小 - 500000)，将 List<> 替换为 LinkedList<> 集合，但没有太大帮助。

你能给我推荐一个解决问题的技巧吗？我对使用更优化的结构更改结构很感兴趣 - 例如，LinkedList<> 在执行加法等操作时比 List<> 表现更好。

更新列表的方法

   private void UpdateForecastList(ConcurrentDictionary<Int32, RegistroSalidaProductoPrevision> prediccion, bool soloMejoresMetodos = true)
   {
        foreach (KeyValuePair<int, RegistroSalidaProductoPrevision> kvp in prediccion)
        {
            KeyValuePair<int, RegistroSalidaProductoPrevision> localKvp = kvp;

            IList<Prediccion> pExistente = prediccionList.Where(p => p.Id == localKvp.Key).ToList();

            Articulo articulo = (articuloList.Where(a => a.Id == localKvp.Key)).First();

            if (pExistente.Count > 0)
            {
                foreach (var p in pExistente)
                {
                    prediccionList.Remove(p);
                }
            }

            if (kvp.Value.Previsiones.Count > 0)
            {
                var previsiones = kvp.Value.Previsiones.Where(prevision => prevision.Value.LPrevision[1] != null).ToList();
                int previsionesCount = previsiones.Count;

                for (int a = 0; a < previsionesCount; a++)
                {
                    var registros = previsiones[a].Value.LPrevision[1].Serie;
                    int c = registros.Count;

                    if (soloMejoresMetodos)
                    {
                        if (localKvp.Value.MejorMetodo != previsiones[a].Key) continue;
                        for (int i = 0; i < c; i++)
                        {
                            var p = new Prediccion()
                                        {
                                            Id = articulo.Id,
                                            Nombre = articulo.Codigo,
                                            Descripcion = articulo.Descripcion,
                                            NombreMetodo =
                                                Utils.SplitStringByCapitals(previsiones[a].Value.NombreMetodo),
                                            Fecha = registros[i].Fecha,
                                            PrediccionArticulo = Math.Round(registros[i].Cantidad, 2),
                                            EsMejorMetodo =
                                                (previsiones[a].Value.NombreMetodo == localKvp.Value.MejorMetodo)
                                                    ? true
                                                    : false
                                        };

                            // This line experiences performance loss
                            prediccionList.Add(p);
                        }
                    }
                    else
                    {
                        for (int i = 0; i < c; i++)
                        {
                            prediccionList.Add(new Prediccion()
                                                   {
                                                       Id = articulo.Id,
                                                       Nombre = articulo.Codigo,
                                                       Descripcion = articulo.Descripcion,
                                                       NombreMetodo = previsiones[a].Value.NombreMetodo,
                                                       Fecha = registros[i].Fecha,
                                                       PrediccionArticulo =
                                                           Math.Round(registros[i].Cantidad, 2),
                                                       EsMejorMetodo =
                                                           (previsiones[a].Value.NombreMetodo ==
                                                            localKvp.Value.MejorMetodo)
                                                               ? true
                                                               : false
                                                   });
                        }
                    }
                }
            }
            else
            {
                prediccionList.Add(new Prediccion()
                                       {
                                           Id = articulo.Id,
                                           Nombre = articulo.Codigo,
                                           Descripcion = articulo.Descripcion,
                                           NombreMetodo = kvp.Value.ErroresDatos[0].Texto,
                                       });
            }
        }
    }

---

方法的小说明:- 该方法读取一个对象(并发字典)并使用与某篇文章对应的预测更新列表(在本例中为 LinkedList)。

并发字典对象不断从并发访问它的各种线程更新。

列表初始化为对应于所有文章的空预测；因此，例如，如果您有 700 篇文章，则列表一开始将填充 700 个空白预测。

当并发字典被其中一个计算线程更新时，它会引发一个调用上述方法的事件，该方法会依次更新列表 (prediccionList)。

prediccionList 中可以保存的最大记录数(在本例中)约为 500000 条记录，但在列表中添加大约 40000 条记录后可能会注意到性能损失。

代码可能看起来有点生疏，因为我尝试了各种优化技巧(将 foreach 替换为 for，计算循环外的计数，将 List<> 对象替换为 LinkedList<> 等)。最后我得出结论，减慢执行时间的部分是行“prediccionList.Add(p);”。

添加到列表中的对象是 Prediccion 类的实例；这个对象我认为不是很重，它只包含 7 个字段。

内存使用情况

我附上了内存分析的结果。使用的内存不超过 256 MB，因此我认为这里的内存不是问题。

Answer 1

该问题与 List 或任何其他 .NET 数据结构的性能无关。您的问题纯粹是算法问题。例如，您有以下代码片段:

    foreach (KeyValuePair<int, RegistroSalidaProductoPrevision> kvp in prediccion)
    {
        KeyValuePair<int, RegistroSalidaProductoPrevision> localKvp = kvp;

        IList<Prediccion> pExistente = prediccionList.Where(p => p.Id == localKvp.Key).ToList();

        Articulo articulo = (articuloList.Where(a => a.Id == localKvp.Key)).First();

因此对于字典中的每个项目 (prediccion)，您要遍历整个 prediccionList。您已经实现了 n^2 算法。执行该方法所需的时间与 prediccion.Count * prediccionList.Count 成正比。

你需要一个更好的算法；不是更快的集合数据结构。