用于大输入的Java优化算术和赋值运算符
我有一段代码必须在时钟速度方面运行得非常快。 该算法已经在O（N）中。 它需要2秒，需要1秒。 对于大多数A.length输入~100,000，除非特定行代码被调用极限次数，否则需要.3s。 （对于深奥的编程挑战）
它使用1,2，… N – > 1,3,4,10,15 ..的算术系列的计算，可以用n *（n + 1）/ 2 I循环通过这个等式数百个成千上万次。 我无法访问输入，也无法显示它。 我能够返回的唯一信息是运行所花费的时间。 特别是等式是：
s+=(n+c)-((n*(n+1))/2); s和c的值可以是0到10亿
n可以是0到100,000
在时钟速度方面写这个语句最有效的方法是什么？ 我听说除法需要更多的时间然后乘法，但除此之外我无法确定在一行或多个赋值行中写这个是否更有效。 除以乘法再乘以然后除以？ 还会创建自定义整数类型显着帮助吗？
根据请求编辑，带有小输入案例的完整代码（对不起，如果它很难看，我只是继续剥离它）：
public static void main(String[] args) { int A[]={3,4,8,5,1,4,6,8,7,2,2,4};//output 44 int K=6; //long start = System.currentTimeMillis();; //for(int i=0;i<100000;i++){ System.out.println(mezmeriz4r(A,K)); //} //long end = System.currentTimeMillis();; // System.out.println((end - start) + " ms"); } public static int mezmeriz4r(int[]A,int K){ int s=0; int ml=s; int mxl=s; int sz=1; int t=s; int c=sz; int lol=50000; int end=A.length; for(int i=sz;iA[mxl]){ mxl=i; }else if(A[i]<A[ml]){ ml=i; } if(Math.abs(A[ml]-A[mxl])=lol)return 1000000000; if(sz>1){ c+=sz; } }else{ if(A[ml]!=A[i]){ t=i-ml; s+=(t+c)-((t*(t+1))/(short)2); i=ml; ml++; mxl=ml; }else{ t=i-mxl; s+=(t+c)-((t*(t+1))/(short)2); i=mxl; mxl++; ml=mxl; } c=1; sz=0; } } if(s>1000000000)return 1000000000; return s+c; }
从挑战中退出：
检测到的时间复杂度：
上）
测试时间结果
示例测试0.290秒。 好
单个元素0.290秒。 好
双二元素0.290秒。 好
小function小function测试0.280秒。 好
small_random小随机序列长度= ~100 0.300 s。 好
small_random2小随机序列长度= ~100 0.300 s。 好
medium_random混沌介质序列长度= ~3,000 0.290 s。 好
large_range大范围测试，长度= ~100,000 2.200 s。 TIMEOUT ERROR运行时间：> 2.20秒，时间限制：1.02秒。
large_random随机大序列长度= ~100,000 0.310 s。 好
large_answer测试，答案很大，为0.320秒。 好
large_extreme所有最大值= ~100,000 0.340 s。 好
我没有权限validation所有输入。 和时间范围。 但是这个肯定会运行O（N）。 并有所改善。 跑，让我知道你的反馈。如有必要，我会提供详细信息
public static int solution(int[]A,int K){ int minIndex=0; int maxIndex=0; int end=A.length; int slize = end; int startIndex = 0; int diff = 0; int minMaxIndexDiff = 0; for(int currIndex=1;currIndexA[maxIndex]){ maxIndex=currIndex; }else if(A[currIndex]K){ minMaxIndexDiff= currIndex- startIndex; if (minMaxIndexDiff > 1){ slize+= ((minMaxIndexDiff*(minMaxIndexDiff-1)) >> 1); if (diff > 0 ) { slize = slize + (diff * minMaxIndexDiff); } } if (minIndex == currIndex){ diff = currIndex - (maxIndex + 1); }else{ diff = currIndex - (minIndex + 1); } if (slize > 1000000000) { return 1000000000; } minIndex = currIndex; maxIndex = currIndex; startIndex = currIndex; } } if ( (startIndex +1) == end){ return slize; } if (slize > 1000000000) { return 1000000000; } minMaxIndexDiff= end- startIndex; if (minMaxIndexDiff > 1){ slize+= ((minMaxIndexDiff*(minMaxIndexDiff-1)) >> 1); if (diff > 0 ) { slize = slize + (diff * minMaxIndexDiff); } } return slize; }
使用小代数，您可以简单地将表达式(n+c)-((n*(n+1))/2)改为c-((n*(n-1))/2)以移除加法运算。 然后你可以将除法除以2 ，向右移位1 ，这比除法更快。 尝试更换
s+=(n+c)-((n*(n+1))/2);
同
s+=c-((n*(n-1))>>1);
摆脱for循环中的System.out.println（）:)你会惊讶地发现你的计算速度会快多少
嵌套分配，即代替
t=i-ml; s+=(t+c)-((t*(t+1))/(short)2); i=ml; ml++; mxl=ml;
就像是
s+=((t=i-ml)+c); s-=((t*(t+1))/(short)2); i=ml; mxl=++ml;
有时会出现在OpenJDK源中。 它主要导致用*dup s替换*load字节码指令。 根据我的实验，它确实提供了非常小的加速，但它是超强的，我不建议手动编写这样的代码。
我会尝试以下内容并在每次更改后对代码进行分析，以检查速度是否有任何增益。
更换：
if(Math.abs(A[ml]-A[mxl])<=K)
通过
int diff = A[ml]-A[mxl]; if(diff<=K && diff>=-K)
更换
/2
通过
>>1
更换
ml++; mxl=ml;
通过
mxl=++ml;
也许避免相同元素的数组访问（java的内部边界检查可能需要一些时间）
因此在本地变量中至少存在A[i] 。
我会首先创建一个C版本，然后看看“直接访问金属”的速度有多快。 有可能，您正在尝试优化已经优化到极限的计算。
if(Math.abs(A[ml]-A[mxl])<=通过更快的自我计算的abs版本（内联，而不是方法调用），我会尝试消除此行！
转换为（短）没有帮助，但尝试右移操作符X >> 1而不是x / 2
删除System.out.println（）可以加速1000倍。但是要小心，否则你的整个算法可以被VM删除因为你不使用它。 旧代码：
for(int i=0;i<100000;i++){ System.out.println(mezmeriz4r(A,K)); }
新代码：
int dummy = 0; for(int i=0;i<100000;i++){ dummy = mezmeriz4r(A,K); } //Use dummy otherwise optimisation can remove mezmeriz4r System.out.print("finished: " + dummy);