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 = 100;
  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                 compareNormalInsertion();
  37
  38                 compareContains(10000);
  39
  40                 compareSortedInsertion(seq);
  41
  42                 System.out.println("custom insertion\n  :" + customSortedInsertionTestMulti(seq, TEST_NUMBER));
  43                 System.out.println("custom insertion\n  :" + customSortedInsertionTestMulti(seq, TEST_NUMBER));
  44
  45                 compareRemoval(10000);
  46         }
  47
  48         private static double customSortedInsertionTestMulti(int[] seq, int numtests) {
  49                 long sum = 0;
  50                 for (int i = 0; i < numtests; i++) {
  51                         sum += customSortedInsertion(seq);
  52                 }
  53                 return ((double) sum) / numtests;
  54         }
  55
  56         private static long customSortedInsertion(int[] seq) {
  57                 SortiranaListaBrojeva slb = new SortiranaListaBrojeva();
  58                 long startTime = System.nanoTime();
  59                 for (int i : seq) {
  60                         slb.dodaj(i);
  61                 }
  62                 return System.nanoTime() - startTime;
  63         }
  64
  65         private static void compareSortedInsertion(int[] seq) {
  66                 ArrayList<Integer> al = new ArrayList<>();
  67                 LinkedList<Integer> ll = new LinkedList<>();
  68
  69                 System.out.println("Sorted insertion test");
  70                 System.out.println("ll:" + sortedInsertionTestMulti(ll, seq, TEST_NUMBER));
  71                 System.out.println("al:" + sortedInsertionTestMulti(al, seq, TEST_NUMBER));
  72                 System.out.println("al:" + sortedInsertionTestMulti(al, seq, TEST_NUMBER));
  73                 System.out.println("ll:" + sortedInsertionTestMulti(ll, seq, TEST_NUMBER));
  74         }
  75
  76         private static void compareNormalInsertion() {
  77                 int[] seq = genRandomSequence(10 * SEQ_LENGTH, new Random(123456789));
  78                 ArrayList<Integer> al = new ArrayList<>();
  79                 LinkedList<Integer> ll = new LinkedList<>();
  80                 int nt = TEST_NUMBER;
  81                 System.out.println("Normal insertion test");
  82                 System.out.println("ll:" + insertionTestMulti(ll, seq, nt));
  83                 System.out.println("al:" + insertionTestMulti(al, seq, nt));
  84                 System.out.println("al:" + insertionTestMulti(al, seq, nt));
  85                 System.out.println("ll:" + insertionTestMulti(ll, seq, nt));
  86         }
  87
  88         private static void compareRemoval(int seqLength) {
  89                 int[] seq = genRandomSequence(seqLength, new Random(123456789));
  90                 ArrayList<Integer> al = new ArrayList<>();
  91                 LinkedList<Integer> ll = new LinkedList<>();
  92                 SortiranaListaBrojeva l = new SortiranaListaBrojeva();
  93                 for (int i : seq) {
  94                         al.add(i);
  95                         ll.add(i);
  96                         l.dodaj(i);
  97                 }
  98                 System.out.println("test izbacivanja; duzina:" + seqLength);
  99                 System.out.println("izbacivanje nepostojeceg:");
 100                 double perc = -1.0;
 101                 int testNumber = TEST_NUMBER;
 102                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 103                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 104                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 105                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 106
 107                 perc = 0.1;
 108                 System.out.println("izbacivanje postojeceg na procentu:" + perc);
 109                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 110                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 111                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 112                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 113
 114                 perc = 0.5;
 115                 System.out.println("izbacivanje postojeceg na procentu:" + perc);
 116                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 117                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 118                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 119                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 120
 121                 perc = 0.8;
 122                 System.out.println("izbacivanje postojeceg na procentu:" + perc);
 123                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 124                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 125                 System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
 126                 System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
 127         }
 128
 129         private static double sortedInsertionTestMulti(List<Integer> l, int[] seq, int numtests) {
 130                 long sum = 0;
 131                 for (int i = 0; i < numtests; i++) {
 132                         try {
 133                                 l = l.getClass().newInstance();
 134                         } catch (InstantiationException | IllegalAccessException e) {
 135                                 e.printStackTrace();
 136                         }
 137                         sum += sortedInsertionTest(l, seq);
 138
 139                 }
 140                 return ((double) sum) / numtests;
 141         }
 142
 143         private static long sortedInsertionTest(List<Integer> l, int[] seq) {
 144                 long startTime = System.nanoTime();
 145                 for (int i : seq)
 146                         insertSorted(i, l);
 147                 return System.nanoTime() - startTime;
 148         }
 149
 150         private static void insertSorted(int num, List<Integer> l) {
 151                 int i = 0;
 152                 while (i < l.size() && l.get(i) < num) {
 153                         i++;
 154                 }
 155                 l.add(i, num);
 156         }
 157
 158         private static double insertionTestMulti(List<Integer> l, int[] seq, int testNumber) {
 159                 long sum = 0;
 160                 for (int i = 0; i < testNumber; i++) {
 161                         try {
 162                                 l = l.getClass().newInstance();
 163                         } catch (InstantiationException | IllegalAccessException e) {
 164                                 e.printStackTrace();
 165                         }
 166                         sum += insertionTest(l, seq);
 167
 168                 }
 169                 return ((double) sum) / testNumber;
 170         }
 171
 172         private static long insertionTest(List<Integer> l, int[] seq) {
 173                 long startTime = System.nanoTime();
 174                 for (int i : seq)
 175                         l.add(0, i);
 176                 return System.nanoTime() - startTime;
 177         }
 178
 179         private static double removalTestMulti(List<Integer> l, int num, int testNumber, double percentWhere) {
 180                 long sum = 0;
 181                 for (int i = 0; i < testNumber; i++) {
 182                         if (percentWhere >= 0) {
 183                                 l.add((int) (l.size() * percentWhere), num);
 184                         }
 185                         long startTime = System.nanoTime();
 186                         l.remove((Integer) num);
 187                         sum += System.nanoTime() - startTime;
 188                 }
 189                 return ((double) sum) / testNumber;
 190         }
 191
 192         private static int[] genRandomSequence(int length, Random r) {
 193                 int[] rez = new int[length];
 194                 for (int i = 0; i < length; i++)
 195                         rez[i] = r.nextInt(length);
 196                 return rez;
 197         }
 198
 199         private static void compareContains(int seqLength) {
 200
 201                 int[] seq = genRandomSequence(seqLength, new Random(123456789));
 202                 ArrayList<Integer> al = new ArrayList<>();
 203                 LinkedList<Integer> ll = new LinkedList<>();
 204                 SortiranaListaBrojeva l = new SortiranaListaBrojeva();
 205                 for (int i : seq) {
 206                         al.add(i);
 207                         ll.add(i);
 208                         l.dodaj(i);
 209                 }
 210
 211                 System.out.println("nepostojeci:");
 212                 System.out.println("contains al:" + containsTestMulti(al, seqLength + 1, TEST_NUMBER));
 213                 System.out.println("contains ll:" + containsTestMulti(ll, seqLength + 1, TEST_NUMBER));
 214                 System.out.println("for-rucn al:" + forSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 215                 System.out.println("for-rucn ll:" + forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 216                 System.out.println("for-each al:" + forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 217                 System.out.println("for-each ll:" + forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 218
 219                 System.out.println("custom sort:" + customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER));
 220
 221                 al.set(seqLength / 3, seqLength + 1);
 222                 ll.set(seqLength / 3, seqLength + 1);
 223                 System.out.println("postojeci:");
 224
 225                 System.out.println("contains al:" + containsTestMulti(al, seqLength + 1, TEST_NUMBER));
 226                 System.out.println("contains ll:" + containsTestMulti(ll, seqLength + 1, TEST_NUMBER));
 227                 System.out.println("for-rucn al:" + forSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 228                 System.out.println("for-rucn ll:" + forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 229                 System.out.println("for-each al:" + forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
 230                 System.out.println("for-each ll:" + forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
 231
 232                 System.out.println("custom sort:" + customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER));
 233         }
 234
 235         private static double containsTestMulti(List<Integer> l, int num, int numTests) {
 236                 long res = 0;
 237                 for (int i = 0; i < numTests; i++) {
 238                         long curr = System.nanoTime();
 239                         l.contains(num);
 240                         res += System.nanoTime() - curr;
 241                 }
 242                 return ((double) res) / numTests;
 243         }
 244
 245         private static double forSearchTestMulti(List<Integer> l, int num, int numTests) {
 246                 long res = 0;
 247                 for (int i = 0; i < numTests; i++) {
 248                         long curr = System.nanoTime();
 249
 250                         int j = 0;
 251                         while (j < l.size() && !l.get(j).equals(num))
 252                                 j++;
 253
 254                         res += System.nanoTime() - curr;
 255                 }
 256                 return ((double) res) / numTests;
 257         }
 258
 259         private static double forEachSearchTestMulti(List<Integer> l, int num, int numTests) {
 260                 long res = 0;
 261                 for (int i = 0; i < numTests; i++) {
 262                         long curr = System.nanoTime();
 263
 264                         for (int el : l)
 265                                 if (el == num)
 266                                         break;
 267
 268                         res += System.nanoTime() - curr;
 269                 }
 270                 return ((double) res) / numTests;
 271         }
 272
 273         private static double customContainsSortedTestMulti(SortiranaListaBrojeva l, int num, int numTests) {
 274                 long res = 0;
 275                 for (int i = 0; i < numTests; i++) {
 276                         long curr = System.nanoTime();
 277                         l.uListi(num);
 278                         res += System.nanoTime() - curr;
 279                 }
 280                 return ((double) res) / numTests;
 281         }
 282 }
 283
 284 class SortiranaListaBrojeva {
 285         class Element {
 286                 Integer info;
 287                 Element veza;
 288
 289                 public Element(int s) {
 290                         this.info = s;
 291                         this.veza = null;
 292                 }
 293
 294                 public String toString() {
 295                         return info + "";
 296                 }
 297         }
 298
 299         // pokazivac na prvi element liste
 300         Element prvi;
 301
 302         /** Kreira praznu listu stringova. */
 303         public SortiranaListaBrojeva() {
 304                 this.prvi = null;
 305         }
 306
 307         /** Vraca da li je lista prazna */
 308         public boolean jePrazna() {
 309                 return prvi == null;
 310         }
 311
 312         public String toString() {
 313                 String rez = "Lista: [ ";
 314                 Element tekuci = prvi;
 315                 while (tekuci != null) {
 316                         rez += tekuci.info + " ";
 317                         tekuci = tekuci.veza;
 318                 }
 319                 rez += "]";
 320                 return rez;
 321         }
 322
 323         public void dodaj(int s) {
 324                 if (prvi == null || prvi.info.compareTo(s) > 0) {
 325                         Element novi = new Element(s);
 326                         novi.veza = prvi;
 327                         prvi = novi;
 328                 } else {
 329                         if (!prvi.info.equals(s)) {
 330                                 Element prethodni = prvi;
 331
 332                                 while (prethodni.veza != null && prethodni.veza.info.compareTo(s) < 0) {
 333                                         prethodni = prethodni.veza;
 334                                 }
 335                                 if (prethodni.veza == null || !prethodni.veza.info.equals(s)) {
 336                                         Element novi = new Element(s);
 337                                         novi.veza = prethodni.veza;
 338                                         prethodni.veza = novi;
 339                                 }
 340                         }
 341                 }
 342         }
 343
 344         /** Vraca da li String {@code s} postoji u listi. */
 345         public boolean uListi(int s) {
 346                 Element tekuci = prvi;
 347                 while (tekuci != null && tekuci.info.compareTo(s) < 0) {
 348                         tekuci = tekuci.veza;
 349                 }
 350
 351                 // da li smo trenutno na elementu
 352                 return tekuci != null && tekuci.info.equals(s);
 353         }
 354 }