我将在底部解释问题的来源,但这是声明.假设我有两个非负整数列表,我将编写(A[0] ... A[n])和(B[0] ... B[m]).他们是严格递增的,所以A[i+1] > A[i]所有的i也是类似的B.我想n * m按照它们总和的递增顺序收集所有元素对.
所以,例如,如果A = (0 1 2)和B = (1 4),那么我想最终收集((0 1) (1 1) (2 1) (0 4) (1 4) (2 4)).如果有一个平局,我不关心我收集这两个元素的顺序.例如,如果A = (0 1)和B = (0 1),那么我不介意哪个混合术语,(0 1)或者(1 0),我先拿起.
显然,我希望这是合理有效的.我希望它有可能及时渐近m * n.具体来说,如果我对输入一无所知,我希望有序输入能使这个问题比同等问题更容易.当我第一次提出问题时,我在思考的是我们必须存储的状态量.我希望这可能是一个恒定的数额,但也许这是不现实的.(自那以后我尝试过的都失败了!)
代码实际上是用Lisp编写的,但我认为问题陈述几乎与它无关.输入最自然地会作为单链接列表,但无论如何我都必须提前撤消它们,所以如果随机访问是相关的,我可以将它们作为数组.如果它是相关的,我希望这主要是在非常小的列表上调用,因此运行时的大量常量项/常数因子可能会排除解决方案.(虽然我很想知道算法的想法!)
背景:我一直在查看Maxima的源代码,这是一个计算机代数系统,特别是它的代码,用于两个多项式的乘法.多项式以"稀疏格式"表示,因此x^5 + x^2 + 2可能显示为(5 1 2 1 0 …
假设我有一些可计算的谓词P,它将整数映射到bool.我知道这P 0是真的,我知道有些N P N是假的.我也知道这P n = false意味着P (n + 1) is false[*].我想找到最大的n,这P n是真的.
显然,我可以通过二分找到解决方案.不幸的是,评估P是昂贵的(可能需要一个小时左右).我还有一个有许多内核的闪亮服务器.
如果评估P持续时间并且我有2个线程(比方说),我可以看到我将如何进行搜索.我划分区间[a,b]上分成三段,并评估P (2a + b)/3和P (a + 2b)/3.两次评估完成后,我就会知道要归入的三个细分中的哪一个.使用两个线程,我的搜索时间将减少三分之一.优秀!
但是,如果评估P需要大量不同的时间呢？在我的具体例子中,它可能需要10秒到1个小时左右.再次假设我有2个线程并且如上所述划分了间隔.也许第一个线程(评估P (2a+b)/3)首先完成.我如何决定下一个的运行方式？
我想有一些信息理论或类似的链接,因为我正在尝试运行测试,根据我目前的知识,这将给我最多的信息.但这似乎应该是其他人调查过的问题 - 任何人都可以指出我的论文或类似内容吗？
[*]在我关心的具体情况中,测试涉及运行SMT求解器,尝试使用X≥n形式的一个额外约束找到约束问题的解X,其中n是上面的整数.
给定一个依赖记录类型：
Record FinPath : Type := mkPath { fp_head : S i;
fp_tail : FinPathTail fp_head
}.
和两个Path相同类型的对象，我想推断它们的头部和尾部是相等的。问题是我很快得到了这种形式的东西：
fpH : {| path_head := fp_head fp; path_tail := fpt_to_pt (fp_tail fp) |} =
{| path_head := fp_head fp'; path_tail := fpt_to_pt (fp_tail fp') |}
使用注入策略，我可以推断出fp_head fp = fp_head fp'这个术语：
existT (fun path_head : S i => PathTail path_head) (fp_head fp)
(fpt_to_pt (fp_tail fp)) =
existT (fun path_head : S i => PathTail path_head) (fp_head fp')
(fpt_to_pt (fp_tail …我有这段代码，基本上需要两个整数并将每个整数移位并相加。但是，添加之后，我得到了一个不正确的值。
我找到了一种解决方法（即通过将移位后的值存储在新的无符号int变量中并将其相加），但是我想了解为什么此方法不起作用：
void change(uint8_t in[3], uint16_t out[2]){
out[0] = in[0]<<2 + in[1]>>2;
printf("%u\n",in[0]<<2 ); // outputs 48 --- correct
printf("%u\n",in[1]>>2 ); // output 1 --- correct
printf("%u\n",out[0] ); // output 768 --- wrong, I expected 49
}
int main(int argc, char const *argv[])
{
uint8_t in[3] = {12,6,9};
uint16_t out[2];
change(in,out);
return 0;
}