使用时间戳数据最有效的结构是什么

Question

各位编码员，

我有一个方法 returns 一个 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，但我觉得将它枚举到数组破坏逻辑顺序 geween 项目。如何防止多次枚举 and 保持顺序关系以供进一步使用？

Answer 1

到目前为止，您的算法中最慢的点是 2 倍 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(m.n)，其中 n 是集合的大小，m 是集合的数量日期对。

使用时间戳数据最有效的结构是什么

What is the most efficient structure to work with datestamped data

c#

linq

sorting

ienumerable