时间戳

首页 > 解决方案 > 处理带日期戳的数据最有效的结构是什么

c# - 处理带日期戳的数据最有效的结构是什么

问题描述

各位码农，

我有一个返回 IEnumerable(T) 的方法，其中 T 包含一个 DateTime 属性。

我需要从这组数据中执行许多基于日期的提取：例如，在 Date1 和 Date2 之间的所有项目。

随着数据集越来越大，我面临一个性能问题：这些提取需要一段时间。我觉得可以通过选择更适合枚举的数据结构来优化它。

我现在正在做的是：

              public class Foo
    {
        public DateTime Date { get; set; }
        public double Value { get; set; }
    }


    public class DoSomething
    {
        public IEnumerable<Foo> Foos { get;}

        public IEnumerable<Foo[]> DoStuff(DateTime[] dates)
        {
            var foos = Foos.
                OrderBy(x=>x.Date)
                .ToArray(); //Prevents multiple enumeration later on, Any better suited structure ? 

            for (int i = 0; i < dates.Length-1; i++)
            {
                yield return foos
                    .Where(x => x.Date > dates[i])
                    .Where(y=>y.Date<dates[i+1])
                    .ToArray();
            }
        }
    }

我读过 LINQ 方法 OrderBy 创建了一个 IOrderEnumerable，但我觉得将它枚举到一个数组会破坏逻辑顺序项目。如何防止多次枚举并保持顺序关系以供进一步使用？

标签： c#linqsortingienumerable

解决方案

到目前为止，您的算法中最慢的点是 2-times Where。永远记住：Where对于大集合和更复杂的比较函数来说总是很慢。

所以这里有一个更好的算法：我会用Where自定义二进制搜索替换这两个。的时间复杂度Where是O(n)，而二分查找的复杂度是O(log n)。二进制搜索的目的是找到最接近边缘日期的元素，换句话说，您将找到foo集合中大于的最小日期dates[i]，然后分别找到小于的最大日期比dates[i+1]。

参考：https ://en.wikipedia.org/wiki/Binary_search_algorithm

因此，您编写了两个辅助方法来查找 中的下限和上限项foo，然后您可以像现在一样简单地生成区间。

Foos.OrderBy.ToArray此外，您可以通过替换Foos.Sort或获得另一个微小的改进Foos.Clone.Sort。您只需要提供一个比较功能。（但是这个重构没有上面的那么重要。）

通过使用这种方法，您可以获得 O(m.log n) 的时间复杂度，而不是当前的 O(mn)，其中 n 是集合的大小，m 是日期对的数量。

推荐阅读