数据结构，以快速找到最近的浮点值

本文关键字：最近 数据结构 | 更新日期: 2023-09-27 18:12:04

如果我有一堆以下数据，我应该使用什么样的数据结构:

MyData
{
    float ValueA;
    float ValueB;
    object OtherInfo;
}

我需要快速找到所有符合这种标准的MyData实例:

0.5 <= ValueA <= 0.7    AND    0.2 <= ValueB <= 0.9

找到这些项目很简单，但我需要尽快完成。是否存在一种理想的数据结构?我不介意用完额外的内存。

我目前的想法是有一个排序列表，按ValueA排序。然后我将进行二进制搜索以找到ValueA>= 0.5的第一个项目，并迭代直到我得到ValueA> 0.7的项目。对于每次迭代，我检查ValueB是否在0.2到0.9之间。我把所有匹配的项目放在我的输出数据集中。

有没有更好/更快的方法做这件事?

顺便说一下，我用的是c#。

数据结构，以快速找到最近的浮点值

区间树可以满足您的需求。示例实现(我没有测试)在Codeplex。更多。

更新:区间树与相关结构段树的比较:段树、区间树、二叉索引树和范围树之间有什么区别?

你的问题是二维的，但你只是在一维上优化搜索空间。四叉树是一种合适的数据结构;你应该不难在c#中找到合适的实现。如果你想要其他的选择，那就搜索二维空间划分算法。这就是你在这里所做的;ValueA和ValueB可以被视为2D坐标，即使这不是它们实际表示的内容。

您可以使用单个列表来完成此操作，该列表首先在ValueA上排序，然后在ValueB上排序。所以如果你有这些项目:

  A    B
{0.5, 0.7}
{0.3, 0.1}
{0.5, 0.2}
{0.5, 0.4}
{0.2, 0.3}

你在你的列表中这样排序:

{0.2, 0.3}
{0.3, 0.1}
{0.5, 0.2}
{0.5, 0.4}
{0.5, 0.7}

在LINQ中按两个标准排序真的很容易:

var sortedList = theList.OrderBy(s => s.ValueA).ThenBy(s => s.ValueB).ToList();

您还可以通过将自定义比较委托传递给sort方法来对列表进行就地排序。

现在，给定搜索:0.5 <= ValueA <= 0.7 && 0.2 <= ValueB <= 0.9，您执行以下操作:

  1. 二进制查找查找>= 0.5的第一个ValueA。命名为startA
  2. 查找最后一个值<= 0.7的值。命名为endA
  3. 二进制查找第一个>= 0.2的ValueB的区间[startA..endA]。将其命名为startB。
  4. 在区间[startA..endA]中查找最后一个ValueB为<= 0.9。将其命名为endB。

您要查找的项目在[startB..endB]区间内。

请注意，如果您要遍历[startB..endB]范围内的所有项，则不必执行最后的二进制搜索，因为您可以在迭代期间将它们过滤掉。

在这个解决方案中，我将数据放入列表中，其中每个列表包含widthX × widthY框中的所有数据点。如果您的数据在valA=[0,1], valB=[0,2]范围内，并且您将网格划分为.1 × .1 bin(如代码所示)，则searchList(4,12)是包含所有值的列表，例如.4 <= valA <= .5和1.2 <= valB <= 1.3

此解决方案仅对相当紧凑的大型输入数组有效。如果存在任何极端的异常值，您将创建许多不必要的箱子。

如果查询在"自然"(即.1，.01)边界上，则效果最好，但这不是必需的。您必须手动遍历searchList(i,j)以过滤掉不需要的元素。

搜索查询相当容易-找到每个维度上的最小/最大bin，并在两者之间的所有bin中循环。

static List<MyData>[,] GetSearchArray(List<MyData> srcList)
{
  float minA = srcList.Min(s => s.valA);
  float minB = srcList.Min(s => s.valB);
  float maxA = srcList.Max(s => s.valA);
  float maxB = srcList.Max(s => s.valB);
  // Round the min's down, the max's up. 
  // If your searches are likely to fall on .1 intervals, that's a good rounding distance.
  // Note, they don't have to be the same for valA and valB
  minA = (float)Math.Floor(minA*10f)/10f;
  minB = (float)Math.Floor(minB*10f)/10f;
  maxA = (float)Math.Ceiling(maxA*10f)/10f;
  maxB = (float)Math.Ceiling(maxB*10f)/10f;
  // How many groupings between minA->maxA and minB->maxB
  int divsA = (int)Math.Round((maxA-minA)/.1);
  int divsB = (int)Math.Round((maxB-minB)/.1);
  // 2d array of data lists.
  var searchList = new List<MyData>[divsA,divsB];
  for (int i = 0; i < divsA; i++)
  {
    for (int j = 0; j < divsB; j++)
    {
      // row i: (minA + i*.1) <= valA <= (minA + (i+1)*.1)
      // col j: (minB + j*.1) <= valB <= (minB + (j+1)*.1)
      searchList[i, j] = new List<MyData>();
      var query = srcList.Where(s => (minA + i * .1 <= s.valA) && (s.valA <= minA + (i + 1) * .1) &&
                                     (minB + j * .1 <= s.valB) && (s.valB <= minB + (j + 1) * .1));
      foreach (MyData d in query)
        searchList[i, j].Add(d);
      // You may want to sort searchList here for fast intra-bin queries.
    }
  }
  return searchList;
}
相关文章：