Hallo,
ich bin gerade dabei eine Doppelt Verkettete Liste zu schreiben (ja, ich weiss es gibt sowas schon fertig mitgeliefert; spiel mich nur etwas rum damit ;-)
Dabei habe ich das Problem, dass das einfügen von neuen Elementen relativ lange dauert (bei 10.000.000 Objekten ca. 15 sekunden). Ich konnte das Problem schon auf einen Methodenaufruf reduzieren, hab aber keinen Dau warum der so lange dauert - ein vorheriger, ähnlicher Methodenaufruf ist wesentlich kürzer.
Hier die Codezeile:
Das setzen des vorherigen Elements (setPreviousElement) ist relativ schnell, das setzen des nächsten (setNextElement) langsam. Wenn ich zu testzwecken das letztere rausnehme brauchen 10.000.000 Methodenaufrufe nur ca. 1,5 Sekunden anstelle von 15.
Anbei der gesamte Quellcode - vielleicht hat ja jemand ne idee.
Danke und Grüsse,
Egon
ListElement.java:
ListManager.java:
ListTest.java:
ich bin gerade dabei eine Doppelt Verkettete Liste zu schreiben (ja, ich weiss es gibt sowas schon fertig mitgeliefert; spiel mich nur etwas rum damit ;-)
Dabei habe ich das Problem, dass das einfügen von neuen Elementen relativ lange dauert (bei 10.000.000 Objekten ca. 15 sekunden). Ich konnte das Problem schon auf einen Methodenaufruf reduzieren, hab aber keinen Dau warum der so lange dauert - ein vorheriger, ähnlicher Methodenaufruf ist wesentlich kürzer.
Hier die Codezeile:
Code:
public void insertFirst( T data )
{
ListElement<T> element = new ListElement<T>( startDummy_.getNextElement(), startDummy_, data );
startDummy_.getNextElement().setPreviousElement( element );
startDummy_.setNextElement( element );
elementCount_ ++;
}Das setzen des vorherigen Elements (setPreviousElement) ist relativ schnell, das setzen des nächsten (setNextElement) langsam. Wenn ich zu testzwecken das letztere rausnehme brauchen 10.000.000 Methodenaufrufe nur ca. 1,5 Sekunden anstelle von 15.
Anbei der gesamte Quellcode - vielleicht hat ja jemand ne idee.
Danke und Grüsse,
Egon
ListElement.java:
Code:
package egrath.test.LinkedList;
public class ListElement<T>
{
private ListElement next_;
private ListElement prev_;
private T data_;
public ListElement( ListElement<T> next, ListElement<T> prev, T data )
{
next_ = next;
prev_ = prev;
data_ = data;
}
public ListElement<T> getPreviousElement()
{
return prev_;
}
public void setPreviousElement( ListElement<T> element )
{
prev_ = element;
}
public ListElement<T> getNextElement()
{
return next_;
}
public void setNextElement( ListElement<T> element )
{
next_ = element;
}
public void setData( T data )
{
data_ = data;
}
public T getData()
{
return data_;
}
}ListManager.java:
Code:
package egrath.test.LinkedList;
import java.util.Iterator;
public class ListManager<T>
implements Iterable<T>, Iterator<T>
{
private ListElement<T> startDummy_;
private ListElement<T> endDummy_;
private ListElement<T> currentElement_;
private int elementCount_;
private int iterIndex_;
private ListElement<T> iterElement_;
public ListManager()
{
startDummy_ = new ListElement<T>( null, null, null );
endDummy_ = new ListElement<T>( null, null, null );
startDummy_.setNextElement( endDummy_ );
endDummy_.setPreviousElement( startDummy_ );
elementCount_ = 0;
}
public void insertLast( T data )
{
ListElement<T> element = new ListElement<T>( endDummy_, endDummy_.getPreviousElement(), data );
endDummy_.getPreviousElement().setNextElement( element );
endDummy_.setPreviousElement( element );
elementCount_ ++;
}
public void insertFirst( T data )
{
ListElement<T> element = new ListElement<T>( startDummy_.getNextElement(), startDummy_, data );
startDummy_.getNextElement().setPreviousElement( element );
startDummy_.setNextElement( element );
elementCount_ ++;
}
public void removeFirst()
{
startDummy_.getNextElement().getNextElement().setPreviousElement( startDummy_ );
startDummy_.setNextElement( startDummy_.getNextElement().getNextElement() );
elementCount_ --;
}
public void removeLast()
{
endDummy_.getPreviousElement().getPreviousElement().setNextElement( endDummy_ );
endDummy_.setPreviousElement( endDummy_.getPreviousElement().getPreviousElement() );
elementCount_ --;
}
public T getLast()
{
if( elementCount_ > 0 )
return endDummy_.getPreviousElement().getData();
else
throw new IndexOutOfBoundsException( "No Elements in List" );
}
public T getFirst()
{
if( elementCount_ > 0 )
return startDummy_.getNextElement().getData();
else
throw new IndexOutOfBoundsException( "No Elements in List" );
}
public T getIndex( int index )
{
return indexWorker( index, IndexWorkerAction.RETURN );
}
public void removeIndex( int index )
{
indexWorker( index, IndexWorkerAction.REMOVE );
}
private T indexWorker( int index, IndexWorkerAction action )
{
if( index > getLength() -1 )
throw new IndexOutOfBoundsException( String.format( "No element with given index (%d)", index ));
ListElement<T> current = null;
if( index > ( getLength() / 2 ))
{
int currentIndex = getLength() -1;
current = endDummy_.getPreviousElement();
while( currentIndex > index )
{
current = current.getPreviousElement();
currentIndex --;
}
}
else
{
int currentIndex = 0;
current = startDummy_.getNextElement();
while( currentIndex < index )
{
current = current.getNextElement();
currentIndex ++;
}
}
if( action == IndexWorkerAction.REMOVE )
{
current.getPreviousElement().setNextElement( current.getNextElement() );
current.getNextElement().setPreviousElement( current.getPreviousElement() );
return null;
}
else if( action == IndexWorkerAction.RETURN )
{
return current.getData();
}
return null;
}
public int getLength()
{
return elementCount_;
}
public void dumpList()
{
ListElement<T> current = startDummy_;
while( current != null )
{
System.out.println( current.getData() == null ? "NULL" : current.getData() );
current = current.getNextElement();
}
}
private enum IndexWorkerAction
{
REMOVE,
RETURN
}
// Implementation of Iterable and Iterator Interfaces
public Iterator<T> iterator()
{
iterIndex_ = -1;
iterElement_ = startDummy_;
return this;
}
public boolean hasNext()
{
if( iterIndex_ < getLength() -1 )
return true;
else
return false;
}
public T next()
{
iterIndex_ ++;
iterElement_ = iterElement_.getNextElement();
return iterElement_.getData();
}
public void remove()
{
removeIndex( iterIndex_ -1 );
}
}ListTest.java:
Code:
package egrath.test.LinkedList;
import java.util.Random;
import java.util.LinkedList;
public class ListTest
{
private static final long ELEMENTS = 10000000;
public static void main( String[] args )
{
ListManager<Integer> lm = new ListManager<Integer>();
Random rnd = new Random();
long myTime = 0;
long sunTime = 0;
/*
** Test for my implementation
*/
// Testing insert
long startTime = System.nanoTime();
for( long i = 0; i < ELEMENTS; i ++ )
{
lm.insertFirst( rnd.nextInt( 100 ) );
}
long endTime = System.nanoTime();
myTime += (( endTime - startTime ) / 1000000 );
System.out.println( "[MY]: Insert took: " + (( endTime - startTime ) / 1000000 ) + " ms" );
// Testing get
startTime = System.nanoTime();
for( Integer i : lm )
{
}
endTime = System.nanoTime();
myTime += (( endTime - startTime ) / 1000000 );
System.out.println( "[MY]: get took: " + (( endTime - startTime ) / 1000000 ) + " ms" );
// Testing remove
startTime = System.nanoTime();
for( long i = 0; i < ELEMENTS; i ++ )
lm.removeFirst();
endTime = System.nanoTime();
myTime += (( endTime - startTime ) / 1000000 );
System.out.println( "[MY]: remove took: " + (( endTime - startTime ) / 1000000 ) + " ms" );
/*
** Test for Sun's implementation of the LinkedList
*/
LinkedList<Integer> ll = new LinkedList<Integer>();
startTime = System.nanoTime();
for( long i = 0; i < ELEMENTS; i ++ )
{
ll.addFirst( rnd.nextInt( 100 ));
}
endTime = System.nanoTime();
sunTime += (( endTime - startTime ) / 1000000 );
System.out.println( "[SUN]: Insert took: " + (( endTime - startTime ) / 1000000 ) + " ms" );
startTime = System.nanoTime();
for( Integer i : ll )
{
}
endTime = System.nanoTime();
sunTime += (( endTime - startTime ) / 1000000 );
System.out.println( "[SUN]: get took: " + (( endTime - startTime ) / 1000000 ) + " ms" );
startTime = System.nanoTime();
for( long i = 0; i < ELEMENTS; i ++ )
{
ll.removeFirst();
}
endTime = System.nanoTime();
sunTime += (( endTime - startTime ) / 1000000 );
System.out.println( "[SUN]: remove took: " + (( endTime - startTime ) / 1000000 ) + " ms" );
// Print cummulative result
System.out.println( String.format( "My: %d Sun: %d", myTime, sunTime ));
}
}
