未知長度的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。

然而，在這兩種功能的代碼是非常低效的，因爲第i個具有 計數陣列的長度，使該長度的一個新的數組和 然後使用幾乎相同的代碼來填充所述陣列

然而，你會發現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被記錄在案，X /日誌x或X /日誌（X-1）。 在[count]處添加新的素數p時，在最壞的情況下需要複製整個陣列。