如何提高java中的雙向鏈表的性能？

所以我有一個任務，要求我修改一個遍歷雙向鏈表的方法。我得到它的工作，但我們的教授。如果方法的工作速度比他提供的方法快，那麼只能以滿分的方式進行設置。該列表是10000個元素。如何提高java中的雙向鏈表的性能？

原來這是怎麼遍歷該列表：

private Node getNodeAt(int givenPosition) 
{ 
    Node currentNode = firstNode; 

    for(int counter = 1; counter < givenPosition; counter++) 
    { 
     currentNode = currentNode.next; 
    } 

    return currentNode;

大約需要1331毫秒。這是我們被告知要遍歷列表的一種方法：

private Node getNodeAt2(int givenPosition) 
    { 
    Node currentNode = firstNode; 
    middleNode = firstNode; 
    boolean nearFront = givenPosition <= (numberOfEntries/4); 
    boolean nearFrontMid = (givenPosition < (numberOfEntries/2)) && (givenPosition > (numberOfEntries/4)); 
    boolean nearBackMid = (givenPosition >= (numberOfEntries/2)) && (givenPosition < ((3*numberOfEntries)/4)); 
    boolean nearLast = (givenPosition >= ((3*numberOfEntries)/4)); 

    middlePosition = numberOfEntries/2; 

    for(int counter = 1; counter < middlePosition; counter++) 
    { 
     middleNode = middleNode.next; 
    } 

    if(nearFront){ 
     currentNode = firstNode; 
    for(int counter = 1; counter < givenPosition; counter++) 
     { 
     currentNode = currentNode.next; 
     } 
    } 
    if(nearFrontMid){ 
     currentNode = middleNode; 
     for(int counter = 1; counter <= (middlePosition - givenPosition) ; counter++) 
     { 
     currentNode = currentNode.previous; 
     } 

    } 
    if(nearBackMid){ 
     currentNode = middleNode; 
     for(int counter = 1; counter <= (givenPosition - middlePosition); counter++) 
     { 
     currentNode = currentNode.next; 
     } 

    } 
    if (nearLast){ 
     currentNode = lastNode; 
     for(int counter = 1; counter <= (numberOfEntries - givenPosition); counter++) 
    { 
     currentNode = currentNode.previous; 
    } 
    } 

    return currentNode;

這一次大約需要800毫秒，即使是速度更快，他預計其採取的第一個方法所花費的時間的四分之一。那可能嗎？

來源

2014-09-23 Devin_Kinh

你能解釋第二種方法比第一種方法快嗎？ – Thilo 2014-09-23 01:49:28

首先，對我而言，你的'if'語句沒有其他任何東西將它們分開，所以如果不止一個是真的，那麼不止一次。他們的觀點似乎是找到最接近的近似節點，只能從那裏遍歷，所以我認爲你最多隻想輸入一個塊。 – Brandon 2014-09-23 01:50:07

@Brandon：看看條件（'nearXXX'）是如何構建的，只有其中一個會運行。但是，我沒有看到這比簡單的迭代更快，除非切點被緩存在某個地方。 – Thilo 2014-09-23 01:52:07

思考：

1）在middleNode總是搜索到的第二解決方案，但它不需要每次（特別是在如果一部分nearfront和nearlast）。如果middleNode剛好在需要時確定，它會更快。

2）迭代更快，因爲該方法知道middleNode在哪裏。也許「quaterNodes」有幫助。

3）有時輪迴迭代比循環快。而不是循環呼叫一個更靠近所需位置一步的方法。 10000個元素不會有任何限制。

來源

2014-09-23 06:19:33

如何提高java中的雙向鏈表的性能？

回答

相關問題