1

我需要一个基本上是数据点列表的数据结构，其中每个数据点都有一个时间戳和一个数据值的 double[]。我希望能够检索到给定时间戳的最近点或指定时间戳范围内的所有点。

我正在使用 c#。我的想法是使用常规列表是可能的，其中“数据点”是一个包含时间戳和双 [] 字段的类。然后插入，我会使用内置的 binarysearch() 来查找插入新数据的位置，我可以再次使用它来查找范围搜索的开始/结束索引。

我首先尝试了 sortedlists，但似乎您不能仅通过键迭代索引 i=0,1,2,...,n，所以我不确定如何在没有一些复杂函数的情况下进行范围搜索.

但后来我了解到 list<> 的 insert() 是 o(n)...如果不牺牲其他地方，难道我不能做得更好吗？

或者，是否有一些不错的 linq 查询可以在一行中完成我想要的所有操作？

4

4 回答 4

1

如果您愿意使用非 BCL 库，C5.SortedArray<T>对我来说一直很有效。

它有一个很棒的方法RangeFromTo，可以很好地解决这类问题。

于 2009-04-17T16:36:36.727 回答
1

如果您只有静态数据，那么任何实现 IList 的结构都应该没问题。对其进行一次排序，然后使用 BinarySearch 进行查询。如果您插入的时间戳总是在增加，这也应该有效，那么您可以在 O(1) 中执行 List.Add() 并且它仍然会被排序。

    List<int> x = new List<int>();
    x.Add(5);
    x.Add(7);
    x.Add(3);

    x.Sort();

    //want to find all elements between 4 and 6
    int rangeStart = x.BinarySearch(4);

    //since there is no element equal to 4, we'll get the binary complement of an index, where 4 could have possibly been found
    //see MSDN for List<T>.BinarySearch
    if (rangeStart < 0)
        rangeStart = ~rangeStart;

    while (x[rangeStart] < 6)
    {
        //do you business
        rangeStart++;
    }

如果您需要在结构中的随机点插入数据、保持排序并能够快速查询范围，则需要一个名为B+ 树的结构。它没有在框架中实现，您需要自己在某个地方获取它。

在最坏的情况下插入记录需要 O(log n) 操作

在最坏的情况下，查找记录需要 O(log n) 次操作

在最坏的情况下，删除（先前定位的）记录需要 O(log n) 操作

在最坏的情况下，执行范围内出现 k 个元素的范围查询需要 O((log n) + k) 次操作。

PS “是否有一些不错的 linq 查询可以在一行中完成我想要的所有事情”

我希望我知道这么好的 linq 查询可以在一行中完成我想要的一切:-)

于 2009-06-17T14:48:54.057 回答
0

如何使用实际的数据库来存储您的数据并针对它运行查询？然后，您可以使用LINQ-to-SQL。

于 2009-04-24T14:57:48.547 回答
0

您可以选择插入、取出或移除时的成本。每种情况都有各种优化的数据结构。在你决定一个之前，我会估计你的结构的总大小，正在生成多少数据点（以及以何种频率）以及将更频繁地使用什么：插入或检索。

如果您以高频率插入大量新数据点，我建议您查看 LinkedList<>。如果您更频繁地检索，我会使用 List<> 即使它的插入时间较慢。

当然，您可以在 LINQ 查询中执行此操作，但请记住，这只是糖衣：查询将每次执行，每次执行都会搜索整个数据点集以找到匹配项。这可能比一开始就为工作使用正确的集合更昂贵。

于 2009-04-17T16:39:23.460 回答