Ugradjene kolekcije, primeri upotrebe i poredjenje performansi

diff --git a/kodovi/kolekcije/ListCompare.java b/kodovi/kolekcije/ListCompare.java
new file mode 100644 (file)
index 0000000..8a04c04
--- /dev/null
+++ b/kodovi/kolekcije/ListCompare.java
@@ -0,0 +1,354 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+/**
+ * Primeri razlicitih operacija na klasama ArrayList i LinkedList i poredjenje
+ * performansi nad istim podacima.
+ * 
+ * U nekim primerima se koriste i sopstvene implementacije klasa za poredjenje
+ * sa ugradjenima.
+ * 
+ * NAPOMENA: merenje vremena izvrsavanja u opstem slucaju nije najpouzdanije,
+ * posto racunar skoro nikad ne izvrsava samo taj jedan program.
+ * 
+ * Druga bitna stvar je da je Java virtuelna masina napravljena tako da
+ * optimizuje samu sebe u skladu sa kodom koji se izvrsava. Zbog toga postoji i
+ * pojam "hladne masine" koja jos nije stigla da se optimizuje uopste. Ali ovaj
+ * proces se stalno desava, tako da ako se dugo radi slican kod, a potom promeni
+ * na nesto drugo to drugo ce inicijalno biti sporije dok se ne re-optimizuje.
+ * 
+ * Bez obzira na sve te napomene, ovi testovi bi trebalo da relativno jasno
+ * prikazu odnose brzina koristeci ponavljanje testova veliki broj puta i
+ * primenjujuci ih razlicitim redosledom na strukture.
+ */
+public class ListCompare {
+
+       private static final int SEQ_LENGTH = 100;
+       private static final int TEST_NUMBER = 100;
+
+       public static void main(String[] args) {
+               // generate random sequence of numbers
+               int[] seq = genRandomSequence(SEQ_LENGTH, new Random(123456789));
+               // insert into ArrayList and LinkedList
+               compareNormalInsertion();
+
+               compareContains(10000);
+
+               compareSortedInsertion(seq);
+
+               System.out.println("custom insertion\n  :" + customSortedInsertionTestMulti(seq, TEST_NUMBER));
+               System.out.println("custom insertion\n  :" + customSortedInsertionTestMulti(seq, TEST_NUMBER));
+
+               compareRemoval(10000);
+       }
+
+       private static double customSortedInsertionTestMulti(int[] seq, int numtests) {
+               long sum = 0;
+               for (int i = 0; i < numtests; i++) {
+                       sum += customSortedInsertion(seq);
+               }
+               return ((double) sum) / numtests;
+       }
+
+       private static long customSortedInsertion(int[] seq) {
+               SortiranaListaBrojeva slb = new SortiranaListaBrojeva();
+               long startTime = System.nanoTime();
+               for (int i : seq) {
+                       slb.dodaj(i);
+               }
+               return System.nanoTime() - startTime;
+       }
+
+       private static void compareSortedInsertion(int[] seq) {
+               ArrayList<Integer> al = new ArrayList<>();
+               LinkedList<Integer> ll = new LinkedList<>();
+
+               System.out.println("Sorted insertion test");
+               System.out.println("ll:" + sortedInsertionTestMulti(ll, seq, TEST_NUMBER));
+               System.out.println("al:" + sortedInsertionTestMulti(al, seq, TEST_NUMBER));
+               System.out.println("al:" + sortedInsertionTestMulti(al, seq, TEST_NUMBER));
+               System.out.println("ll:" + sortedInsertionTestMulti(ll, seq, TEST_NUMBER));
+       }
+
+       private static void compareNormalInsertion() {
+               int[] seq = genRandomSequence(10 * SEQ_LENGTH, new Random(123456789));
+               ArrayList<Integer> al = new ArrayList<>();
+               LinkedList<Integer> ll = new LinkedList<>();
+               int nt = TEST_NUMBER;
+               System.out.println("Normal insertion test");
+               System.out.println("ll:" + insertionTestMulti(ll, seq, nt));
+               System.out.println("al:" + insertionTestMulti(al, seq, nt));
+               System.out.println("al:" + insertionTestMulti(al, seq, nt));
+               System.out.println("ll:" + insertionTestMulti(ll, seq, nt));
+       }
+
+       private static void compareRemoval(int seqLength) {
+               int[] seq = genRandomSequence(seqLength, new Random(123456789));
+               ArrayList<Integer> al = new ArrayList<>();
+               LinkedList<Integer> ll = new LinkedList<>();
+               SortiranaListaBrojeva l = new SortiranaListaBrojeva();
+               for (int i : seq) {
+                       al.add(i);
+                       ll.add(i);
+                       l.dodaj(i);
+               }
+               System.out.println("test izbacivanja; duzina:" + seqLength);
+               System.out.println("izbacivanje nepostojeceg:");
+               double perc = -1.0;
+               int testNumber = TEST_NUMBER;
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+
+               perc = 0.1;
+               System.out.println("izbacivanje postojeceg na procentu:" + perc);
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+
+               perc = 0.5;
+               System.out.println("izbacivanje postojeceg na procentu:" + perc);
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+
+               perc = 0.8;
+               System.out.println("izbacivanje postojeceg na procentu:" + perc);
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("ll:%1$10.2f\n", removalTestMulti(ll, seqLength + 2, testNumber, perc));
+               System.out.printf("al:%1$10.2f\n", removalTestMulti(al, seqLength + 2, testNumber, perc));
+       }
+
+       private static double sortedInsertionTestMulti(List<Integer> l, int[] seq, int numtests) {
+               long sum = 0;
+               for (int i = 0; i < numtests; i++) {
+                       try {
+                               l = l.getClass().newInstance();
+                       } catch (InstantiationException | IllegalAccessException e) {
+                               e.printStackTrace();
+                       }
+                       sum += sortedInsertionTest(l, seq);
+
+               }
+               return ((double) sum) / numtests;
+       }
+
+       private static long sortedInsertionTest(List<Integer> l, int[] seq) {
+               long startTime = System.nanoTime();
+               for (int i : seq)
+                       insertSorted(i, l);
+               return System.nanoTime() - startTime;
+       }
+
+       private static void insertSorted(int num, List<Integer> l) {
+               int i = 0;
+               while (i < l.size() && l.get(i) < num) {
+                       i++;
+               }
+               l.add(i, num);
+       }
+
+       private static double insertionTestMulti(List<Integer> l, int[] seq, int testNumber) {
+               long sum = 0;
+               for (int i = 0; i < testNumber; i++) {
+                       try {
+                               l = l.getClass().newInstance();
+                       } catch (InstantiationException | IllegalAccessException e) {
+                               e.printStackTrace();
+                       }
+                       sum += insertionTest(l, seq);
+
+               }
+               return ((double) sum) / testNumber;
+       }
+
+       private static long insertionTest(List<Integer> l, int[] seq) {
+               long startTime = System.nanoTime();
+               for (int i : seq)
+                       l.add(0, i);
+               return System.nanoTime() - startTime;
+       }
+
+       private static double removalTestMulti(List<Integer> l, int num, int testNumber, double percentWhere) {
+               long sum = 0;
+               for (int i = 0; i < testNumber; i++) {
+                       if (percentWhere >= 0) {
+                               l.add((int) (l.size() * percentWhere), num);
+                       }
+                       long startTime = System.nanoTime();
+                       l.remove((Integer) num);
+                       sum += System.nanoTime() - startTime;
+               }
+               return ((double) sum) / testNumber;
+       }
+
+       private static int[] genRandomSequence(int length, Random r) {
+               int[] rez = new int[length];
+               for (int i = 0; i < length; i++)
+                       rez[i] = r.nextInt(length);
+               return rez;
+       }
+
+       private static void compareContains(int seqLength) {
+
+               int[] seq = genRandomSequence(seqLength, new Random(123456789));
+               ArrayList<Integer> al = new ArrayList<>();
+               LinkedList<Integer> ll = new LinkedList<>();
+               SortiranaListaBrojeva l = new SortiranaListaBrojeva();
+               for (int i : seq) {
+                       al.add(i);
+                       ll.add(i);
+                       l.dodaj(i);
+               }
+
+               System.out.println("nepostojeci:");
+               System.out.println("contains al:" + containsTestMulti(al, seqLength + 1, TEST_NUMBER));
+               System.out.println("contains ll:" + containsTestMulti(ll, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-rucn al:" + forSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-rucn ll:" + forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-each al:" + forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-each ll:" + forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
+
+               System.out.println("custom sort:" + customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER));
+
+               al.set(seqLength / 3, seqLength + 1);
+               ll.set(seqLength / 3, seqLength + 1);
+               System.out.println("postojeci:");
+
+               System.out.println("contains al:" + containsTestMulti(al, seqLength + 1, TEST_NUMBER));
+               System.out.println("contains ll:" + containsTestMulti(ll, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-rucn al:" + forSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-rucn ll:" + forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-each al:" + forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER));
+               System.out.println("for-each ll:" + forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER));
+
+               System.out.println("custom sort:" + customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER));
+       }
+
+       private static double containsTestMulti(List<Integer> l, int num, int numTests) {
+               long res = 0;
+               for (int i = 0; i < numTests; i++) {
+                       long curr = System.nanoTime();
+                       l.contains(num);
+                       res += System.nanoTime() - curr;
+               }
+               return ((double) res) / numTests;
+       }
+
+       private static double forSearchTestMulti(List<Integer> l, int num, int numTests) {
+               long res = 0;
+               for (int i = 0; i < numTests; i++) {
+                       long curr = System.nanoTime();
+
+                       int j = 0;
+                       while (j < l.size() && !l.get(j).equals(num))
+                               j++;
+
+                       res += System.nanoTime() - curr;
+               }
+               return ((double) res) / numTests;
+       }
+
+       private static double forEachSearchTestMulti(List<Integer> l, int num, int numTests) {
+               long res = 0;
+               for (int i = 0; i < numTests; i++) {
+                       long curr = System.nanoTime();
+
+                       for (int el : l)
+                               if (el == num)
+                                       break;
+
+                       res += System.nanoTime() - curr;
+               }
+               return ((double) res) / numTests;
+       }
+
+       private static double customContainsSortedTestMulti(SortiranaListaBrojeva l, int num, int numTests) {
+               long res = 0;
+               for (int i = 0; i < numTests; i++) {
+                       long curr = System.nanoTime();
+                       l.uListi(num);
+                       res += System.nanoTime() - curr;
+               }
+               return ((double) res) / numTests;
+       }
+}
+
+class SortiranaListaBrojeva {
+       class Element {
+               Integer info;
+               Element veza;
+
+               public Element(int s) {
+                       this.info = s;
+                       this.veza = null;
+               }
+
+               public String toString() {
+                       return info + "";
+               }
+       }
+
+       // pokazivac na prvi element liste
+       Element prvi;
+
+       /** Kreira praznu listu stringova. */
+       public SortiranaListaBrojeva() {
+               this.prvi = null;
+       }
+
+       /** Vraca da li je lista prazna */
+       public boolean jePrazna() {
+               return prvi == null;
+       }
+
+       public String toString() {
+               String rez = "Lista: [ ";
+               Element tekuci = prvi;
+               while (tekuci != null) {
+                       rez += tekuci.info + " ";
+                       tekuci = tekuci.veza;
+               }
+               rez += "]";
+               return rez;
+       }
+
+       public void dodaj(int s) {
+               if (prvi == null || prvi.info.compareTo(s) > 0) {
+                       Element novi = new Element(s);
+                       novi.veza = prvi;
+                       prvi = novi;
+               } else {
+                       if (!prvi.info.equals(s)) {
+                               Element prethodni = prvi;
+
+                               while (prethodni.veza != null && prethodni.veza.info.compareTo(s) < 0) {
+                                       prethodni = prethodni.veza;
+                               }
+                               if (prethodni.veza == null || !prethodni.veza.info.equals(s)) {
+                                       Element novi = new Element(s);
+                                       novi.veza = prethodni.veza;
+                                       prethodni.veza = novi;
+                               }
+                       }
+               }
+       }
+
+       /** Vraca da li String {@code s} postoji u listi. */
+       public boolean uListi(int s) {
+               Element tekuci = prvi;
+               while (tekuci != null && tekuci.info.compareTo(s) < 0) {
+                       tekuci = tekuci.veza;
+               }
+
+               // da li smo trenutno na elementu
+               return tekuci != null && tekuci.info.equals(s);
+       }
+}

diff --git a/kodovi/kolekcije/PrimerArrayList.java b/kodovi/kolekcije/PrimerArrayList.java
new file mode 100644 (file)
index 0000000..5ffc8d4
--- /dev/null
+++ b/kodovi/kolekcije/PrimerArrayList.java
@@ -0,0 +1,35 @@
+import java.util.*;
+
+/**
+ * 
+ */
+public class PrimerArrayList {
+
+  public static ArrayList<String> ucitajIzFajla(String fn) {
+    if (!Svetovid.testIn(fn))
+      return null;
+    ArrayList<String> rez = new ArrayList<>();
+    while (Svetovid.in(fn).hasMore()) {
+      String s = Svetovid.in(fn).readLine();
+      rez.add(s);
+    }
+    Svetovid.in(fn).close();
+    return rez;
+  }
+  
+  public static void main(String[] args) { 
+    ArrayList<String> al = new ArrayList<>();
+    al.add("Studisha");
+    al.add("Imenisha");
+    al.add("Suncoje");
+    
+    System.out.println(al);
+    
+    al.add(2,"Drugan");
+    
+    System.out.println(al);
+    
+    System.out.println(ucitajIzFajla("PrimerArrayList1.java"));
+  }
+  
+}