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 int seq_length = 1000;
  30         private static int test_repeats = 2000;
  31
  32         public static void main(String[] args) {
  33                 System.out.println(
  34                                 "Broj puta koliko će se testovi ponavljati:" + test_repeats);
  35                 System.out.println("* ponegde će biti naznačeno ako je drugačije");
  36                 System.out.println(
  37                                 "Sva vremena su izražena u nanosekundama, dato je prosečno vreme za jednu operaciju");
  38                 System.out.println();
  39                 System.out.println("al - ArrayList");
  40                 System.out.println("ll - LinkedList");
  41                 System.out.println("sl - naša sortirana lista");
  42                 System.out.println();
  43                 // generate random sequence of numbers
  44                 int[] seq = genRandomSequence(seq_length, new Random(123456789));
  45                 int[] seqs = genRandomSequence(seq_length / 10, new Random(123456789));
  46                 // insert into ArrayList and LinkedList
  47                 System.out.println("--- ubacivanje ---");
  48                 compareNormalInsertion();
  49
  50                 System.out.println("--- contains operacija ---");
  51                 compareContains(seq);
  52
  53                 System.out.println("--- sortirano ubacivanje ---");
  54                 System.out.println("broj elemenata:" + (seq_length / 10));
  55                 compareSortedInsertion(seqs);
  56
  57                 System.out.printf("sl:%1$12.2f%n",
  58                                 customSortedInsertionTestMulti(seqs, test_repeats));
  59                 System.out.printf("sl:%1$12.2f%n",
  60                                 customSortedInsertionTestMulti(seqs, test_repeats));
  61                 System.out.println("--- uklanjanja ---");
  62                 compareRemoval(10000);
  63         }
  64
  65         private static int[] genRandomSequence(int length, Random r) {
  66                 int[] rez = new int[length];
  67                 for (int i = 0; i < length; i++)
  68                         rez[i] = r.nextInt(length);
  69                 return rez;
  70         }
  71
  72         private static void compareNormalInsertion() {
  73                 int duz = 10 * seq_length;
  74                 int[] seq = genRandomSequence(duz, new Random(123456789));
  75                 ArrayList<Integer> al = new ArrayList<>();
  76                 LinkedList<Integer> ll = new LinkedList<>();
  77                 int nt = test_repeats / 20;
  78                 System.out.printf("Broj brojeva: %1d; broj testiranja: %2d%n", duz, nt);
  79                 System.out.printf("ll:%1$12.2f%n", insertionTestMulti(ll, seq, nt));
  80                 System.out.printf("al:%1$12.2f%n", insertionTestMulti(al, seq, nt));
  81                 System.out.printf("al:%1$12.2f%n", insertionTestMulti(al, seq, nt));
  82                 System.out.printf("ll:%1$12.2f%n", insertionTestMulti(ll, seq, nt));
  83         }
  84
  85         private static double insertionTestMulti(List<Integer> l, int[] seq,
  86                         int testNumber) {
  87                 long sum = 0;
  88                 for (int i = 0; i < testNumber; i++) {
  89                         try {
  90                                 l = l.getClass().newInstance();
  91                         } catch (InstantiationException | IllegalAccessException e) {
  92                                 e.printStackTrace();
  93                         }
  94                         sum += insertionTest(l, seq);
  95
  96                 }
  97                 return ((double) sum) / testNumber;
  98         }
  99
 100         private static long insertionTest(List<Integer> l, int[] seq) {
 101                 long startTime = System.nanoTime();
 102                 for (int i : seq)
 103                         l.add(0, i);
 104                 return System.nanoTime() - startTime;
 105         }
 106
 107         private static void compareSortedInsertion(int[] seq) {
 108                 ArrayList<Integer> al = new ArrayList<>();
 109                 LinkedList<Integer> ll = new LinkedList<>();
 110
 111                 System.out.println("Sortirano ubacivanje");
 112                 System.out.printf("ll:%1$12.2f%n",
 113                                 sortedInsertionTestMulti(ll, seq, test_repeats));
 114                 System.out.printf("al:%1$12.2f%n",
 115                                 sortedInsertionTestMulti(al, seq, test_repeats));
 116                 System.out.printf("al:%1$12.2f%n",
 117                                 sortedInsertionTestMulti(al, seq, test_repeats));
 118                 System.out.printf("ll:%1$12.2f%n",
 119                                 sortedInsertionTestMulti(ll, seq, test_repeats));
 120         }
 121
 122         private static double sortedInsertionTestMulti(List<Integer> l, int[] seq,
 123                         int numtests) {
 124                 long sum = 0;
 125                 for (int i = 0; i < numtests; i++) {
 126                         try {
 127                                 l = l.getClass().newInstance();
 128                         } catch (InstantiationException | IllegalAccessException e) {
 129                                 e.printStackTrace();
 130                         }
 131                         sum += sortedInsertionTest(l, seq);
 132
 133                 }
 134                 return ((double) sum) / numtests;
 135         }
 136
 137         private static long sortedInsertionTest(List<Integer> l, int[] seq) {
 138                 long startTime = System.nanoTime();
 139                 for (int i : seq)
 140                         insertSorted(i, l);
 141                 return System.nanoTime() - startTime;
 142         }
 143
 144         private static void insertSorted(int num, List<Integer> l) {
 145                 int i = 0;
 146                 while (i < l.size() && l.get(i).compareTo(num) < 0) {
 147                         i++;
 148                 }
 149                 l.add(i, num);
 150         }
 151
 152         private static double customSortedInsertionTestMulti(int[] seq,
 153                         int numtests) {
 154                 long sum = 0;
 155                 for (int i = 0; i < numtests; i++) {
 156                         sum += customSortedInsertion(seq);
 157                 }
 158                 return ((double) sum) / numtests;
 159         }
 160
 161         private static long customSortedInsertion(int[] seq) {
 162                 SortiranaListaBrojeva slb = new SortiranaListaBrojeva();
 163                 long startTime = System.nanoTime();
 164                 for (int i : seq) {
 165                         slb.dodaj(i);
 166                 }
 167                 return System.nanoTime() - startTime;
 168         }
 169
 170         private static void compareRemoval(int seqLength) {
 171                 int[] seq = genRandomSequence(seqLength, new Random(123456789));
 172                 ArrayList<Integer> al = new ArrayList<>();
 173                 LinkedList<Integer> ll = new LinkedList<>();
 174                 SortiranaListaBrojeva l = new SortiranaListaBrojeva();
 175                 for (int i : seq) {
 176                         al.add(i);
 177                         ll.add(i);
 178                         l.dodaj(i);
 179                 }
 180                 System.out.println("test izbacivanja; dužina:" + seqLength);
 181                 System.out.println("izbacivanje nepostojećeg:");
 182                 double perc = -1.0;
 183                 int testNumber = test_repeats;
 184                 System.out.printf("al:%1$12.2f\n",
 185                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 186                 System.out.printf("ll:%1$12.2f\n",
 187                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 188                 System.out.printf("ll:%1$12.2f\n",
 189                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 190                 System.out.printf("al:%1$12.2f\n",
 191                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 192
 193                 perc = 0.1;
 194                 System.out.println("izbacivanje postojećeg na procentu:" + perc);
 195                 System.out.printf("al:%1$12.2f\n",
 196                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 197                 System.out.printf("ll:%1$12.2f\n",
 198                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 199                 System.out.printf("ll:%1$12.2f\n",
 200                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 201                 System.out.printf("al:%1$12.2f\n",
 202                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 203
 204                 perc = 0.5;
 205                 System.out.println("izbacivanje postojećeg na procentu:" + perc);
 206                 System.out.printf("al:%1$12.2f\n",
 207                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 208                 System.out.printf("ll:%1$12.2f\n",
 209                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 210                 System.out.printf("ll:%1$12.2f\n",
 211                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 212                 System.out.printf("al:%1$12.2f\n",
 213                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 214
 215                 perc = 0.8;
 216                 System.out.println("izbacivanje postojećeg na procentu:" + perc);
 217                 System.out.printf("al:%1$12.2f\n",
 218                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 219                 System.out.printf("ll:%1$12.2f\n",
 220                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 221                 System.out.printf("ll:%1$12.2f\n",
 222                                 removalTestMulti(ll, seqLength + 2, testNumber, perc));
 223                 System.out.printf("al:%1$12.2f\n",
 224                                 removalTestMulti(al, seqLength + 2, testNumber, perc));
 225         }
 226
 227         private static double removalTestMulti(List<Integer> l, int num,
 228                         int testNumber, double percentWhere) {
 229                 long sum = 0;
 230                 for (int i = 0; i < testNumber; i++) {
 231                         if (percentWhere >= 0) {
 232                                 l.add((int) (l.size() * percentWhere), num);
 233                         }
 234                         long startTime = System.nanoTime();
 235                         l.remove((Integer) num);
 236                         sum += System.nanoTime() - startTime;
 237                 }
 238                 return ((double) sum) / testNumber;
 239         }
 240
 241         private static void compareContains(int[] seq) {
 242                 int seqLength = seq.length;
 243                 System.out.println("Broj brojeva:" + seqLength);
 244                 ArrayList<Integer> al = new ArrayList<>();
 245                 LinkedList<Integer> ll = new LinkedList<>();
 246                 SortiranaListaBrojeva l = new SortiranaListaBrojeva();
 247                 for (int i : seq) {
 248                         al.add(i);
 249                         ll.add(i);
 250                         l.dodaj(i);
 251                 }
 252
 253                 System.out.println("- nepostojeći (-1):");
 254                 System.out.printf("contains al:%1$12.2f%n",
 255                                 containsTestMulti(al, -1, test_repeats));
 256                 System.out.printf("contains ll:%1$12.2f%n",
 257                                 containsTestMulti(ll, -1, test_repeats));
 258                 System.out.printf("petlja   al:%1$12.2f%n",
 259                                 loopSearchTestMulti(al, -1, test_repeats));
 260                 System.out.printf("petlja   ll:%1$12.2f%n",
 261                                 loopSearchTestMulti(ll, -1, test_repeats));
 262                 System.out.printf("for-each al:%1$12.2f%n",
 263                                 forEachSearchTestMulti(al, -1, test_repeats));
 264                 System.out.printf("for-each ll:%1$12.2f%n",
 265                                 forEachSearchTestMulti(ll, -1, test_repeats));
 266
 267                 System.out.printf("sl uListi  :%1$12.2f%n",
 268                                 customContainsSortedTestMulti(l, -1, test_repeats));
 269
 270                 al.set(seqLength / 3, seqLength + 1);
 271                 ll.set(seqLength / 3, seqLength + 1);
 272                 // ovaj moramo uzeti jer je sortirano
 273                 int el3 = l.element(seqLength / 3);
 274                 System.out.println("- postojeći (na trećini dužine):");
 275
 276                 System.out.printf("contains al:%1$12.2f%n",
 277                                 containsTestMulti(al, seqLength + 1, test_repeats));
 278                 System.out.printf("contains ll:%1$12.2f%n",
 279                                 containsTestMulti(ll, seqLength + 1, test_repeats));
 280                 System.out.printf("for-ručn al:%1$12.2f%n",
 281                                 loopSearchTestMulti(al, seqLength + 1, test_repeats));
 282                 System.out.printf("for-ručn ll:%1$12.2f%n",
 283                                 loopSearchTestMulti(ll, seqLength + 1, test_repeats));
 284                 System.out.printf("for-each al:%1$12.2f%n",
 285                                 forEachSearchTestMulti(al, seqLength + 1, test_repeats));
 286                 System.out.printf("for-each ll:%1$12.2f%n",
 287                                 forEachSearchTestMulti(ll, seqLength + 1, test_repeats));
 288
 289                 System.out.printf("sl uListi  :%1$12.2f%n",
 290                                 customContainsSortedTestMulti(l, el3, test_repeats));
 291         }
 292
 293         private static double containsTestMulti(List<Integer> l, int num,
 294                         int numTests) {
 295                 long res = 0;
 296                 for (int i = 0; i < numTests; i++) {
 297                         long curr = System.nanoTime();
 298                         l.contains(num);
 299                         res += System.nanoTime() - curr;
 300                 }
 301                 return ((double) res) / numTests;
 302         }
 303
 304         private static double loopSearchTestMulti(List<Integer> l, int num,
 305                         int numTests) {
 306                 long res = 0;
 307                 for (int i = 0; i < numTests; i++) {
 308                         long curr = System.nanoTime();
 309
 310                         int j = 0;
 311                         int size = l.size();
 312                         while (j < size && !l.get(j).equals(num))
 313                                 j++;
 314
 315                         res += System.nanoTime() - curr;
 316                 }
 317                 return ((double) res) / numTests;
 318         }
 319
 320         private static double forEachSearchTestMulti(List<Integer> l, int num,
 321                         int numTests) {
 322                 long res = 0;
 323                 for (int i = 0; i < numTests; i++) {
 324                         long curr = System.nanoTime();
 325
 326                         for (Integer el : l)
 327                                 if (el.equals(num))
 328                                         break;
 329
 330                         res += System.nanoTime() - curr;
 331                 }
 332                 return ((double) res) / numTests;
 333         }
 334
 335         private static double customContainsSortedTestMulti(SortiranaListaBrojeva l,
 336                         int num, int numTests) {
 337                 long res = 0;
 338                 for (int i = 0; i < numTests; i++) {
 339                         long curr = System.nanoTime();
 340                         l.uListi(num);
 341                         res += System.nanoTime() - curr;
 342                 }
 343                 return ((double) res) / numTests;
 344         }
 345 }
 346
 347 class SortiranaListaBrojeva {
 348         class Element {
 349                 Integer info;
 350                 Element veza;
 351
 352                 public Element(int s) {
 353                         this.info = s;
 354                         this.veza = null;
 355                 }
 356
 357                 public String toString() {
 358                         return info + "";
 359                 }
 360         }
 361
 362         // pokazivac na prvi element liste
 363         Element prvi;
 364
 365         /** Kreira praznu listu stringova. */
 366         public SortiranaListaBrojeva() {
 367                 this.prvi = null;
 368         }
 369
 370         /** Vraca da li je lista prazna */
 371         public boolean jePrazna() {
 372                 return prvi == null;
 373         }
 374
 375         public String toString() {
 376                 String rez = "Lista: [ ";
 377                 Element tekuci = prvi;
 378                 while (tekuci != null) {
 379                         rez += tekuci.info + " ";
 380                         tekuci = tekuci.veza;
 381                 }
 382                 rez += "]";
 383                 return rez;
 384         }
 385
 386         public void dodaj(int s) {
 387                 if (prvi == null || prvi.info.compareTo(s) > 0) {
 388                         Element novi = new Element(s);
 389                         novi.veza = prvi;
 390                         prvi = novi;
 391                 } else {
 392                         if (!prvi.info.equals(s)) {
 393                                 Element prethodni = prvi;
 394
 395                                 while (prethodni.veza != null
 396                                                 && prethodni.veza.info.compareTo(s) < 0) {
 397                                         prethodni = prethodni.veza;
 398                                 }
 399                                 Element novi = new Element(s);
 400                                 novi.veza = prethodni.veza;
 401                                 prethodni.veza = novi;
 402                         }
 403                 }
 404         }
 405
 406         public int element(int k) {
 407                 if (k < 0) {
 408                         throw new IndexOutOfBoundsException(
 409                                         "Ne postoje elementi na negativnim pozicijama!");
 410                 }
 411
 412                 Element tekuci = prvi;
 413                 int brojac = 0;
 414
 415                 while (tekuci != null && k > brojac) {
 416                         tekuci = tekuci.veza;
 417                         brojac++;
 418                 }
 419
 420                 if (tekuci != null) {
 421                         return tekuci.info;
 422                 } else {
 423                         throw new IndexOutOfBoundsException("Lista je kraca od " + k);
 424                 }
 425         }
 426
 427         /** Vraca da li String {@code s} postoji u listi. */
 428         public boolean uListi(int s) {
 429                 Element tekuci = prvi;
 430                 while (tekuci != null && tekuci.info.compareTo(s) < 0) {
 431                         tekuci = tekuci.veza;
 432                 }
 433
 434                 // da li smo trenutno na elementu
 435                 return tekuci != null && tekuci.info.equals(s);
 436         }
 437 }