高效多队列迭代

Question

给我们一个子例程，它接受两个正int参数并返回一个int，假设它是def f(m,n): return (m+n)**2-n**2。输入值必须是正整数。返回的值相对于这两个输入都在增加:即f(m,n)<f(m+1,n)和f(m,n)<f(m,n+1)用于所有m和所有n。我们希望按照一个顺序迭代所有可能的m和n，以递增的顺序给出返回的值，直到它通过测试为止。我们不关心测试:我们知道一些值将通过它，我们希望最小的返回值通过。我们也不知道测试是否会在m和n的头100万个值中通过，所以我们不能只构建整个值列表并对其进行排序。 我们如何以正确的顺序，合理有效地迭代m,n？

我把它想象成一个多队列，它不可能是正确的名称:它叫什么？

我有一个由m-1索引的数组m-1，为该m存储了最大的访问n。另一个由m-1索引的数组m-1存储f(m,nextN[m-1])的返回值，因此对于任何对，我们不会多次调用f() (这可以省略为预优化，但是当f运行很长时间或有副作用时，这是必要的优化)。在每个步骤中，我们取最小的存储值并对其进行测试，并使用n的下一个值更新两个数组中的这些元素。

问题是:应该使用什么数据结构和方法来提高这种多队列的效率和可理解性？我有快速的黑客，但我想要一个更好，更容易理解和维护的解决方案。

我是用Python写的，但同样的问题也适用于Java、C等。用任何你喜欢的语言给出答案。(我不会用一种选择的语言来选择答案，但如果我能理解它，并且它是有用的，我会选择它。)

下面是一些示例代码：

from array import array
from math import sqrt

def findSmallestV(f,test):
    # initialize with m,n=1,1 filled out
    nextN = array('I', [1])
    nextV = array('I', [f(1,1)])
    while True:
        v = min(nextV)
        m = nextV.index(v)+1
        n = nextN[m-1]
        if test(v):
            return (m,n,v)
        nextN[m-1] += 1
        nextV[m-1] = f(m,n+1)
        # if we've just operated on the last column, put a value into the next column
        if m == len(nextN):
            nextN.append(1)
            nextV.append(f(m+1,1))


# example value function
def g(m,n): return (m+n)**2-n**2

# example test function
def h(v): return len(str(v))>5 and int(sqrt(v))**2 == v

ans = findSmallestV(g,h)
print("Smallest V: m=%d, n=%d -> %d" % ans)

当min(nextV)的大小越来越大时，我觉得这会花很长时间在nextV上。更好的方法是什么？

Answer 1

你能做的就是把这个问题分成两个步骤：

1. 找到一些通过测试的(m，n)。
2. 使用二进制搜索技术找到通过的最低值(m，n)。

您也可以在第一部分中使用二进制搜索技术。

很难知道什么是“通过考试”的意思。您知道返回的值是太大还是太小吗？如果是这样，您可以通过将m和n减半或加倍来调整它们，直到找到解决方案为止。

考虑到您的限制(即您描述的关系)，对两个变量的二进制搜索应该不会太困难。

您可以跟踪优先级队列中的中间传递值。因此，当您找到一个传递，您可以把它放在队列中。这可能是你下一次经历的起点。您还需要跟踪所找到的最高和最低的传递值，这样您就可以更容易地对搜索进行排序。

而且，我想，您会希望保留一个哈希表，这种哈希表将阻止您多次生成相同的(m,n)。

如果m和n有一些定义的范围，这就更容易了。如果它是“所有正整数”，我描述的技术是可能的，但是如果把它们放在括号里，就容易多了。

Answer 2

如注释中所建议的，优先级队列将导致一个很好的解决方案。

在算法运行过程中的任何时候，您都会考虑到一些点，而不是其他点。您将把这个划分边界上的点放入一个优先级队列中。更具体地说，您要维护一个优先级队列(可能是作为二进制堆实现的)，它是按v排序的三元组(m，n，v)，其中(m，n)是这个边界上的一个点，并且它的值是v。

在每次迭代时，从队列中提取最低值点并进行测试。如果它通过了，那就是答案。如果不是，将右边和上面的点连同它们的值放在队列中。

这将按原样工作，但效率很低，因为每个点都会被多次处理。为了防止这种情况发生，还可以在队列中的每个列中维护最低坐标的可增长数组，并为每一行中最左边的条目维护一个数组。每当您在队列中输入一个点时，首先检查该列中是否已经有一个较低的点，或者在同一行中左边是否有一个点。如果是这样的话，那就别进去了--反正以后会来的。