Inefficient java / arrays of unknown length

Question

I am making a few methods that are used for finding the prime factors of a certain number. This is broken down into two functions which both use arrays. However, in both functions the code is very inefficient. First I have to count the length of the array, make a new array of that length and then use almost the exact same code to populate the array.

Is there a way I can make the array unknown width and push integers to the end of the array as I find them?

Here is my code:

public class JavaApplication7{
    public static void main(String[] args) {
        System.out.println(Arrays.toString(primeFactors(85251)));
    }
    public static int[] primeFactors(int num){
        int[] factors = primesUpTo(num);
        int originalNum = num;
        int i = 0;
        int count = 0;
        while(num != 1){
            if(num % factors[i] == 0){
                num /= factors[i];
                i = 0;
                count++;
            }else{
                i++;
            }
        }
        int[] primeFactors = new int[count];
        i = 0;
        count = 0;
        while(originalNum != 1){
            if(originalNum % factors[i] == 0){
                originalNum /= factors[i];
                primeFactors[count] = factors[i];
                i = 0;
                count++;
            }else{
                i++;
            }
        }
        return primeFactors;
    }
    public static int[] primesUpTo(int upTo){
        int count = 0;
        int num = 2;
        while(num <= upTo){
            boolean isPrime = true;
            for(int div = 2; div <= num / 2; div++){
                isPrime = num % div == 0 ? false : isPrime;
            }
            count += isPrime ? 1 : 0;
            num++;
        }
        int i = 0;
        num = 2;
        int[] primes = new int[count];
        while(num <= upTo){
            boolean isPrime = true;
            for(int div = 2; div <= num / 2; div++){
                isPrime = num % div == 0 ? false : isPrime;
            }
            if(isPrime){
                primes[i] = num;
                i++;
            }
            num++;
        }
        return primes;
    }    
} 

Answer 1

You can use a ArrayList which is created empty with no specific size and you can add (-> add(Object o) or remove (-> remove(int index)) anytime you want.

Answer 2

You can use an

ArrayList<Integer>

but this requires substantial memory overhead due to auto-boxing.

Or you can use the excellent GNU Trove3 libraries. These contain an TIntArrayList, which takes care of the resizing for you; and is essentially an int[] + a length field. The logic for appending to then is roughly:

double[] array = new double[10]; // Allocated space
int size = 0; // Used space

void add(int v) {
    if (size == array.length) {
        array = Arrays.copyOf(array, array.length * 2);
    }
    array[size++] = v;
}

Answer 3

You could use Arraylists that are more dynamic than Arrays.

However in both functions the code is very inefficient as first i have to count the length of the array, make a new array of that length and then use almost the exact same code to populate the array

However, you will find that Arraylists do seem dynamic but underneath they do a similar thing. They start with a size and make a copy of the underlying Array to a bigger one etc.

Another thing you can do if you know some upper bounds to how many numbers you will have to store is to implement you own container class. It can have a big array to hold the numbers and a length variable, for looping through the elements.

For example:

public class NumberContainer(){

    private int[] elements;
    private int numOfElements;

    public NumberContainer(int size){
        elements = new int[size];
        numOfElements = 0;
    }

    //add a number

    public void add(int x){
        elements[numOfElements] = x;
        numOfElements++;
    }

    //get length
    public int length(){
        return numOfElements;
    }

}

....and so on.

This way you don't have to copy an Array to a new large one, allways assuming that you instantiate the NumberContainer with a large enough size.

Hope this helps

Answer 4

Use an ArrayList if you still need fast retrieval by Index. Otherwise consider a LinkedList, as add = O(1).

For LinkedList

get(int index) is O(n)
add(E element) is O(1)
add(int index, E element) is O(n)
remove(int index) is O(n)
Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>

For ArrayList

get(int index) is O(1) <--- main benefit of ArrayList<E>
add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)
remove(int index) is O(n - index) (i.e. removing last is O(1))
Iterator.remove() is O(n - index)
ListIterator.add(E element) is O(n - index)

When to use LinkedList over ArrayList?

Answer 5

I did

        boolean isPrime = true;
        for (int div = 2; div <= num / 2; div++) {
            if (num % div == 0) {
                isPrime = false;
                break;
            }
            // Instead isPrime = num % div == 0 ? false : isPrime;
        }

and the time needed went from 13 to 1 second.

Actually I wanted to try

public static int guessedPrimeCount(int upTo) {
    if (upTo < 10) {
        return 10;
    }
    return (int) (upTo / Math.log10(upTo - 1));
}

public int[] addToPrimes(int[] primes, int count, int p) {
    if (count >= primes.length) {
        primes = Arrays.copyOf(primes, count + 10);
    }
    primes[count] = p;
    return primes;
}

primes = addToPrimes(primes, count, num);
++count;

The guessedPrimeCount is documented, x/log x, or x/log(x-1). On adding a new prime p at [count], one in the worst case has to copy the entire array.