Java的优化算术和赋值运算符为大输入 [英] Java Optimizing arithmetic and Assignment Operators for large input
问题描述
我有一张code必须在时钟速度方面的运行速度非常快。该算法已经在O（N）。它需要2秒，它需要花费1秒。对于大多数则为a.length输入〜10万需要.3s除非code在特定线路被调用的次数一个极端的数量。 （对于深奥的编程挑战）
I have a piece of code that must run extremely fast in terms of clock speed. The algorithm is already in O(N). It takes 2seconds, it needs to take 1s. For most A.length inputs ~ 100,000 it takes .3s unless a particular line of code is invoked an extreme number of times. (For an esoteric programming challenge)
它使用一个计算的算术系列1,2，... N的 - > 1,3,4,10,15 .. 用n *（N + 1）/ 2 psented可重新$ P $ 余环路通过这个方程数十万次。 我没有访问输入，亦不能显示它。我能够得到返回的唯一信息是花了运行时间。 特别是方程是：
It uses a calculation of the arithmetic series that 1,2,..N -> 1,3,4,10,15.. that can be represented by n*(n+1)/2 I loop through this equation hundreds of thousands of times. I do not have access to the input, nor can I display it. The only information I am able to get returned is the time it took to run. particularly the equation is:
s+=(n+c)-((n*(n+1))/2);
S和C可具有值范围从0到10亿
s and c can have values range from 0 to 1Billion
n可以0至100,000
n can range 0 to 100,000
什么是写这个声明，时钟速度方面最有效的方法是什么？ 我听到司需要更多的时间，那么乘，但除此之外，我不能确定是否一行或多行转让写作，这是更有效的。 除法和乘法与乘和然后除以？ 还将创建自定义的整数类型显著帮助？
What is the most efficient way to write this statement in terms of clock speed? I have heard division takes more time then multiplication, but beyond that I could not determine whether writing this in one line or multiple assignment lines was more efficient. Dividing and multiplying versus multiplying and then dividing? Also would creating custom integers types significantly help?
编辑根据要求，充分code以小投入的情况下（抱歉，如果它的丑陋，我只是不停地剥离下来）：
Edit as per request, full code with small input case (sorry if it's ugly, I've just kept stripping it down):
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;i<end;i++){
if(A[i]>A[mxl]){
mxl=i;
}else if(A[i]<A[ml]){
ml=i;
}
if(Math.abs(A[ml]-A[mxl])<=K){
sz++;
if(sz>=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;
}
这是挑战返回：
Returned from Challenge:
检测到的时间复杂度：
O（N）
测试时间结果
例如 例如测试0.290秒。确定
example example test 0.290 s. OK
单 单个元素0.290秒。确定
single single element 0.290 s. OK
双 两个元素0.290秒。确定
double two elements 0.290 s. OK
small_functional 小功能测试0.280秒。确定
small_functional small functional tests 0.280 s. OK
small_random 小的随机序列长度为100〜0.300秒。确定
small_random small random sequences length = ~100 0.300 s. OK
small_random2 小的随机序列长度为100〜0.300秒。确定
small_random2 small random sequences length = ~100 0.300 s. OK
medium_random 混沌中的序列长度= 3000〜0.290秒。确定
medium_random chaotic medium sequences length = ~3,000 0.290 s. OK
large_range 大范围的测试，长度=〜100000 2.200秒。超时错误 运行时间：> 2.20秒，时限：1.02秒
large_range large range test, length = ~100,000 2.200 s. TIMEOUT ERROR running time: >2.20 sec., time limit: 1.02 sec.
large_random 随机大序列长度=〜100000 0.310秒。确定
large_random random large sequences length = ~100,000 0.310 s. OK
large_answer 测试与大型回答0.320秒。确定
large_answer test with large answer 0.320 s. OK
large_extreme 所有的最大值=〜100000 0.340秒。确定
large_extreme all maximal value = ~100,000 0.340 s. OK
推荐答案
我没有获得验证所有输入。和时间范围。但是这一次运行O（N）的肯定。并得到了改善。跑，让我知道你feedback.i会提供详细信息，如果有必要
I dont have access to validate all inputs. and time range. but this one runs O(N) for sure. and have improved. run and let me know your feedback.i will provide details if necessary
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;currIndex<end;currIndex++){
if(A[currIndex]>A[maxIndex]){
maxIndex=currIndex;
}else if(A[currIndex]<A[minIndex]){
minIndex=currIndex;
}
if( (A[maxIndex]-A[minIndex]) >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;
}
这篇关于Java的优化算术和赋值运算符为大输入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
