计算一个,两个和三个连续项的SUM的更好方法

Question

类

public class myItem
{
    public int ID;
    public long Value;
    public long Sum1;
    public long Sum2;
    public long Sum3;
}

数据

ID   Value
1    25
2    45
3    56
4    21

结果:

     Sum1     Sum2         Sum3
1    25     25 + 45    25 + 45 + 56
2    45     45 + 56    45 + 56 + 21
3    56     56 + 21    56 + 21 + 0
4    21     21 + 0     21 +  0 + 0

当前程序:工作但很慢(约10分钟),行数为100k.

List<myItem> list;
for (int i = 0; i < list.Count(); i++)
{
   myItem m = list[i];
   m.Sum1 = list.Where(x => x.ID == i).Sum(x => x.Value);
   m.Sum2 = list.Where(x => x.ID >= i && x.ID <= i + 2).Sum(x => x.Value);
   m.Sum3 = list.Where(x => x.ID >= i && x.ID <= i + 3).Sum(x => x.Value);
}

所以我想应该有一种方法可以做到这一点,而不是for加快速度.

Answer 1

缓慢的根本原因是你的循环是O(n ^ 2),因为对于每个元素,你在整个列表中搜索它的后继.下面减少到O(n log n)(最慢的部分是排序).

List<myItem> list;
list.Sort(<.. sort by id ..>);
for (int i = 0; i < list.Count; i++)
{
   myItem m = list[i];
   m.Sum1 = m.Value;

   m.Sum2 = m.Sum1;
   if (i < list.Count - 1)
   {
       m.Sum2 += list[i + 1].Value;
   }

   m.Sum3 = m.Sum2;
   if (i < list.Count - 2)
   {
       m.Sum3 = += list[i + 2].Value;
   }
}