2

给定数组列表和大量设置时间，我需要快速找到每个数组的某个子跨度中的最小值。在概念上：

class SpanThing
{
     int Data;
     SpanThing(int[][] data) /// must be rectangulare
     {
         Data = data;
         //// process, can take a while
     }

     int[] MinsBruteForce(int from, int to)
     {
         int[] result = new int[data.length];
         foreach(int index, int[] dat; Data)
         {
             result[i] = int.max;
             foreach(int v; dat[from .. to]);
                result[i] = min(result[i], v);
         }
         return result;
     }
     int[] MinsSmart(int from, int to)
     {
          // same as MinsBruteForce but faster
     }
}

我目前关于如何做到这一点的想法是在每个节点包含相关跨度中的最小值的数据上构建一个二叉树。这样，在一行的跨度中找到最小值将包括仅找到组成它的树节点的最小值。该集合对于每一行都是相同的，因此可以计算一次。

有没有人看到这个想法有任何问题或知道更好的方法？

为了澄清，我正在谈论的树将被设置为根节点将包含整个行的最小值，对于每个节点，它的左子节点将具有父节点跨度左半部分的最小值，并且右边也是一样。

 0   5   6  2   7   9   4   1   7   2   8   4   2
 ------------------------------------------------
   | 5 | 6|   | 7 | 9 |   | 1 | 7 | 2 | 8 | 4 | 2  
 0 |   5  | 2 |   7   | 4 |   1   |   2   |   2  
   0      |   2       |   1       |       2
          0           |           1
                      0

这棵树可以映射到一个数组并以这样一种方式定义，即可以计算段边界，从而实现快速查找。

我正在优化的情况是我有一个固定的输入集和大量的前期时间，但随后需要对各种跨度进行许多快速测试。

4

3 回答 3

2

您描述的方法听起来像是您正在尝试进行某种记忆或缓存，但这只会在您重复检查相同的跨度或嵌套的跨度时对您有所帮助。

min([0..n])的一般情况将是O(n)，这就是您已经拥有的。

您的代码似乎更关心数组中的实际数字，而不是它们在数组中的顺序。如果您要反复检查这些跨度，是否可以先对数据进行排序，这可能是一个O(n log n)操作，然后是一堆O(1)操作？大多数语言在其标准库中都有某种内置的排序算法。

于 2009-02-07T20:13:29.080 回答
2

您提出的解决方案似乎使用恒定的空间开销、恒定的时间设置和查询的对数时间给出了答案。如果您愿意支付二次空间（即提前计算所有区间），您可以在恒定时间内得到答案。您的对数方案几乎肯定是首选。

如果有可能做得更好，我不会感到惊讶，但如果有一个简单的数据结构可以做得更好，我会感到震惊——实际上，对数时间几乎总是足够快。去吧。

于 2009-02-07T22:56:06.803 回答
0

目前尚不清楚我们如何使用您描述的树方法有效地表示间隔的层次结构。划分区间的方法有很多种——我们是否必须考虑每一种可能性？

像这样的简单方法就足够了：假设data是一个 N x M 数组。我会创建一个 M x M x N 数组，其中 entry(i,j,k)给出data(k,i:j). 数组条目将按需填充：

int[] getMins(int from, int to)
{
    assert to >= from;

    if (mins[from][to] == null)
    {
        mins[from][to] = new int[N];

        // populate all entries (from,:,:)
        for (int k = 0; k < N; k++)
        {
            int t = array[k][from];

            for (int j = from; j < M; j++)
            {
                if (array[k][j] < t)
                    t = array[k][j];

                mins[from][j][k] = t;
            }
        }
    }

    return mins[from][to];
}
于 2009-02-07T20:44:29.440 回答