这是我在Visual C＃中的解决方案。
class ProblemEight
{
static byte[] input = new byte[] { 7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2, 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0 };
static long product, max = 0;
public static void SolutionEight()
{
for (short i = 0; i < 987; i++)
{
product = (long)input[i]
* input[i + 1]
* input[i + 2]
* input[i + 3]
* input[i + 4]
* input[i + 5]
* input[i + 6]
* input[i + 7]
* input[i + 8]
* input[i + 9]
* input[i + 10]
* input[i + 11]
* input[i + 12];
max = product > max ? product : max;
}
Console.WriteLine(max);
}
}
给出正确的答案，并且是最好的在Intel Core i5-5200U @ 2.2Ghz处理器上，
release的运行时间为20,000，0.0956389122543305 milliseconds的运行时间为。如何进一步提高速度？
[基准]
以下是答案中提供的所有出色解决方案的基准。这些实现在具有8GB RAM的Intel Core i5-5200U @ 2.2Ghz处理器上运行。在20,000次运行中计算出最快的时间，并且在任何实现中均未调用
Console.WriteLine(...)。 注意：我已经尽力在相同的标准上运行所有实现，而没有引入自己的优化（在必要时删除了输入的
string到int转换）JNS '位偏移优化
x64（调试）-0.241196671392629毫秒
x64（发布）-0.131561820759616毫秒
Forsvarir的多线程优化
x64（调试）-0.0797768487584903毫秒
x64（发布）-0.070446223172702毫秒
Risky Martin的倒数乘法（由brian_o实现）
x64（调试）-0.0121298132615248毫秒
x64（发布）-0.0181947198922873毫秒
Dennis_E的队列优化
x64（调试） -0.033590252108838毫秒
x64（发布）-0.0284584080366544毫秒
Falco的红利因子乘法
x64（调试）-0.0149290009372613毫秒
x64 （发布）-0.00793103174792009毫秒
domi1819的转换优化
x64（调试）-0.0102636881443672毫秒
x64（发布）-0.005598375351473毫秒
Brian_o的精心零跳
x64（调试）-0.00933062558578834毫秒
x64（发布）-0.00419878151360475毫秒
Zonker.in.Geneva和Mathreadler's对数方法（由brian_o实现）
x64（调试）-0.0121298132615248毫秒
x64（发布）-0.00466531279289417毫秒
[UPDATE]
如果您正在寻找更大的数据集来测试您的算法，那么我已经使用George Marsaglia的CMWC（带进位乘积）生成器（这里的源代码）生成了100万个随机数。
这里是文件
#1 楼
受Zonker.in.Geneva和mathreadler的思想启发。不会进行任何乘或除运算来找到正确的索引。仅在最后，当找到最佳运行时，它才会计算运行产品。
private static readonly byte[] logs = { 0, 0, 69, 109, 138, 160, 179, 194, 207, 219 };
public static long SolutionEightAlt19()
{
int bestScore = 0;
uint bestIndex = 0;
int runningScore = 0;
uint prevUsable = 0;
for (uint i = 0; i < 1000; ++i)
{
if (input[i] == 0)
{
prevUsable = 0;
runningScore = 0;
}
else
{
++prevUsable;
runningScore += logs[input[i]];
if (prevUsable > 13) runningScore -= logs[input[i - 13]];
if (prevUsable >= 13 && runningScore > bestScore)
{
bestScore = runningScore;
bestIndex = i - 12;
}
}
}
return (long)(input[bestIndex] * input[bestIndex + 1] * input[bestIndex + 2] * input[bestIndex + 3] * input[bestIndex + 4] * input[bestIndex + 5] * input[bestIndex + 6]) * (input[bestIndex + 7] * input[bestIndex + 8] * input[bestIndex + 9] * input[bestIndex + 10] * input[bestIndex + 11] * input[bestIndex + 12]);
}
评论
\ $ \ begingroup \ $
+1：这也是我的想法，尽管您可以使用if（input [i] == 0）{.. i = i + 12; }
\ $ \ endgroup \ $
– RBarryYoung
16年5月19日在18:43
\ $ \ begingroup \ $
嗯，我的i + 12根本无法工作，因为它仍然必须加载管路。 h不好，您说对了。
\ $ \ endgroup \ $
– RBarryYoung
16年5月20日在18:27
\ $ \ begingroup \ $
我的机器上的这一时间为0.0713792857312808毫秒！有趣的解决方案
\ $ \ endgroup \ $
– Paras
16年5月21日在1:37
\ $ \ begingroup \ $
所有答案都是不错的选择，但我之所以选择它，是因为它很有启发性，而且只需少量工作即可扩展！谢谢大家
\ $ \ endgroup \ $
– Paras
16年5月26日在22:00
\ $ \ begingroup \ $
您如何选择对数逼近的小数位数？根据我的信封背面，log（9）的255几乎不能精确到13位数字，219的危险是不准确的，而130恰好显示了所有8位标度值中的最低相对误差。
\ $ \ endgroup \ $
–灰胡子
19年4月6日在17:42
#2 楼
使用您的基本算法和一个计时单位，每次迭代平均得到130个滴答声（0.013毫秒）。 （注意：在Debug上运行）class ProblemEight
{
static byte[] input = { 7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2, 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0 };
static long product, max = 0;
static long[] timings = new long[1000];
public static void SolutionEight()
{
Stopwatch watch = new Stopwatch();
for (int iterations = 0; iterations < timings.Length; iterations++)
{
watch.Restart();
for (short i = 0; i < 987; i++)
{
product = (long)input[i]
* input[i + 1]
* input[i + 2]
* input[i + 3]
* input[i + 4]
* input[i + 5]
* input[i + 6]
* input[i + 7]
* input[i + 8]
* input[i + 9]
* input[i + 10]
* input[i + 11]
* input[i + 12];
max = product > max ? product : max;
}
watch.Stop();
timings[iterations] = watch.ElapsedTicks;
}
Console.WriteLine(timings.Average());
}
}
跳过零
if (input[i + 12] == 0)
i += 13;
跳过零设置新的最大值将其降低到〜60个滴答声（0.006毫秒）。
其他大多数答案都涉及到此问题，但这是非常重要的性能改进，不应忽略。 br />检查其他答案以获得更好的解释。
优化乘法
product = (long)(input[i] * input[i + 1] * input[i + 2] * input[i + 3] * input[i + 4] * input[i + 5] * input[i + 6])
* (input[i + 7] * input[i + 8] * input[i + 9] * input[i + 10] * input[i + 11] * input[i + 12]);
通过简单地添加两对括号，您可以将其降低到每次操作大约30个滴答（0.003毫秒）。魔术，是吧？
在.NET中，两个字节相乘不会返回一个字节。实际上，只要不涉及任何long，.NET中的所有整数乘法都将导致一个int。 （如果涉及到long，则双方都将强制转换为long并执行“ long乘法”）。
在您的代码中，进行了long乘法（因为9 ^ 13可能会溢出int这个想法是正确的），但是长乘法比int乘法的性能差。在您的示例中，执行了12个长乘法。
该优化背后的想法是将乘法分成较小的部分，特别是6和5个int乘法的块（因为9 ^ 7不能溢出int）然后进行最后的长乘法以提高性能。
我可以想到的其他优化没有提供任何明显的改进。
评论
\ $ \ begingroup \ $
哇，那是非常精明的指针！ * 0 *
\ $ \ endgroup \ $
– Paras
16年5月18日在12:55
\ $ \ begingroup \ $
通过应用这两个简单的重构，我已经达到了0.0643813165419395毫秒！谢谢
\ $ \ endgroup \ $
– Paras
16年5月18日在13:00
#3 楼
不幸的是，实现移位框架方法时，仅将前导数字除以最后一个数字，而不是将所有13个数字一遍又一遍地相乘，对于13个数字而言，这并不是一个好方法。通常算术单元的除法运算要比乘法慢得多（我记得某些CPU的除法系数为10-15），因此单个除法运算可能比13乘法慢。因此，我尝试了另一种方法：我只将乘数和因子相乘，直到所有乘积因子都大于乘数，然后再进行除法和乘法。 />您可以实现一些移位帧逻辑，如下所示：这可以使算法快两倍...
您可以通过乘以divisor_digits divs = d_i * d_（i + 1）...并乘以新的prods = d_（ i + 13）* d_（i + 14），并且仅在prods> divs时计算新的最大值，然后新的最大值为p_i / divs * prods
结果与原始实现和运行时相同在第一个基准测试中大约要快3-4倍。
Java代码：
Let a product p_i be the product of all digits d_i...d_(i+1)
A product p_(i+1) can only be bigger than p_i if the digit d_(i+13) is bigger than d_i
Because: p_(i+1) = p_i / d_i * d_(i+13)
评论
\ $ \ begingroup \ $
用Java的基准计时时间：原始时间：14.5毫秒，Zerro跳过：11.5毫秒，而ShiftFrame：4.3毫秒（循环的平均运行时间为100.000，预热：10.000轮）-基准测试代码：pastebin.com/R4uvgRNP
\ $ \ endgroup \ $
– Falco
16年5月18日在11:27
\ $ \ begingroup \ $
我将代码转换为C＃（必须删除所有决赛），算法的最快时钟输出为0.0779107236413326毫秒！这很棒！
\ $ \ endgroup \ $
– Paras
16年5月18日在12:35
\ $ \ begingroup \ $
我做了一些更多的基准测试和鲁棒性测试，我对代码进行了一些更改，并添加了对长时间溢出的检查，如果出现大量溢出，可能会发生。现在，它更安全且仍然一样快，如果您想使用代码，请更新以下更改:-)-我还在尝试其他数据类型，有时浮点算术比长计算要快...
\ $ \ endgroup \ $
– Falco
16年5月18日在14:09
\ $ \ begingroup \ $
太好了！保持更新。尝试是否可以简化嵌套结构，也许使用更轻量的数据类型（内存访问更快）
\ $ \ endgroup \ $
– Paras
16年5月18日在14:37
#4 楼
一种明显的优化是跳过其中包含0的节。在下面的代码中，我正在检查第13个数字是否为0，如果是，则跳过接下来的13个数字，其乘积将始终为0 ...int i = 0;
do
{
product = (long)input[i]
* input[i + 1]
* input[i + 2]
* input[i + 3]
* input[i + 4]
* input[i + 5]
* input[i + 6]
* input[i + 7]
* input[i + 8]
* input[i + 9]
* input[i + 10]
* input[i + 11]
* input[i + 12];
max = product > max ? product : max;
if (0 != input[i + 12]) i++;
else i += 13;
}
while (i < 987);
在现代CPU上，您可以从并行执行中获得一些好处。由于所需的执行次数非常少，因此您需要避免启动/结束线程，因为这可能会产生相当大的开销，因此您想使用线程池中的线程。您还希望最小化线程之间的争用，因此您不希望它们都更新相同的Max变量。一种基本策略是将处理分为多个部分（其中部分数是CPU的数量）。
每个窗口，计算该窗口的最大值，然后将其与最大值进行比较对于其他窗口。然后可以使用建议的各种其他方法来优化计算阶段。
这将导致类似以下的代码（我尚未真正验证上限检查，但是确实会得出正确的答案，因此我认为它已经足够近了。）
public static void SolutionEight()
{
var threads = Environment.ProcessorCount;
int windowSize = 1000 / threads;
var tasks = new Task<long>[threads];
for (int i = 0; i < threads; i++)
{
int windowStart = i;
tasks[windowStart] = Task<long>.Run(() => { return GetMax(windowStart * windowSize, (windowStart + 1) * windowSize - ((windowStart == threads - 1) ? 12 : 0)); });
}
long max = 0;
foreach (var task in tasks)
{
var result = task.Result;
max = max > result ? max : result;
}
Console.WriteLine(max);
}
static public long GetMax(int start, int end)
{
long max = 0;
for(int i = start; i < end - 12; i++)
{
if (HasZero(i)) continue;
// Optimised as suggested by @Falco
if (i > 0 && input[i - 1] > input[i + 12]) continue;
// Optimised as suggestd by @domi1819
long product = (long)(input[i]
* input[i + 1]
* input[i + 2]
* input[i + 3]
* input[i + 4]
* input[i + 5]
* input[i + 6])
*( input[i + 7]
* input[i + 8]
* input[i + 9]
* input[i + 10]
* input[i + 11]
* input[i + 12]);
max = product > max ? product : max;
}
return max;
}
static bool HasZero(int i)
{
return !(input[i] != 0 &&
input[i + 1] != 0 &&
input[i + 2] != 0 &&
input[i + 3] != 0 &&
input[i + 4] != 0 &&
input[i + 5] != 0 &&
input[i + 6] != 0 &&
input[i + 7] != 0 &&
input[i + 8] != 0 &&
input[i + 9] != 0 &&
input[i + 10] != 0 &&
input[i + 11] != 0 &&
input[i + 12] != 0);
}
评论
\ $ \ begingroup \ $
如果索引i + 13的数字也为0，该怎么办？这是我们必须承担的风险吗？还是有办法解决？
\ $ \ endgroup \ $
– Paras
16年5月18日在8:23
\ $ \ begingroup \ $
@ParasDPain当第13位数字为0时，您可以进行一次if扫描，直到获得没有0的13位数字。是否值得，取决于在13位数字中的0位数。彼此。尽管显然可以直观地检查特定问题的存在，但在一组数字的开头存在相同的风险。
\ $ \ endgroup \ $
– forsvarir
16年5月18日在8:34
\ $ \ begingroup \ $
这是一个非常极端的解决方案！我喜欢它！正在等待基于线程的实现。
\ $ \ endgroup \ $
– Paras
16年5月18日在13:13
\ $ \ begingroup \ $
您的实施最快的运行时间为0.159553697516981毫秒。我尝试删除for并使代码线性化，但是最多只能达到0.14695 ...毫秒
\ $ \ endgroup \ $
– Paras
16年5月18日在14:14
\ $ \ begingroup \ $
@ParasDPain有趣的是，我的解决方案比原来的解决方案提高了50％，但我使用的是相当老的i7笔记本电脑。可能是您的CPU正在快速运行代码，因此线程的成本高于执行的成本。
\ $ \ endgroup \ $
– forsvarir
16年5月18日在14:25
#5 楼
我实现了Risky Martin提出的使用倒数乘法的建议，到目前为止，它似乎是我表现最好的。谁知道？我感到有些惊讶，因为我认为执行
1.0 / input[i - 13]（除法）与除法一样昂贵，但是也许有一种优化，因为一个是long，另一个是byte ？巫毒教？还是我错了？进行泛化时，请注意精度误差，但对于此特定输入来说似乎不错。
public static long SolutionEightAlt8()
{
double best = 0;
double prevProduct = 1;
uint prevUsable = 0;
for (uint i = 0; i < 1000; ++i)
{
if (input[i] == 0)
{
prevUsable = 0;
prevProduct = 1;
}
else
{
++prevUsable;
prevProduct *= input[i];
if (prevUsable > 13)
{
double recip = 1.0 / input[i - 13];
prevProduct *= recip;
}
best = prevProduct > best ? prevProduct : best;
}
}
return (long)best;
}
评论
\ $ \ begingroup \ $
互惠不仅仅是一个部门。有一种比将数字除以1.0更快的方法，并且我们需要将“ input [i]”强制转换为两倍，尽管如果您未打开脚踏标志，编译器可能会为您这样做。但是反正还是不错的。使用“ -Ofast”进行编译应自动执行此类数值捷径，但也会破坏精度。
\ $ \ endgroup \ $
–宏线程
16年5月18日在17:29
\ $ \ begingroup \ $
确实很有趣，但是，这仍然比我在当前硬件上的实现（一点点）慢（一点点），而不是基准代码。
\ $ \ endgroup \ $
–多米
16年5月18日在17:40
\ $ \ begingroup \ $
我想您可以将倒数存储在数组中，这样循环中就不会有除法了。因此，您可以编写类似prevProduct * = reciprocals [input [i-13]];之类的东西。有趣的是，在循环中计算倒数比在循环中除法要快。
\ $ \ endgroup \ $
–Risky Martin
16年5月19日在0:40
\ $ \ begingroup \ $
@RiskyMartin我实际上在随后的实验中尝试过该方法，得知它没有任何作用，感到非常惊讶！由于只有10个可能的数字，因此我将一个预先计算的“这是任何数字的倒数”直接作为静态只读数组放入类中。但是没有变化！也许它以某种方式被缓存了？
\ $ \ endgroup \ $
–brian_o
16年5月19日在1:07
\ $ \ begingroup \ $
由于除法是精确的（将两个整数除以产生一个整数），因此应使用2adic除法而不是实数除法。我假设算术模2 ^ 64会长吗？除数的存在使事情比平时更加复杂。您可以做的是使表满足inverse [y] * y == 8（mod 2 ^ 64）。然后，要将x除以y，可以对long进行算术运算并计算（x * inverse [y]）>> 3。
\ $ \ endgroup \ $
–user14393
16年5月19日在17:32
#6 楼
跳过0很好，但实际上您要确保连续的13个数字都不为0。在示例数据中，从索引157开始，您具有以下数字字符串（
874715852386305071569329096329522744304355766896648），其中我分为0和非0：874 715 852 386 3（13位）0 5 0 715 693 29 0 963 295 227 443（12位数字）0 435 576 689 664 8（13位数字）仅跳过前0个（因为
digits[i+13] == 0），就可以执行24个不必要的计算，所有这些计算都等于0。此外，一旦确认13个连续数字都不为0，则如果
digits[i+13] == 1，则可以跳过它，因为乘积相同（if digits[i] == 1）或更小（if digits[i] > 1）。评论
\ $ \ begingroup \ $
我在上面列出的“跳过零点”部分上进行扩展，尝试进一步优化它。.很抱歉，如果我不清楚。但是，我确实看到了（发布后），brian_o已经在那条路上了
\ $ \ endgroup \ $
–Zonker.in.Geneva
16年5月18日在17:05
#7 楼
这是一个展开展开乘法，也执行0序列跳过。我做了一个类似的功能，可以进行除法和单次乘法，但是这个速度更快。BTW，我喜欢原件的可读性。
编辑（更多推理）：
考虑解决方案的一种方法是说有988个子字符串，而您需要找到最佳子字符串。
计算索引为
i的子字符串的分数具有一定的成本。如果您可以优化该成本，那就太好了。 （请参阅domi1819的回答，或我的原始照片（参加聚会的人！）。成本计算：除以非共享的“旧”数字，再除以“新”数字，在我的实验中，通过使用我的硬件，我发现完全计算分数（非自举，13个优化数字乘法）的效果要好于除法-and-multiply方法论，所以我坚持使用13-num-multiply方法，但是重要的是，我检查了一下！如果我们要查找26位字符串，答案肯定会有所不同。 > 您的第一种方法进行了987个评分，但是正如其他人所谈到的那样，零的存在使许多计算变得不必要。
因此弄清楚可以消除哪些评分非常重要，但是需要权衡：零跳变不是免费的！
没有零跳变：987个得分
domi1819：（便宜的零跳跃方法！）此输入的430分
我的解决方案：（更昂贵的零跳跃方法）此输入的263分
在我的硬件上，我的方法似乎比domi1819更好，并且我相信这是因为我的得分更少。我一直在研究算法，并尝试做更便宜的零跳。到目前为止，我最好的实现方式是330个得分，其总体性能比我当前发布的答案还要快。我觉得仍有改进的空间。
您提到并行化。可能是个不错的策略，但请记住，就像零跳过一样，这不是免费的！我尚未进行实验，但听起来很有趣。我的直觉告诉我，这么小的投入是不值得的，但是谁知道呢！量度！
最后编辑：
我想我已经走得很远了。这是我最后一个性能最好的功能（对于此输入，使用我的硬件，编译为x86）。它进行一些零跳过（中等成本），最终计算出330分。我进行的其他更复杂的尝试来计算更少的分数并没有跑赢它，可能是因为它们花了太多时间来计算不计算的内容，或者是因为它们弄乱了缓存行。谁知道。
public static long SolutionEightAlt3()
{
long best = 0;
uint prevUsable = 0;
for (uint i = 0; i < 1000; ++i)
{
if (input[i] == 0)
{
prevUsable = 0;
}
else
{
++prevUsable;
if (prevUsable >= 13)
{
long prevProduct = (long)(input[i - 12] *
input[i - 11] *
input[i - 10] *
input[i - 9] *
input[i - 8] *
input[i - 7]) *
(long)(input[i - 6] *
input[i - 5] *
input[i - 4] *
input[i - 3] *
input[i - 2] *
input[i - 1] *
input[i]);
best = prevProduct > best ? prevProduct : best;
}
}
}
return best;
}
评论
\ $ \ begingroup \ $
谢谢，我喜欢连续0的迭代检查器。另外，是否有必要明确地将长整型转换为两次，一次就不够？
\ $ \ endgroup \ $
– Paras
16年5月18日在13:17
\ $ \ begingroup \ $
@ParasDPain我很确定这是不必要的，但我认为它在运行时不会花费任何费用。我还认为通过明确意图可以提高可读性。 （如果我了解到它实际上在运行时会花一些钱，那么我将其删除。）
\ $ \ endgroup \ $
–brian_o
16年5月18日在14:02
\ $ \ begingroup \ $
实际上，（long）int1 * int2的IL代码将两个int都转换为long。当一侧存在长整数时，编译器决定将另一侧也强制转换为长整数以执行长乘法。
\ $ \ endgroup \ $
–多米
16年5月18日在16:10
\ $ \ begingroup \ $
是的，您可以通过反汇编long l =（long）int1 * int2;来进行确认，这将导致ldloc.X（将变量X加载到堆栈上），conv.i8（将堆栈从上到下转换） ldloc.Y（将变量Y加载到堆栈上），conv.i8（将堆栈顶部从顶部投射到长方），mul（乘以两个顶部堆栈元素并将结果存储在堆栈上）和stloc.Z（将堆栈顶部存储到变量Z中并删除堆栈顶部） ）。如您所见，尽管您只告诉它投射左侧，但它正在进行两次投射。
\ $ \ endgroup \ $
–多米
16年5月18日在16:41
#8 楼
一种优化是对2的倍数使用位移位。不确定这是否有意义，但是理论上应该更快；）。下面的代码示例还进行了一些结构上的优化：public class ProblemEight
{
static readonly long[] input = new long[] { 7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2, 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0 };
const int ADJACENT_DIGITS_LENGTH = 13;
public static void SolutionEight()
{
var max = 0L;
for (short i = 0; i < input.Length - ADJACENT_DIGITS_LENGTH; i++)
{
var product = 1L;
for (int j = 0; j < ADJACENT_DIGITS_LENGTH; j++)
{
var val = input[i + j];
switch (val)
{
case 1:
break;
case 2:
product <<= 1;
break;
case 4:
product <<= 2;
break;
case 8:
product <<= 3;
break;
default:
product *= val;
break;
}
}
max = product > max ? product : max;
}
Console.WriteLine(max);
}
}
编辑：在上面的代码中添加了案例1。
也许也可以让编译器优化代码。这就要求编译器在编译时知道具体的数字：
switch(val)
{
case 2:
product *= 2;
break;
case 3:
product *= 3;
break;
//...
}
评论
\ $ \ begingroup \ $
我使用相同的时钟机制运行该解决方案，在20,000次运行中，最快的运行时间为0.181480667643583毫秒。位移一定会使它更快，但是第二for循环也会使其变慢。您能否详细说明var是否更快以及使用Math.Max（...）等。
\ $ \ endgroup \ $
– Paras
16年5月18日在6:47
\ $ \ begingroup \ $
var对性能没有任何影响，因为它实际上很长（编译器知道它一定很长）。我认为Math.Max（...）对性能也没有影响...但是我没有对其进行检查。
\ $ \ endgroup \ $
– JanDotNet
16年5月18日在6:52
\ $ \ begingroup \ $
@ParasDPain：您是对的...嵌套的for循环会减慢它的速度（我已经固定好以优化代码的可读性，而我没有看到它^^）。因此，另一个优化将是删除第一个for循环。这可以通过使用T4模板来完成。
\ $ \ endgroup \ $
– JanDotNet
16年5月18日在6:55
\ $ \ begingroup \ $
使用var或显式类型之间没有什么区别，因为它会导致相同的编译。
\ $ \ endgroup \ $
– JanDotNet
16年5月18日在7:10
\ $ \ begingroup \ $
@ParasDPain这是一个不同的问题（这个问题在网络上有很多答案）。
\ $ \ endgroup \ $
–菲利普·肯德尔（Philip Kendall）
16年5月18日在10:17
#9 楼
一种优化是跳过包含0的序列。另一种优化是，如果前一个序列不是以0开头，则通过将前一个乘积除以前一个序列中的第一个数字并乘以当前中的最后一个数字来计算当前序列序列。我希望您有代码将字符串中的1000位数字转换为数字数组。我知道您追求速度，但是很多时候可读性和可维护性更为重要，在这些情况下，您希望使用循环或LINQ而不是将增量编码为索引13次来计算乘积。您还应该使用类似
int count = input.Count() - sequenceLength;之类的值来计算当前的987硬编码值。评论
\ $ \ begingroup \ $
同意，我目前正在尝试实现对0的跳过和移码以减少乘法运算。商定的可读性很重要，但是我正在与朋友竞争，因此愿意牺牲它。是的，我当然写了一个函数，将字符串转换为字节数组
\ $ \ endgroup \ $
– Paras
16年5月18日在8:36
\ $ \ begingroup \ $
我不确定移动帧是否会带来好处，在许多算术单位中，除法比乘法慢约10-15倍，这会使单除法比13乘法更昂贵...但是您可以测试...
\ $ \ endgroup \ $
– Falco
16年5月18日在9:08
\ $ \ begingroup \ $
我将测试并发布结果
\ $ \ endgroup \ $
– Paras
16年5月18日在9:30
\ $ \ begingroup \ $
@ParasDPain除了进行除法运算外，您还可以尝试将数字的倒数存储在数组中并将它们相乘或使用相应的乘法移位运算。
\ $ \ endgroup \ $
–Risky Martin
16年5月18日在10:39
#10 楼
基本上所有的乘法都是13次。当有13个数字的乘积
a1 * a2 * ... * a13时，找到下一个乘积所需要做的就是除以a1并乘以a14。您不必再将a2乘以a13。处理此问题的明显方法是使用队列。
您可以进行的第二个优化是开始一个新序列。遇到0时为13。（如果不检查0，则会得到
DivideByZeroException）。首先，让我们做一个扩展方法，从数字字符串中获取所有数字。 ：
public static IEnumerable<int> Digits(this string s) {
foreach (char c in s) yield return c - '0';
}
然后解决问题8：
public long SolveProblem008() {
private const string input = "731..."; //I'm not going to display the entire string here...
return GreatestConsecutiveProduct(13, input.Digits());
}
static long GreatestConsecutiveProduct(int length, IEnumerable<int> digits) {
var buffer = new Queue<int>(length);
long product = 1L, max = long.MinValue;
foreach (int input in digits) {
if (buffer.Count < length) { //We don't have 13 digits yet
if (input == 0) { //Encountered a 0: start from scratch
product = 1L;
buffer.Clear();
} else {
buffer.Enqueue(input);
product *= input;
}
} else {
if (input == 0) { //Encountered a 0: start from scratch
product = 1L;
buffer.Clear();
} else {
product /= buffer.Dequeue();
buffer.Enqueue(input);
product *= input;
if (product > max) max = product;
}
}
}
return max;
}
评论
\ $ \ begingroup \ $
我运行了它，但得到了错误的答案-2090188800（可能是溢出，最大乘积超过了int.MaxValue）。你能确认一下吗
\ $ \ endgroup \ $
– Paras
16年5月18日在10:18
\ $ \ begingroup \ $
是的，我将方法，产品和队列的类型更改为long并获得了正确的答案，但最快的20,000次运行只能达到0.122231195173827，告诉我可以改进实施
\ $ \ endgroup \ $
– Paras
16年5月18日在10:21
\ $ \ begingroup \ $
@ParasDPain是的，我忘了。问题曾经是找到一个5个连续数字的序列（如果我没记错的话），它很适合int。他们后来将其更改为13。我编辑它返回很长
\ $ \ endgroup \ $
– Dennis_E
16年5月18日在10:24
\ $ \ begingroup \ $
此优化将对非常大的n（> 13）有所帮助，但是在大多数算术单位上，除法（乘数10-15）比乘法慢得多。因此，单个除法可能会慢于13个乘法。而且这没有考虑流水线，分支预测和L1 / L2缓存...
\ $ \ endgroup \ $
– Falco
16年5月18日在10:47
\ $ \ begingroup \ $
您是否实际测试过并发现它可以提高性能？这似乎..真的不太可能。正如Falco所说，对于我们正在谈论的位数，优化本身不但令人质疑，但真正的问题是您在那里存在的可怕的不可预测的分支。这只是两个主要问题-队列的开销可能不会有太大关系，但是无论如何都不是免费的。
\ $ \ endgroup \ $
– Voo
16年5月18日在13:24
#11 楼
似乎有人已经尝试过我的第一个本能来制作一个“移动框架”，该框架将尾部的旧数字除以前面的数字（1 mul和1 div而不是12 mul）。但是div的速度比muls还要慢，而且还会弄糟管道，所以也许这就是为什么它不能很好地起作用的原因。所以第一层是原始数字n1，n2，n3，...。第二层是n1 * n2，n3 * n4，...第三层n1 * n2 * n3 * n4，....等。我们可以在8处停下来，因为那将是2的乘方，正好低于13。在最好的情况下，两个乘法而不是12。我毕竟可以将实现留为练习，毕竟该项目旨在帮助人们更好地进行编程。
我只是意识到我没有测试方法。即使是带有优化标志的未优化代码的当前状态，也只需7-17 µs即可运行，这对于进行任何可靠的测试来说太少了。也许我们可以提出一些更长的模型数据，从而迫使每个算法花费更长的时间。
评论
\ $ \ begingroup \ $
我将在问题中发布一百万个随机数序列，以用数据大小衡量基准算法的效率
\ $ \ endgroup \ $
– Paras
16年5月21日在3:13
\ $ \ begingroup \ $
听起来很棒。也许发布一个链接到文件，而不是问题文本中的所有数字。
\ $ \ endgroup \ $
–宏线程
16年5月21日在3:29
\ $ \ begingroup \ $
我已经通过文件链接更新了问题（对延迟表示抱歉）
\ $ \ endgroup \ $
– Paras
16年5月21日在14:40
#12 楼
我还有一个想法，那就是移位帧的一种变化。 。确定最大乘积的13个连续数字也与确定最大SUM的相同连续数字....因此，如果我们采用移位帧方法但减去第一个元素并加上接下来的元素，我们避免分裂。我们只跟踪将给我们最大的总和的索引。在循环结束时，我们基于从GreatestSumIndex开始的13个连续数字进行一次乘法。
自然地，我们仍然要避免任何具有零的序列。
由于将近凌晨02:00，我将在早上处理代码。除非有人要刺它......
评论
\ $ \ begingroup \ $
“确定最大积的13个连续数字也是确定最大SUM的相同连续数字”不幸的是，没有。 5555555555555的数字总和小于9191919191916，但是其数字乘积要大得多。
\ $ \ endgroup \ $
–brian_o
16年5月19日在2:29
\ $ \ begingroup \ $
尽管$ \ log（ab）= log（a）+ log（b）$，它仍可以使用对数定律，但遗憾的是，大多数计算日志的方法都相当慢。
\ $ \ endgroup \ $
–宏线程
16年5月19日在15:56
\ $ \ begingroup \ $
mathreadler您只需计算每个数字的对数一次。
\ $ \ endgroup \ $
–user1008646
16年5月19日在17:03
\ $ \ begingroup \ $
是的，我同意，但是计算仍然很慢。我在其他stackexchange和溢出站点中读到，日志的c实现在现代intel cpus上可能需要35个周期，如果有良好的管道，乘法运算平均只需要花费很少或少于一个周期。但是，如果每个位数只有一次，那也许是值得的。
\ $ \ endgroup \ $
–宏线程
16年5月21日在4:19
\ $ \ begingroup \ $
@mathreadler您可以在运行时进行任何日志计算而无需做任何工作。将数字1-9的对数表示形式放入静态数组中。
\ $ \ endgroup \ $
–brian_o
16年5月22日在13:31
评论
您可以使用并行处理吗？您不是自己想出欧拉专案的目的吗？ projecteuler.net/about
我已经完成了Euler挑战。不到一秒钟就可以找到正确的解决方案（我达到了0.9ms），但有兴趣了解它可以优化多远
记住要同时编译和基准测试x86和x64。您可能会得到令人惊讶的结果。
这不是有关代码审查的第一个Euler项目问题。实际上，如果您选中此标签project-euler，则可以看到更多标签。另外，用欧拉计画来命名问题的目的是使人们知道他们在寻找什么，而不会意外地破坏自己，因为老实说，如果有人想寻找解决方案，他们已经在互联网上了。 “项目欧拉：x”可以帮助那些不想破坏答案的人。您可以在此处了解更多信息