编程问题-抛硬币
我需要优化以下代码以占用更少的内存。 我无法找出内存被浪费在哪里。它给出了正确的结果。 问题陈述可以在这里查看 http://www.codechef.com/problems/FLIPCOIN/
import java.util.Scanner;
public class FLIPCOIN4 {
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
//take N = no of coins, Q = no of commands as input
String s = in.nextLine();
String[] str = s.split(" ");
int N = Integer.parseInt(str[0]);
int Q= Integer.parseInt(str[1]);
int[] output = new int[Q];
int[] input;
//input - array of integers (one integer for 32 coins)
if(N%32>0)
input = new int[N/32 + 1];
else
input = new int[N/32];
//initialize to 0 = tails
for(int i=0;i<input.length;i++)
{
input[i] = 0;
}
int out = 0;
int temp1 = 0;
int temp2 = 0;
int command = 0;
int RangeL = 0;
int RangeR = 0;
//looping over all Q commands
while(Q>0) {
s = in.nextLine();
str = s.split(" ");
//command - command code
//RangeL,RangeR - range of coins which are affected
command = Integer.parseInt(str[0]);
RangeL = Integer.parseInt(str[1]);
RangeR = Integer.parseInt(str[2]);
// command==0 => if coins are to be flipped
if(command==0) {
//if the coins range is over multiple numbers in array input[]
if(RangeR/32>RangeL/32) {
if(RangeL%32==0)
input[RangeL/32] = input[RangeL/32] ^ -1;
else if(RangeL%32==1)
input[RangeL/32] =
input[RangeL/32] ^ Integer.MAX_VALUE;
else
input[RangeL/32] =
input[RangeL/32] ^ (int)Math.pow(2, 32-(RangeL%32));
if(RangeR%32==0)
input[RangeR/32] = input[RangeL/8] ^ Integer.MIN_VALUE;
else
input[RangeR/32] =
input[RangeR/8] ^
(Integer.MIN_VALUE
+ ( Integer.MAX_VALUE +1-
(int) Math.pow(2, 31-(RangeL%32))));
if(RangeR/32 - RangeL/32 > 1) {
for(int i=RangeL/32+1; i <RangeR/32 ; i++) {
input[i] = input[i] ^ -1;
}
}
}//if the coins range is contained in one single integer in input[]
else if(RangeR/32==RangeL/32) {
if(RangeL%32==0 && RangeR%32==0)
input[RangeL/32] = input[RangeL/32] ^
Integer.MIN_VALUE;
else if(RangeL%32==0 && RangeR%32==1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MIN_VALUE + (int) Math.pow(2, 30));
else if(RangeL%32==0 && RangeR%32 >1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MIN_VALUE + Integer.MAX_VALUE +1 -
(int) Math.pow(2, 31-(RangeR%32)));
else if(RangeL%32==1 && RangeR%32 ==1)
input[RangeL/32] = input[RangeL/32] ^
(int) Math.pow(2, 30);
else if(RangeL%32==1 && RangeR%32 >1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MAX_VALUE +1 -
(int) Math.pow(2, 31-(RangeR%32)));
else
input[RangeL/32] = input[RangeL/32] ^
((int) Math.pow(2, 32-(RangeL%32)) -
(int) Math.pow(2, 31-(RangeR%32)) );
}
}// command==1 => no of heads is to be reported
else if(command==1) {//if the coins range is contained in a single integer
if(RangeR/32 == RangeL/32) {
temp1 = input[RangeL/32]<< RangeL%32;
temp1 = temp1 >>> RangeL%32;
temp1 = temp1 >>> (31 - RangeR%32);
temp1 = temp1 << (31 - RangeR%32);
output[out] = Integer.bitCount(temp1);
}
//if the coins range is over multiple numbers in array input[]
else if(RangeR/32>RangeL/32) {
temp1 = input[RangeL/32]<< RangeL%32;
temp1 = temp1 >>> RangeL%32;
temp2 = input[RangeL/32] >>> (31 - RangeR%32);
temp2 = temp2 << (31 - RangeR%32);
output[out] =
Integer.bitCount(temp1)+ Integer.bitCount(temp2);
}
if(RangeR/32 - RangeL/32 > 1) {
for(int i=RangeL/32+1; i <RangeR/32 ; i++) {
output[out] = output[out] + Integer.bitCount(input[i]);
}
}
out++;
}
Q--;
}
for(int i =0;i<out;i++) {
System.out.println(output[i]);
}
}
}
I need to optimize the following code to take less memory.
I cant find out where the memory is being wasted. It is giving the correct results.
The problem statement can be seen here http://www.codechef.com/problems/FLIPCOIN/
import java.util.Scanner;
public class FLIPCOIN4 {
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
//take N = no of coins, Q = no of commands as input
String s = in.nextLine();
String[] str = s.split(" ");
int N = Integer.parseInt(str[0]);
int Q= Integer.parseInt(str[1]);
int[] output = new int[Q];
int[] input;
//input - array of integers (one integer for 32 coins)
if(N%32>0)
input = new int[N/32 + 1];
else
input = new int[N/32];
//initialize to 0 = tails
for(int i=0;i<input.length;i++)
{
input[i] = 0;
}
int out = 0;
int temp1 = 0;
int temp2 = 0;
int command = 0;
int RangeL = 0;
int RangeR = 0;
//looping over all Q commands
while(Q>0) {
s = in.nextLine();
str = s.split(" ");
//command - command code
//RangeL,RangeR - range of coins which are affected
command = Integer.parseInt(str[0]);
RangeL = Integer.parseInt(str[1]);
RangeR = Integer.parseInt(str[2]);
// command==0 => if coins are to be flipped
if(command==0) {
//if the coins range is over multiple numbers in array input[]
if(RangeR/32>RangeL/32) {
if(RangeL%32==0)
input[RangeL/32] = input[RangeL/32] ^ -1;
else if(RangeL%32==1)
input[RangeL/32] =
input[RangeL/32] ^ Integer.MAX_VALUE;
else
input[RangeL/32] =
input[RangeL/32] ^ (int)Math.pow(2, 32-(RangeL%32));
if(RangeR%32==0)
input[RangeR/32] = input[RangeL/8] ^ Integer.MIN_VALUE;
else
input[RangeR/32] =
input[RangeR/8] ^
(Integer.MIN_VALUE
+ ( Integer.MAX_VALUE +1-
(int) Math.pow(2, 31-(RangeL%32))));
if(RangeR/32 - RangeL/32 > 1) {
for(int i=RangeL/32+1; i <RangeR/32 ; i++) {
input[i] = input[i] ^ -1;
}
}
}//if the coins range is contained in one single integer in input[]
else if(RangeR/32==RangeL/32) {
if(RangeL%32==0 && RangeR%32==0)
input[RangeL/32] = input[RangeL/32] ^
Integer.MIN_VALUE;
else if(RangeL%32==0 && RangeR%32==1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MIN_VALUE + (int) Math.pow(2, 30));
else if(RangeL%32==0 && RangeR%32 >1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MIN_VALUE + Integer.MAX_VALUE +1 -
(int) Math.pow(2, 31-(RangeR%32)));
else if(RangeL%32==1 && RangeR%32 ==1)
input[RangeL/32] = input[RangeL/32] ^
(int) Math.pow(2, 30);
else if(RangeL%32==1 && RangeR%32 >1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MAX_VALUE +1 -
(int) Math.pow(2, 31-(RangeR%32)));
else
input[RangeL/32] = input[RangeL/32] ^
((int) Math.pow(2, 32-(RangeL%32)) -
(int) Math.pow(2, 31-(RangeR%32)) );
}
}// command==1 => no of heads is to be reported
else if(command==1) {//if the coins range is contained in a single integer
if(RangeR/32 == RangeL/32) {
temp1 = input[RangeL/32]<< RangeL%32;
temp1 = temp1 >>> RangeL%32;
temp1 = temp1 >>> (31 - RangeR%32);
temp1 = temp1 << (31 - RangeR%32);
output[out] = Integer.bitCount(temp1);
}
//if the coins range is over multiple numbers in array input[]
else if(RangeR/32>RangeL/32) {
temp1 = input[RangeL/32]<< RangeL%32;
temp1 = temp1 >>> RangeL%32;
temp2 = input[RangeL/32] >>> (31 - RangeR%32);
temp2 = temp2 << (31 - RangeR%32);
output[out] =
Integer.bitCount(temp1)+ Integer.bitCount(temp2);
}
if(RangeR/32 - RangeL/32 > 1) {
for(int i=RangeL/32+1; i <RangeR/32 ; i++) {
output[out] = output[out] + Integer.bitCount(input[i]);
}
}
out++;
}
Q--;
}
for(int i =0;i<out;i++) {
System.out.println(output[i]);
}
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
关于您的程序的一些一般性评论（与内存问题并不真正相关，但可能有助于解决它）：
您的类名有点奇怪 - 这是任务以某种方式强制要求的吗？
（在 Java 中，对于类名，通常使用驼峰式大小写。
FlipCoin就是一个示例。）您正在这个非常大的方法中进行所有处理。更好地构建代码，将其放入多个方法中，每个方法只有一个任务。
Scanner类比nextLine()拥有更多的方法 - 如果您直接使用nextInt，您的程序会短很多。您需要
output数组做什么？您可以在生成后立即输出每个数字。这将为您节省 200 kB（如果他们的测试输入确实有 Q=50000）。您可以在这里使用
[(N-1)/32 +1]并避免这两种情况，但我不确定这是否真的更具可读性。input数组有一个错误的名称：它不是输入，但它代表硬币的当前状态。数组元素自动用
0（或'\0'或0.0或null）初始化，所以这个循环完全没有必要。大多数这些变量最好在首次使用时声明（并初始化）。
如前所述，您可以在这里轻松使用
in.nextInt()。我还认为 s.split 方法每次都会创建一个新的正则表达式模式，这不会花费太长时间，但仍然是多余的。
对于命令，您实际上不需要将其解析为
int，使用字符串比较也可以。您正在使用四个数字
RangeR/32、RangeL/32、RangeR%32和RangeL%32一遍又一遍。将它们分配给适当的变量（甚至常量，使用final） - 如果您使用正确的名称，这首先会使您的程序更快一些，并且（更重要的是）更清晰。不要使用 Math.pow 进行 2 的小幂的整数幂运算。
2x 可写为
1 << x（如果 0 <= x < 32）。呵呵，这真是一个残忍的公式。您知道 Integer.MAX_VALUE + 1 == Integer.MIN_VALUE 吗？
如果没有之前的 if 检查，您的循环将同样工作（那么它将是一个空循环）。
该注释看起来与右大括号相关，但实际上与下面的
if相关。如前所述：将其放入另一个方法中，并且不要使用 Math.pow。
啊，你知道如何进行位移位:-)
你也可以屏蔽它们，而不是位移位。
final int mask = 1<<(32-RangeL%32) - 1<<(31-RangeR%32)，或类似的，然后temp1 = mask &输入[RangeL/32]。我之前所说的也适用于这个循环。
此时你可以输出结果，但根本没有这个数组。
（那么这个输出就没有必要了。）
要考虑的另一件事是：如果您以相反的方式对位进行排序，则不必在到处的指数中使用这些减法。
使用 java.util.BitSet 之类的东西会让你的整个程序变得非常短，因为它为你完成了所有的位逻辑。
Some general remarks about your program (not really related to the memory problem, but may help to solve it):
Your class name is a bit strange - was this somehow mandated by the task?
(In Java, for class name one usually uses camel-case.
FlipCoinwould be an example here.)You are doing all your processing inside this really large method. Better structure your code, put it in several methods which each have only one task.
The
Scannerclass has more methods than onlynextLine()- if you would use directlynextInt, your program would be shorter by quite a bit.What do you need the
outputarray for? You could simply output each number as soon as produced. This would save you 200 kB (if their test input has really Q=50000).You could have used
[(N-1)/32 +1]here and avoid the two cases, but I'm not sure this is really more readable.The
inputarray has a wrong name: it is not the input, but it represents the current state of the coins.Array elements are automatically initialized with
0(or'\0'or0.0ornull), so this loop is totally unnecessary.Most of these variables would be better declared (and initialized) where they are first used.
As said before, you could have used
in.nextInt()here as easily.I also think the
s.splitmethod is creating a new regex-Pattern each time, which does not take too long, but still is superfluous.And for the commands, you would not really need to parse it as an
int, using String comparison would work too.You are using the four numbers
RangeR/32,RangeL/32,RangeR%32andRangeL%32over and over again. Assign them to proper variables (or even constants, withfinal) - this firstly would make your program a bit faster, and (more importantly) more legible, if you are using the right names.Don't use Math.pow for integer exponentation with small powers of two.
2x is writable as
1 << x(if 0 <= x < 32).Huh, this is a cruel formula. Did you know that Integer.MAX_VALUE + 1 == Integer.MIN_VALUE?
Your loop would work the same without the if-check before (it would be a empty loop then).
This comment looks like it would relate to the closing brace, while it in reality relates to the following
if.As said before: put this in another method, and don't use Math.pow.
Ah, you know how to bit-shift :-)
Instead of shifting the bits off, you could have masked them, too.
final int mask = 1<<(32-RangeL%32) - 1<<(31-RangeR%32), or similar, and thentemp1 = mask & input[RangeL/32].What I said before is valid for this loop, too.
At this point you could output the result, and not have this array at all.
(This output would be not necessary then.)
Another thing to think about: If you ordered the bits the other way around, you would not have to use these subtractions in the exponents everywhere.
And using something like java.util.BitSet would make your whole program very short, since this does all the bit-logic for you.
那么，让我们看一下您的程序，特别是您的内存分配。
在这里您将创建两个大数组。如果 N 和 Q 都最大为 50000，则它们应该只需要 206250 字节，再加上一点开销。
这是在循环中完成的，每个循环创建一个新字符串（从输入读取）和一个新字符串[]。也许还有一个新的正则表达式模式和匹配器（我不知道这些是否已被修改）。但无论如何，您只保留这些对象直到下一次迭代，因此垃圾收集器应该能够丢弃它们。
总而言之，您的程序没有理由需要 177 MB 来运行 50000（短）行长输入。
我认为CodeChef的评估程序有点愚蠢，你不应该担心它说的是什么。也许它为程序提供了一个非常大的堆，这样它们就不需要进行任何垃圾收集，然后在它们达到 177 MB 时杀死它们。 （它也拒绝了我的答案，因为运行时间太长。）
我将在另一个答案中为您提供一些有关您的程序的一般提示。
So, lets take a look at your program, especially your memory allocations.
Here you are creating two big arrays. If N and Q are both maximally 50000, these should only take 206250 bytes, plus a bit overhead.
This is done in a loop, each creates a new string (read from the input) and a new string[]. Maybe also a new Regexp-pattern and matcher (I don't know whether those are chached). But anyway, you retain these objects only until the next iteration, so the garbage collector should be able to throw them away.
All in all, there is no real reason your program should take 177 MB for running with a 50000 (short) lines long input.
I think the evaluation program of CodeChef is a bit stupid, and you should not worry about what it said. Maybe it gives the programs an very big heap so they would not need to do any garbage collection, and then kills them when they reach 177 MB. (It rejected my answer, too, for running too long.)
I'll give you some general tips about your program in another answer.