Auswertung Softwarepraktikum - Gruppe pi

Zufallszahlen

[Meßbedingungen] - [Durchführung] - [Laufzeiten] - [Graphiken] - [Detaillierte Resultate] - [Bemerkungen]

Meßbedingungen

Durchführung der Messung

Für die Messung wird eine Datei mit vorgegebener Anzahl an Zufallszahlen eingelesen. Die Zufallszahlen werden in die PriorityQueue mit insert() eingefügt und danach wieder mit extractMin() ausgelesen (damit wird der Datensatz sortiert). Dies wird für jede Queue fünfmal wiederholt.

public static void main(...)
{
   ...    
   //Datei einlesen
   long duration = 0;
   int[] zufallszahlen;
   //Die ersten zehn Knoten im Graphen
   ...
   duration = System.currentTimeMillis();
   for(int i = 0; i < zufallszahlen.length; ++i)
      Queue.insert(zufallszahlen[i]);
   while(!Queue.isEmpty())
      Queue.extractMin();  
   duration = System.currentTimeMillis() - duration;
   ...
}

Laufzeiten - Mittelwert aus fünf kompletten Durchläufen

Da die Ergebnisse der BucketQueues sich nur minimal von denen der normalen Queues unterscheiden, sind hier nur die Ergebnisse für die normalen Queues aufgeführt. Die Ergebnisse für die BucketQueues können dem Archiv entnommen werden.

Heapbasierte Queues

Sonstige Queues

Laufzeiten - Graphik

Zufallszahlen - mit WeakHeapPQ

Zufallszahlen - ohne WeakHeapPQ

Detaillierte Resultate

• Detaillierte Resultate im Archiv: Zufallszahlen-Results.tar.gz

Bemerkungen

Bei dieser Applikation erweisen sich die mäßig komplexen Queues LeftistTreePQ, HeapPQ und RedBlackTreePQ als deutlich am effizientesten. Die auf decreaseKey()-Operationen optimierten Queues schneiden hier relativ schlecht ab, da diese Operation hier nicht gemessen wird und die anderen Operationen eher weniger effektiv implementiert weerden können. Auch die einfachen verlinkten Listen erweisen sich als für große Datensätze ungeeignet. Bei kleinen Datenmengen (bis ca. 2000 Zahlen) sind dagegen alle diese Queues in etwa gleich gut geeignet. Die hohen Werte für den WeakHeap dürften wieder an der nicht optimalen Implementation dieser Datenstruktur liegen.

[Meßbedingungen] - [Durchführung] - [Laufzeiten] - [Graphiken] - [Detaillierte Resultate] - [Bemerkungen]