我们得到一个子例程,它接受两个正的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
对,顺序是以递增的顺序给出返回值,直到它通过测试我们不关心测试:我们知道一些值对将通过测试,我们希望通过的返回值最小我们也不知道测试是否会在前100万个m
和n
值中通过,所以我们不能只构建整个值列表并对其进行排序。
我们如何以正确的顺序、合理有效地迭代m,n
?
我把它想象成一个多队列,不能是正确的名称:它叫什么?
我有一个由nextN[]
索引的数组m-1
,它存储了访问量最大的n
。由m
索引的另一个数组nextV[]
存储m-1
的返回值,因此我们不会对任何对多次调用f(m,nextN[m-1])
(这可以作为预优化省略,但当f()
需要很长时间运行或有副作用时,这是必需的优化)在每个步骤中,我们取最小的存储值并对其进行测试,然后用下一个值f
更新这两个数组中的元素。
问题是:应该使用什么样的数据结构和方法来提高多队列的效率和可理解性?我有快速破解,但我想要一个更好,更容易理解和维护的解决方案。
我是用python编写的,但同样的问题也适用于java、c等,用你喜欢的任何语言给出你的答案。(我不会用一种因晦涩难懂而被选中的语言来选择答案,但如果我能理解它并且它对我有帮助的话,我会加1。)
下面是一些示例代码:
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)
我觉得当
n
的大小变大时,这将花费很长时间在min(nextV)
上。最好的办法是什么? 最佳答案
你能做的就是把问题分成两步:
找一些(m,n)通过测试。
使用二进制搜索技术查找通过的最低值(m,n)。
你也可以在第一部分使用二进制搜索技术。
很难知道“通过测试”是什么意思。你知道返回值是太大还是太小吗?如果是,您可以通过减半或加倍来调整m
和n
,直到找到解决方案。
考虑到您的限制(即您描述的关系),对两个变量的二进制搜索应该不会太困难。
您可以跟踪优先级队列中的中间传递值。所以当你找到一个通过的,你可以把它放在队列上这可能是你下次通过的起点。您还需要跟踪找到的最高和最低传递值,以便可以更轻松地将搜索括起来。
而且,我想,您需要保留某种哈希表,以防止您多次生成相同的(m,n)
。
如果m
和n
具有某个定义的范围,这将变得更容易如果是“所有正整数”,我描述的技术是可能的,但是如果把它们放在括号里就容易多了。
关于arrays - 高效的多队列迭代,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/21119354/