java - 编程问题-抛硬币

Question

我需要优化以下代码以占用更少的内存。 我无法找出内存被浪费在哪里。它给出了正确的结果。 问题陈述可以在这里看到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]);
        }
    }
}

Answer 1

关于您的程序的一些一般性评论(与内存问题并不真正相关，但可能有助于解决它):

import java.util.Scanner;

public class FLIPCOIN4 {

你的类名有点奇怪 - 这是任务强制要求的吗？ (在 Java 中，类名通常使用驼峰命名法。FlipCoin 就是一个例子。)

    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]);

Scanner类的方法不仅仅只是 nextLine() - 如果您直接使用nextInt ，你的程序会短很多。

        int[] output = new int[Q];

你需要什么output数组为？您可以在生成后立即输出每个数字。这将为您节省 200 kB(如果他们的测试输入确实有 Q=50000)。

        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];

您可以使用[(N-1)/32 +1]在这里并避免这两种情况，但我不确定这是否真的更具可读性。

input数组的名称错误:它不是输入，但它代表硬币的当前状态。

        //initialize to 0 = tails
        for(int i=0;i<input.length;i++)
            {
                input[i] = 0;
            }

数组元素自动初始化为 0 (或 '\0' 或 0.0 或 null )，所以这个循环是完全没有必要的。

        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]);

如前所述，您可以使用 in.nextInt()这里同样容易。

我也认为s.split方法每次都会创建一个新的正则表达式模式，这不会花费太长时间，但仍然是多余的。

            // command==0 => if coins are to be flipped

对于命令，您实际上不需要将其解析为 int ，使用字符串比较也可以。

            if(command==0) {
                //if the coins range is over multiple numbers in array input[]
                if(RangeR/32>RangeL/32) {
                    if(RangeL%32==0)

您正在使用四个数字 RangeR/32 , RangeL/32 , RangeR%32和RangeL%32一遍又一遍地。将它们分配给适当的变量(甚至常量，使用 final ) - 如果您使用正确的名称，这首先会让您的程序更快一点，并且(更重要的是)更清晰。

                        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));

不要使用 Math.pow 进行 2 的小幂的整数幂运算。

2^x 可写为 1 << x (如果 0 <= x < 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))));

呵呵，这真是一个残酷的公式。您知道 Integer.MAX_VALUE + 1 == Integer.MIN_VALUE 吗？

                    if(RangeR/32 - RangeL/32 > 1) {
                        for(int i=RangeL/32+1; i <RangeR/32 ; i++) {
                            input[i] = input[i] ^ -1;
                        }
                    }

如果没有之前的 if 检查，你的循环将同样工作(那么它将是一个空循环)。

                }//if the coins range is contained in one single integer in input[]
                else if(RangeR/32==RangeL/32) {

这条评论看起来像是与右大括号相关，而实际上它与以下 if 相关。 .

                    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)) );

如前所述:将其放入另一个方法中，并且不要使用 Math.pow。

                }
            }// 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);

啊，你知道如何位移:-)

您也可以屏蔽它们，而不是将这些位移走。 final int mask = 1<<(32-RangeL%32) - 1<<(31-RangeR%32) ，或类似的，然后 temp1 = mask & input[RangeL/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]);
        }

(那么这个输出就没有必要了。)

    }
}

要考虑的另一件事:如果您以相反的方式对位进行排序，则不必在到处的指数中使用这些减法。

使用像 java.util.BitSet 这样的东西会让你的整个程序变得非常短，因为它会为你完成所有的位逻辑。