Inefficient java / arrays of unknown length
I am doing several methods that are used to find prime factors of a certain number. This is broken down into two functions, which are used as arrays. However, in both functions, the code is very inefficient. First I need to calculate the length of the array, create a new array of that length, and then use pretty much the same code to populate the array.
Is there a way to make an array of unknown width and push integers to the end of the array when 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;
}
}
source to share
You can use Arraylists
which are more dynamic than arrays.
However, in both functions, the code is very inefficient, since I first calculate the length of the array, create a new array of that length and then use almost the same code to fill the array
However, you will find that they Arraylists
do look dynamic, but underneath they do a similar thing. They start at size and make a copy of the base one Array
larger, and so on.
Another thing you can do if you know some upper bounds on how many numbers you will need to store is to implement your own container class. It can have a large array for storing numbers and a variable length for scrolling through items.
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;
}
}
.... etc.
This way you don't have to copy Array
to a new large, always assuming you are creating an instance NumberContainer
with a large enough size.
Hope it helps
source to share
you can use
ArrayList<Integer>
but this requires significant memory overhead due to automatic boxing.
Or you can use the excellent GNU Trove3 libraries. They contain TIntArrayList
that will take care of the resizing for you; and is essentially a field int[]
+. The logic for adding to it is approximately equal to:
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;
}
source to share
Use ArrayList if you still need fast index lookups. Otherwise, consider 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)
source to share
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 required time was 13 to 1 second.
I actually 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
document is documented, x / log x or x / log (x-1). When adding a new prime p
to [count], one in the worst case should copy the entire array.
source to share