kodovi/kolekcije/ListCompare.java

   1 import java.util.ArrayList;
   2 import java.util.Arrays;
   3 import java.util.LinkedList;
   4 import java.util.List;
   5 import java.util.Random;
   6
   7 /**
   8  * Primeri razlicitih operacija na klasama ArrayList i LinkedList i poredjenje
   9  * performansi nad istim podacima.
  10  *
  11  * U nekim primerima se koriste i sopstvene implementacije klasa za poredjenje
  12  * sa ugradjenima.
  13  *
  14  * NAPOMENA: merenje vremena izvrsavanja u opstem slucaju nije najpouzdanije,
  15  * posto racunar skoro nikad ne izvrsava samo taj jedan program.
  16  *
  17  * Druga bitna stvar je da je Java virtuelna masina napravljena tako da
  18  * optimizuje samu sebe u skladu sa kodom koji se izvrsava. Zbog toga postoji i
  19  * pojam "hladne masine" koja jos nije stigla da se optimizuje uopste. Ali ovaj
  20  * proces se stalno desava, tako da ako se dugo radi slican kod, a potom promeni
  21  * na nesto drugo to drugo ce inicijalno biti sporije dok se ne re-optimizuje.
  22  *
  23  * Bez obzira na sve te napomene, ovi testovi bi trebalo da relativno jasno
  24  * prikazu odnose brzina koristeci ponavljanje testova veliki broj puta i
  25  * primenjujuci ih razlicitim redosledom na strukture.
  26  */
  27 public class ListCompare {
  28
  29         private static final int SEQ_LENGTH = 500;
  30         private static final int TEST_NUMBER = 100;
  31
  32         public static void main(String[] args) {
  33                 // generate random sequence of numbers
  34                 int[] seq = genRandomSequence(SEQ_LENGTH, new Random(123456789));
  35                 // insert into ArrayList and LinkedList
  36                 System.out.println("--- ubacivanje ---");
  37                 compareNormalInsertion();
  38
  39                 System.out.println("--- contains operacija ---");
  40                 compareContains(1000);
  41
  42                 System.out.println("--- sortirano ubacivanje ---");
  43                 compareSortedInsertion(seq);
  44
  45                 System.out.printf("custom insertion%n  :%1$10.2f%n", customSortedInsertionTestMulti(seq, TEST_NUMBER));
  46                 System.out.printf("custom insertion%n  :%1$10.2f%n", customSortedInsertionTestMulti(seq, TEST_NUMBER));
  47
  48                 System.out.println("--- uklanjanja ---");
  49                 compareRemoval(10000);
  50         }
  51
  52         private static int[] genRandomSequence(int length, Random r) {
  53                 int[] rez = new int[length];
  54                 for (int i = 0; i < length; i++)
  55                         rez[i] = r.nextInt(length);
  56                 return rez;
  57         }
  58
  59         private static void compareNormalInsertion() {
  60                 int[] seq = genRandomSequence(10 * SEQ_LENGTH, new Random(123456789));
  61                 ArrayList<Integer> al = new ArrayList<>();
  62                 LinkedList<Integer> ll = new LinkedList<>();
  63                 int nt = TEST_NUMBER;
  64                 System.out.println("Normal insertion test");
  65                 System.out.printf("ll:%1$10.2f%n", insertionTestMulti(ll, seq, nt));
  66                 System.out.printf("al:%1$10.2f%n", insertionTestMulti(al, seq, nt));
  67                 System.out.printf("al:%1$10.2f%n", insertionTestMulti(al, seq, nt));
  68                 System.out.printf("ll:%1$10.2f%n", insertionTestMulti(ll, seq, nt));
  69         }
  70
  71         private static double insertionTestMulti(List<Integer> l, int[] seq, int testNumber) {
  72                 long sum = 0;
  73                 for (int i = 0; i < testNumber; i++) {
  74                         try {
  75                                 l = l.getClass().newInstance();
  76                         } catch (InstantiationException | IllegalAccessException e) {
  77                                 e.printStackTrace();
  78                         }
  79                         sum += insertionTest(l, seq);
  80
  81                 }
  82                 return ((double) sum) / testNumber;
  83         }
  84
  85         private static long insertionTest(List<Integer> l, int[] seq) {
  86                 long startTime = System.nanoTime();
  87                 for (int i : seq)
  88                         l.add(0, i);
  89                 return System.nanoTime() - startTime;
  90         }
  91
  92         private static void compareSortedInsertion(int[] seq) {
  93                 ArrayList<Integer> al = new ArrayList<>();
  94                 LinkedList<Integer> ll = new LinkedList<>();
  95
  96                 System.out.println("Sorted insertion test");
  97                 System.out.printf("ll:%1$10.2f%n", sortedInsertionTestMulti(ll, seq, TEST_NUMBER));
  98                 System.out.printf("al:%1$10.2f%n", sortedInsertionTestMulti(al, seq, TEST_NUMBER));
  99                 System.out.printf("al:%1$10.2f%n", sortedInsertionTestMulti(al, seq, TEST_NUMBER));
 100                 System.out.printf("ll:%1$10.2f%n", sortedInsertionTestMulti(ll, seq, TEST_NUMBER));
 101         }
 102
 103         private static double sortedInsertionTestMulti(List<Integer> l, int[] seq, int numtests) {
 104                 long sum = 0;
 105                 for (int i = 0; i < numtests; i++) {
 106                         try {
 107                                 l = l.getClass().newInstance();
 108                         } catch (InstantiationException | IllegalAccessException e) {
 109                                 e.printStackTrace();
 110                         }
 111                         sum += sortedInsertionTest(l, seq);
 112
 113                 }
 114                 return ((double) sum) / numtests;
 115         }
 116
 117         private static long sortedInsertionTest(List<Integer> l, int[] seq) {
 118                 long startTime = System.nanoTime();
 119                 for (int i : seq)
 120                         insertSorted(i, l);
 121                 return System.nanoTime() - startTime;
 122         }
 123
 124         private static void insertSorted(int num, List<Integer> l) {
 125                 int i = 0;
 126                 while (i < l.size() && l.get(i) < num) {
 127                         i++;
 128                 }
 129                 l.add(i, num);
 130         }
 131
 132         private static double customSortedInsertionTestMulti(int[] seq, int numtests) {
 133                 long sum = 0;
 134                 for (int i = 0; i < numtests; i++) {
 135                         sum += customSortedInsertion(seq);
 136                 }
 137                 return ((double) sum) / numtests;
 138         }
 139
 140         private static long customSortedInsertion(int[] seq) {
 141                 SortiranaListaBrojeva slb = new SortiranaListaBrojeva();
 142                 long startTime = System.nanoTime();
 143                 for (int i : seq) {
 144                         slb.dodaj(i);
 145                 }
 146                 return System.nanoTime() - startTime;
 147         }
 148
 149         private static void compareRemoval(int seqLength) {
 150                 int[] seq = genRandomSequence(seqLength, new Random(123456789));
 151                 ArrayList<Integer> al = new ArrayList<>();
 152                 LinkedList<Integer> ll = new LinkedList<>();
 153                 SortiranaListaBrojeva l = new SortiranaListaBrojeva();
 154                 for (int i : seq) {
 155                         al.add(i);
 156                         ll.add(i);
 157                         l.dodaj(i);
 158                 }
 159                 System.out.println("test izbacivanja; duzina:" + seqLength);
 160                 System.out.println("izbacivanje nepostojeceg:");
 161                 double perc = -1.0;
 162                 int testNumber = TEST_NUMBER;
 163                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 164                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 165                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 166                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 167
 168                 perc = 0.1;
 169                 System.out.println("izbacivanje postojeceg na procentu:" + perc);
 170                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 171                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 172                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 173                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 174
 175                 perc = 0.5;
 176                 System.out.println("izbacivanje postojeceg na procentu:" + perc);
 177                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 178                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 179                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 180                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 181
 182                 perc = 0.8;
 183                 System.out.println("izbacivanje postojeceg na procentu:" + perc);
 184                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 185                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 186                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 187                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 188         }
 189
 190         private static double removalTestMulti(List<Integer> l, int num, int testNumber, double percentWhere) {
 191                 long sum = 0;
 192                 for (int i = 0; i < testNumber; i++) {
 193                         if (percentWhere >= 0) {
 194                                 l.add((int) (l.size() * percentWhere), num);
 195                         }
 196                         long startTime = System.nanoTime();
 197                         l.remove((Integer) num);
 198                         sum += System.nanoTime() - startTime;
 199                 }
 200                 return ((double) sum) / testNumber;
 201         }
 202
 203         private static void compareContains(int seqLength) {
 204
 205                 int[] seq = genRandomSequence(seqLength, new Random(123456789));
 206                 ArrayList<Integer> al = new ArrayList<>();
 207                 LinkedList<Integer> ll = new LinkedList<>();
 208                 SortiranaListaBrojeva l = new SortiranaListaBrojeva();
 209                 for (int i : seq) {
 210                         al.add(i);
 211                         ll.add(i);
 212                         l.dodaj(i);
 213                 }
 214
 215                 System.out.println("nepostojeci:");
 216                 System.out.printf("contains al:%1$10.2f%n" , containsTestMulti(al, seqLength + 1, TEST_NUMBER));
 217                 System.out.printf("contains ll:%1$10.2f%n" , containsTestMulti(ll, seqLength + 1, TEST_NUMBER));
 218                 System.out.printf("for-rucn al:%1$10.2f%n" , forSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 219                 System.out.printf("for-rucn ll:%1$10.2f%n" , forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 220                 System.out.printf("for-each al:%1$10.2f%n" , forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 221                 System.out.printf("for-each ll:%1$10.2f%n" , forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 222
 223                 System.out.printf("custom sort:%1$10.2f%n" , customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER));
 224
 225                 al.set(seqLength / 3, seqLength + 1);
 226                 ll.set(seqLength / 3, seqLength + 1);
 227                 // ovaj moramo uzeti jer je sortirano
 228                 int el3 = l.element(seqLength / 3);
 229                 System.out.println("postojeci:");
 230
 231                 System.out.printf("contains al:%1$10.2f%n" , containsTestMulti(al, seqLength + 1, TEST_NUMBER));
 232                 System.out.printf("contains ll:%1$10.2f%n" , containsTestMulti(ll, seqLength + 1, TEST_NUMBER));
 233                 System.out.printf("for-rucn al:%1$10.2f%n" , forSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 234                 System.out.printf("for-rucn ll:%1$10.2f%n" , forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 235                 System.out.printf("for-each al:%1$10.2f%n" , forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 236                 System.out.printf("for-each ll:%1$10.2f%n" , forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 237
 238                 System.out.printf("custom sort:%1$10.2f%n" , customContainsSortedTestMulti(l, el3, TEST_NUMBER));
 239         }
 240
 241         private static double containsTestMulti(List<Integer> l, int num, int numTests) {
 242                 long res = 0;
 243                 for (int i = 0; i < numTests; i++) {
 244                         long curr = System.nanoTime();
 245                         l.contains(num);
 246                         res += System.nanoTime() - curr;
 247                 }
 248                 return ((double) res) / numTests;
 249         }
 250
 251         private static double forSearchTestMulti(List<Integer> l, int num, int numTests) {
 252                 long res = 0;
 253                 for (int i = 0; i < numTests; i++) {
 254                         long curr = System.nanoTime();
 255
 256                         int j = 0;
 257                         while (j < l.size() && !l.get(j).equals(num))
 258                                 j++;
 259
 260                         res += System.nanoTime() - curr;
 261                 }
 262                 return ((double) res) / numTests;
 263         }
 264
 265         private static double forEachSearchTestMulti(List<Integer> l, int num, int numTests) {
 266                 long res = 0;
 267                 for (int i = 0; i < numTests; i++) {
 268                         long curr = System.nanoTime();
 269
 270                         for (int el : l)
 271                                 if (el == num)
 272                                         break;
 273
 274                         res += System.nanoTime() - curr;
 275                 }
 276                 return ((double) res) / numTests;
 277         }
 278
 279         private static double customContainsSortedTestMulti(SortiranaListaBrojeva l, int num, int numTests) {
 280                 long res = 0;
 281                 for (int i = 0; i < numTests; i++) {
 282                         long curr = System.nanoTime();
 283                         l.uListi(num);
 284                         res += System.nanoTime() - curr;
 285                 }
 286                 return ((double) res) / numTests;
 287         }
 288 }
 289
 290 class SortiranaListaBrojeva {
 291         class Element {
 292                 Integer info;
 293                 Element veza;
 294
 295                 public Element(int s) {
 296                         this.info = s;
 297                         this.veza = null;
 298                 }
 299
 300                 public String toString() {
 301                         return info + "";
 302                 }
 303         }
 304
 305         // pokazivac na prvi element liste
 306         Element prvi;
 307
 308         /** Kreira praznu listu stringova. */
 309         public SortiranaListaBrojeva() {
 310                 this.prvi = null;
 311         }
 312
 313         /** Vraca da li je lista prazna */
 314         public boolean jePrazna() {
 315                 return prvi == null;
 316         }
 317
 318         public String toString() {
 319                 String rez = "Lista: [ ";
 320                 Element tekuci = prvi;
 321                 while (tekuci != null) {
 322                         rez += tekuci.info + " ";
 323                         tekuci = tekuci.veza;
 324                 }
 325                 rez += "]";
 326                 return rez;
 327         }
 328
 329         public void dodaj(int s) {
 330                 if (prvi == null || prvi.info.compareTo(s) > 0) {
 331                         Element novi = new Element(s);
 332                         novi.veza = prvi;
 333                         prvi = novi;
 334                 } else {
 335                         if (!prvi.info.equals(s)) {
 336                                 Element prethodni = prvi;
 337
 338                                 while (prethodni.veza != null && prethodni.veza.info.compareTo(s) < 0) {
 339                                         prethodni = prethodni.veza;
 340                                 }
 341                                 Element novi = new Element(s);
 342                                 novi.veza = prethodni.veza;
 343                                 prethodni.veza = novi;
 344                         }
 345                 }
 346         }
 347
 348         public int element(int k) {
 349                 if (k < 0) {
 350                         throw new IndexOutOfBoundsException(
 351                                         "Ne postoje elementi na negativnim pozicijama!");
 352                 }
 353
 354                 Element tekuci = prvi;
 355                 int brojac = 0;
 356
 357                 while (tekuci != null && k > brojac) {
 358                         tekuci = tekuci.veza;
 359                         brojac++;
 360                 }
 361
 362                 if (tekuci != null) {
 363                         return tekuci.info;
 364                 } else {
 365                         throw new IndexOutOfBoundsException("Lista je kraca od "
 366                                         + k);
 367                 }
 368         }
 369
 370         /** Vraca da li String {@code s} postoji u listi. */
 371         public boolean uListi(int s) {
 372                 Element tekuci = prvi;
 373                 while (tekuci != null && tekuci.info.compareTo(s) < 0) {
 374                         tekuci = tekuci.veza;
 375                 }
 376
 377                 // da li smo trenutno na elementu
 378                 return tekuci != null && tekuci.info.equals(s);
 379         }
 380 }