From: Doni Pracner Date: Wed, 10 May 2017 23:21:50 +0000 (+0200) Subject: Ugradjene kolekcije, primeri upotrebe i poredjenje performansi X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa1-materijali.git;a=commitdiff_plain;h=67bed8baf2ce329f7aac519c8c908f23f3dfa0af Ugradjene kolekcije, primeri upotrebe i poredjenje performansi --- diff --git a/kodovi/kolekcije/ListCompare.java b/kodovi/kolekcije/ListCompare.java new file mode 100644 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 al = new ArrayList<>(); + LinkedList 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 al = new ArrayList<>(); + LinkedList 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 al = new ArrayList<>(); + LinkedList 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 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 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 l) { + int i = 0; + while (i < l.size() && l.get(i) < num) { + i++; + } + l.add(i, num); + } + + private static double insertionTestMulti(List 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 l, int[] seq) { + long startTime = System.nanoTime(); + for (int i : seq) + l.add(0, i); + return System.nanoTime() - startTime; + } + + private static double removalTestMulti(List 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 al = new ArrayList<>(); + LinkedList 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 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 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 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 index 0000000..5ffc8d4 --- /dev/null +++ b/kodovi/kolekcije/PrimerArrayList.java @@ -0,0 +1,35 @@ +import java.util.*; + +/** + * + */ +public class PrimerArrayList { + + public static ArrayList ucitajIzFajla(String fn) { + if (!Svetovid.testIn(fn)) + return null; + ArrayList 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 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")); + } + +}