About coding habits, a small java program as an example,

Question

This is a piece of code to solve a simple problem:)

you can find the statements of this problem with this link http://acm.bjtu.edu.cn/problem/detail?pid=1547

import java.util.ArrayList;

public class SumsOfPerfectPowers {

    ArrayList<Long> numList = new ArrayList<Long>(5000001);
    // status of whether a number is power number
    boolean[] result = new boolean[5000001];

    public SumsOfPerfectPowers() {
        numList.add((long) 0);
        numList.add((long) 1);
        for (int i = 2; i <= 2237; i++) {
            int j = 2;
            double value;
            while ((value = Math.pow(i, j)) <= 5000000) {
                numList.add((long) value);
                j++;
            }
        }

        int len = numList.size();
//      System.out.println(len);
        int value;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                value = (int) (numList.get(i) + numList.get(j));
                if (value <= 5000001) {
                    result[value] = true;
                }
            }
        }


    }

    static {
    }

    public int howMany(int a, int b) {
        int sum = 0;
        for(int i=a;i<=b;i++) {
            if(result[i]) {
                sum ++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        SumsOfPerfectPowers test = new SumsOfPerfectPowers();

        System.out.println(test.howMany(0, 1));
        System.out.println(test.howMany(5, 6));
        System.out.println(test.howMany(25, 30));
        System.out.println(test.howMany(103, 103));
        System.out.println(test.howMany(1, 100000));

    }

}

is this piece of code well coded?

any bad habits here?

what can be improved?

thank you:)

Answer 1

1. (long) 0 scructures should be written as 0L.

2. Access modifiers of numList and result should be private:

   private ArrayList<Long> numList = new ArrayList<Long>(5000001);
   // status of whether a number is power number
   private boolean[] result = new boolean[5000001];
   

3. ArrayList<...> reference types should be simply List<...>. See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces

   private List<Long> numList = new ArrayList<Long>(5000001);
   

4. 5000000 is a magic number. Using named constants instead of numbers would make the code more readable and less fragile. If you have to modify it's value it's easy to forget to do it everywhere. 2237 is also a magic number and a computed value. I'd create a MAX constant:

   private static final int MAX = 5000000;
   

   and use it everywhere, for example:

   private boolean[] result = new boolean[MAX + 1];
   

   then change 2237 to the following:

   final int maxSquare = (int) Math.ceil(Math.sqrt(MAX));
   for (int i = 2; i <= maxSquare; i++) { ... }
   

5. numList only used in the constructor, so it could be a local variable there instead of a field. Try to minimize the scope of variables. See Effective Java, Second Edition, Item 45: Minimize the scope of local variables.

6. Actually, I'd rename numList to perfectPowers since it stores perfect powers. I'd make the code more readable and easier to maintain.

7. You set the initial capacity of the list to 5000000 while it contains only about 2500 elements. It's a huge memory wasting. I'd use the default constructor of the ArrayList which use less memory.

   final List<Long> perfectPowers = new ArrayList<Long>();
   

8. Math.pow uses floating point numbers which are not always precise. For small numbers it's correct, but for big numbers it not:

   final long a = 97761243;
   final long aa = a * a;
   System.out.println("long            " + aa);
   System.out.println("Math.pow        " + ((long) Math.pow(a, 2)));
   System.out.println("BigInteger.pow: " + BigInteger.valueOf(a).pow(2).longValue());
   

   It prints:

   long            9557260632905049
   Math.pow        9557260632905048
   BigInteger.pow: 9557260632905049
   

   So, I'd change the while loop to the following:

   long value;
   while ((value = BigInteger.valueOf(i).pow(j).longValue()) <= MAX) {
       perfectPowers.add(value);
       j++;
   }
   

9. Some additional changes on the same loop would result the following:

   while (true) {
       final long value = BigInteger.valueOf(i).pow(j).longValue();
       if (value > MAX) {
           break;
       }
       perfectPowers.add(value);
       j++;
   }
   

   It does the same but I think it's easier to read.

10. In the first for loop I'd rename i to base and j to exponent, and the parameters of the howMany method to lowerBound and upperBound.

11. The empty static block is unnecessary:

    static {
    }
    

Answer 2

In addition to the other answers' points which don't need reiterating,

In almost all cases, a boolean[] can be replaced with a BitSet. It takes a significant (and deterministic) amount of space, and provides you with logical operations that, if you tried to do manually on a boolean[] you likely introduce subtle bugs into at worst, and would reinvent the wheel at best. :-)

Answer 3

A couple of comments:

1. Generally, it is recommended to declare variables as interface types for extensibility and implementation-neutral as much as possible. You would realize this when writing large programs. Based on this, numList would be of type List or Collection.
2. Instead of typecasting to (long), you can simply suffix the values with 'L' to make them long.
3. It is recommended to declare the member variables as private. The default scope is package private.
4. Didn't understand the purpose of empty static block!

Answer 4

That's how I would write it:

import java.util.ArrayList;
import java.util.List;

public class SumsOfPerfectPowers {

    private final static int SIZE = 5000001;
    private final boolean[] result = new boolean[SIZE];

    public SumsOfPerfectPowers() {
        List<Long> numList = fillNumList();
        fillResults(numList);
    }

    private List<Long> fillNumList() {
        List<Long> numList = new ArrayList<Long>(SIZE);
        numList.add(0L);
        numList.add(1L);
        int limit = 1 + (int) Math.sqrt(SIZE);
        for (int i = 2; i <= limit; i++) {
            for(long j = 2, value = i*i; value < SIZE; j++, value = (long) Math.pow(i, j)) {
                numList.add(value);
            }
        }
        return numList;
    }

    private void fillResults(List<Long> numList) {
        int len = numList.size();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int value = (int) (numList.get(i) + numList.get(j));
                if (value < SIZE) {
                    result[value] = true;
                }
            }
        }
    }

    public int howMany(int a, int b) {
        int sum = 0;
        for(int i=a; i<=b; i++) {
            sum += result[i] ? 1 : 0;
        }
        return sum;
    }

    //...
}

• usually members should be private (there are exceptions, e.g. for final members it might be OK to make them public)
• don't use magic numbers, give them a name. Or let the client provide them (maybe have a sensible default)
• prefer for loops, note that you can have multiple init and step parts. Generally, try to limit the scope of your variables
• the "assign then compare" pattern in while is not kewl
• try to make your methods smaller
• prefer interfaces over concrete classes (e.g. List)
• don't hold unnecessary data in your objects. For such a long list even uncle Bob would avoid it