Неэффективные java/массивы неизвестной длины

Question

Я делаю несколько методов, которые используются для нахождения простых коэффициентов определенного числа. Это разбивается на две функции, которые используют как массивы. Однако в обеих функциях код очень неэффективен. Сначала я должен подсчитать длину массива, создать новый массив этой длины, а затем использовать почти тот же самый код для заполнения массива.

Есть ли способ сделать массив неизвестной ширины и нажимать целые числа до конца массива, когда я их нахожу?

Вот мой код:

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

Вы можете использовать Arraylists, которые более динамичны, чем массивы.

Однако в обеих функциях код очень неэффективной, так как первый у меня есть подсчитать длину массива, создать новый массив той длины и затем использовать почти тот же самый код, чтобы заполнить массив

Однако вы обнаружите, что Arraylists действительно выглядят динамичными, но под ними они делают аналогичную вещь. Они начинаются с размера и составляют копию базового Array для большего размера и т. Д.

Еще одна вещь, которую вы можете сделать, если знаете некоторые верхние границы того, сколько чисел вам нужно хранить, - это реализовать свой собственный класс контейнера , Он может иметь большой массив для хранения чисел и переменной длины для прокрутки элементов.

Например:

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

} 

.... и так далее.

Таким образом, вам не нужно копировать Array на новый большой, всегда при условии, что вы создаете экземпляр NumberContainer с достаточно большим размером.

Надеется, что это помогает

Answer 2

Вы можете использовать ArrayList, который создается пустой, без определенного размера, и вы можете добавить (->add(Object o) или удалить (->remove(int index)) в любое время вы хотите

.

Answer 3

Вы можете использовать

ArrayList<Integer> 

, но это требует значительных накладных расходов памяти за счет автоматического бокса.

Или вы можете использовать отличные библиотеки GNU Trove3. Они содержат TIntArrayList, который позаботится об изменении размера для вас; и является по существу int[] + полем длины. Логика для добавления в то примерно:

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 4

ArrayList Используйте, если вам все еще нужен быстрый поиск по индексу. В противном случае рассмотрим LinkedList, как add = O (1).

Для 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> 

Для 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

Я сделал

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

и время, необходимое пошел от 13 до 1 секунды.

На самом деле я хотел бы попробовать

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; 

guessedPrimeCount документирована, х/журнал х или х/журнал (х-1). При добавлении нового простого p в [count], один в худшем случае должен скопировать весь массив.