java - structures - data structure中文



如何在列表數據結構中編寫clear()方法? (4)

我最近閱讀了一些框架源代碼,並註意到他們編寫了類似於列表的數據結構的clear()方法。 逐個刪除元素。

while (_arr.length > 0 )
{

    remove(_arr[0]);

}       

(也許上面看起來有點令人困惑,但這是因為這種語言本身的數組類型本身就是一個動態數組)或

 for (int i = 0; i < size; i++)
  { elementData[i] = null;}
 size = 0;

但我記得我寫過這樣的代碼。 該列表裝飾了本機數組類型,我寫了這樣的clear()方法。

 _arr=new Array();
 _size=0;

直接實例化新的本機數組類型。

這段代碼是用垃圾收集的語言編寫的。 所以我認為所有元素最終都會被收集,為什麼需要一個循環呢?新的會快嗎?


Answer #1

在創建新陣列或重新使用現有陣列時同意@Eran響應!

我想在這裡再添加一個信息。

clear()的源代碼如下:

public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

removeAll()的源代碼(在AbstractCollection中定義):

public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    Iterator<?> e = iterator();
    while (e.hasNext()) {
        if (c.contains(e.next())) {
            e.remove();
            modified = true;
        }
    }
    return modified;
}

clear()當然更快,因為它不必處理所有這些額外的調用。 所以最好將元素設置為null而不是刪除它。


Answer #2

在我看來,當創建一個新的數組並用零實例化時,它應該更慢。 在這種情況下,完成初始化和迭代以設置默認值。 在使用現有數組的情況下,僅完成迭代位。 因此,使用現有數組並迭代它應該更快。

在我們的項目中,我們經常在長時間運行的批處理過程中的某些計算過程中創建數組對象。創建一個池,您可以從中獲取並在使用後返回顯示一個顯著的改進。


Answer #3

應該是一個評論,但它不適合我認為。

還有一個事實是, besides分配一個數組可能太昂貴並清除以前的數組會更便宜,還有一個事實是以new byte[100]或其他形式分配一個數組也必須將內容歸零,這可能也很昂貴。

因此,在java-9中, String連接使用UNSAFE.allocateUninitializedArray ,它專門表示Allocates an array of a given type, but does not do zeroing. 當然還增加了:

此方法僅應用於非常罕見的情況,其中高性能代碼完全覆蓋目標數組,並且編譯器無法幫助消除歸零。 在絕大多數情況下,應該使用正常的Java分配。

這就是實際方法的樣子:

    @ForceInline
    private static byte[] newArray(int length, byte coder) {
        return (byte[]) UNSAFE.allocateUninitializedArray(byte.class, length << coder);
    }

這只是為了證明有些情況下創建數組實際上太昂貴了,而且它不便宜。 特別是因為數組可能需要連續的內存分配 - 但這不是規範所要求的。


Answer #4

我想動機是重新使用現有的後備陣列而不是分配一個新陣列。 這一點非常重要,特別是當後備陣列非常大時(在某些極少數情況下甚至可能意味著在舊的數組被垃圾收集之前無法分配新數組)。

分配新數組(以及收集舊數組的垃圾)可能比迭代現有數組並將所有元素的引用設置為null更耗時。

編輯:正如評論中所提到的,在基於數組的List中將引用設置為null是不夠的。 您還必須指明List為空。 在java.util.ArrayList這是通過將size屬性設置為0





data-structures