计算一个、两个和三个连续项目的总和的更好方法

本文关键字：项目 连续 更好 方法 三个 和的 一个 计算 两个 | 更新日期: 2023-09-27 18:01:53

类

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的情况下加快速度。

计算一个、两个和三个连续项目的总和的更好方法

缓慢的根本原因是循环是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;
   }
}

只是对Jared的解决方案进行了一些修改，但使用了他的想法：

        List<myItem> list;
        //list.Sort(<.. sort by id ..>);
        int count = list.Count();
        for (int i = 0; i < count; i++)
        {
            myItem m = list[i];
            m.Sum1 = m.Value;                
            m.Sum2 = (i+1 < count) ? (m.Value + list[i+1].Value) : m.Value;
            m.Sum3 = (i+2 < count) ? (m.Sum2 + list[i+2].Value) : m.Sum2;                
        }

(取消删除答案，因为事实证明其他答案中仍然存在细微的错误(

LINQ在这个问题上没有帮你。只需根据需要引用数组索引：

List<myItem> list;
// sort list by id
list.Sort(t => t.ID);
for (int i = 0; i < list.Count; i++)
{
   myItem m = list[i];
   m.Sum1 = m.Value;
   m.Sum2 = m.Sum1 + (i + 1 < list.Count ? list[i + 1].Value : 0);
   m.Sum3 = m.Sum2 + (i + 2 < list.Count ? list[i + 2].Value : 0);
}

编辑：关于列表的小注释。计数((与列表。计数

我注意到有人评论说不使用list.Count()(Enumerable.Count()(而使用list.Count(属性(。我个人也很喜欢，但应该注意的是，与一些人可能会相信的不同，Enumerable.Count()版本不会迭代整个列表来获得计数。相反，因为它检测到列表是ICollection<T>的实现，所以它将直接使用Count属性。因此，实际上，在这种特定情况下，这两个选项之间的性能差异可以忽略不计。

此行为记录在此处。

如果源的类型实现ICollection<T>，则该实现用于获取元素计数。否则，此方法将确定计数。

另一个解决方案。不需要排序。不确定它是否会跑得更快，请检查。

list.ForEach(m =>
{
      m.Sum1 = m.Value;
      m.Sum2 = ((m.ID + 1) < list.Count) ? (m.Sum1 + list[m.ID + 1].Value) : m.Sum1;
      m.Sum3 = ((m.ID + 2) < list.Count) ? (m.Sum2 + list[m.ID + 2].Value) : m.Sum2;
});

此处的功能方式：

var seed = new { 
    Result = new List<myItem>(), 
    Item1 = ( myItem )null, 
    Item2 = ( myItem )null 
};
// seed contains intermediate result and other items related to currentItem
// [Item1, Item2, currentItem]
// For the first item, it would be
// [null, null, Id = 1]
// For the second item, it would be
// [null, Id = 1, Id = 2]
// And the third
// [Id = 1, Id = 2, Id = 3]
// For nth item, it's
// [Id = n-2, Id = n-1, Id = n]
var final = input.Aggregate( seed, ( pr, i ) =>
{
    if ( pr.Item1 != null )
    {
        var item1 = pr.Item1;
        item1.Sum3 = item1.Sum2 + i.Value;
    }
    if ( pr.Item2 != null )
    {
        var item2 = pr.Item2;
        item2.Sum2 = item2.Sum1 + i.Value;
    }
    pr.Result.Add( i );
    i.Sum1 = i.Value;
    // It will create lots of short life object.
    // If performance is bad, create named class just as this anonymous class,
    // update its properties and return it
    // pr.Item1 = pr.Item2;
    // pr.Item2 = pr.i;
    // return pr;
    return new { Result = pr.Result, Item1 = pr.Item2, Item2 = i };
} );
相关文章：