homedukeAlgorithmen & Datenstrukturen mit Java: Tests mit zufälligem und sortiertem Einfügen Prof. Dr. Uwe Schmidt FH Wedel

Tests mit zufälligem und sortiertem Einfügen

weiter

weiter

Testprogramm
mit Zufallswerten und auf- und absteigend sortierten Werten für persistent Implementierung
weiter
   1package tests.persistent.queue;
   2
   3import ds.interfaces.PriorityQueue;
   4
   5import java.util.Random;
   6
   7import ds.persistent.queue.BinaryHeap;
   8import ds.util.PV;
   9import ds.util.P;
  10
  11import static ds.util.P.mkP;
  12import static ds.util.V.mkV;
  13import static ds.util.PV.mkPair;
  14
  15import tests.util.Args;
  16
  17public class BinaryHeapTrace {
  18
  19    public static void main(String [] args) {
  20        int noOfElems = Args.getInt(args, 0, 1023);
  21
  22        (new Main(noOfElems)).run();
  23    }
  24
  25    private static
  26        class Main
  27        extends tests.util.Main {
  28        final int n;
  29        final Random r;
  30
  31        BinaryHeap h;
  32
  33        Main(int n1) {
  34            n = n1;
  35            r = new Random();
  36            h = BinaryHeap.empty();
  37        }
  38
  39        void buildHeapRandom() {
  40            startTime("building binary heap tree by inserting " +
  41                      n +
  42                      " random elements)");
  43            for (int i = 0; i < n++i) {
  44                int p = r.nextInt();
  45                if ( n <= 100 )
  46                    msg("insert " + p + ", " + i);
  47                h = h.insert(mkP(p)mkV(i));
  48            }
  49            stopTime();
  50        }
  51
  52        void buildHeapAscending() {
  53            startTime("building binary heap tree by inserting " +
  54                      n +
  55                      " ascending elements");
  56            for (int i = 0; i < n++i) {
  57                int p = i;
  58                if ( n <= 100 )
  59                    msg("insert " + p + ", " + i);
  60                h = h.insert(mkP(p)mkV(i));
  61            }
  62            stopTime();
  63        }
  64
  65        void buildHeapDescending() {
  66            startTime("building binary heap tree by inserting " +
  67                      n +
  68                      " descending elements");
  69            for (int i = 0; i < n++i) {
  70                int p = n - i - 1;
  71                if ( n <= 100 )
  72                    msg("insert " + p + ", " + i);
  73                h = h.insert(mkP(p)mkV(i));
  74            }
  75            stopTime();
  76        }
  77
  78        void buildHeapConst() {
  79            startTime("building binary heap tree by inserting " +
  80                      n +
  81                      " times the same element");
  82            for (int i = 0; i < n++i) {
  83                int p = 0;
  84                if ( n <= 100 )
  85                    msg("insert " + p + ", " + i);
  86                h = h.insert(mkP(p)mkV(i));
  87            }
  88            stopTime();
  89        }
  90
  91        void deleteHeap() {
  92            startTime("deleting a binary heap tree by removing " +
  93                      n +
  94                      " elements in ascending order");
  95            for (int i = 0; i < n++i) {
  96                PV pv = h.findMin();
  97                if ( n <= 100 )
  98                    msg("remove " + pv.fst.prio + ", " + pv.snd.value);
  99                h = h.removeMin();
 100            }
 101            msg("binary heap: h.isEmpty() == " + h.isEmpty());
 102            stopTime();
 103        }
 104
 105        void stats() {
 106            msg("h.size()          = " + h.size());
 107            msg("h.depth()         = " + h.depth());
 108            msg("h.minDepth()      = " + h.minDepth());
 109            msg("h.inv()           = " + h.inv());
 110            msg("");
 111        }
 112
 113        void memStats() {
 114            msg(h.objStats());
 115        }
 116
 117        void classStats() {
 118            msg(BinaryHeap.stats());
 119        }
 120
 121        public void run() {
 122            nl();
 123            buildHeapRandom();
 124            stats();
 125            memStats();
 126            classStats();
 127            deleteHeap();
 128            stats();
 129            classStats();
 130
 131            buildHeapAscending();
 132            stats();
 133            memStats();
 134            classStats();
 135            deleteHeap();
 136            stats();
 137            classStats();
 138
 139            buildHeapDescending();
 140            stats();
 141            memStats();
 142            classStats();
 143            deleteHeap();
 144            stats();
 145            classStats();
 146
 147            buildHeapConst();
 148            stats();
 149            memStats();
 150            classStats();
 151            deleteHeap();
 152            stats();
 153            classStats();
 154        }
 155    }
 156}
weiter
Testläufe
für persistent Implementierung
 
 
weiter
Testläufe
für destruktive Implementierung
 
weiter
Quellen
weiter

Letzte Änderung: 10.12.2015
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel