From a7c9bbd0ab53b9b19a6bac5856735001ce8e3293 Mon Sep 17 00:00:00 2001 From: Doni Pracner Date: Wed, 16 May 2018 00:37:17 +0200 Subject: [PATCH] ListCompare, doterivanja i premestanja delova koda --- kodovi/kolekcije/ListCompare.java | 240 +++++++++++++++++------------- 1 file changed, 133 insertions(+), 107 deletions(-) diff --git a/kodovi/kolekcije/ListCompare.java b/kodovi/kolekcije/ListCompare.java index 8a04c04..2059d05 100644 --- a/kodovi/kolekcije/ListCompare.java +++ b/kodovi/kolekcije/ListCompare.java @@ -7,58 +7,85 @@ 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 SEQ_LENGTH = 500; 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 + System.out.println("--- ubacivanje ---"); compareNormalInsertion(); - compareContains(10000); + System.out.println("--- contains operacija ---"); + compareContains(1000); + System.out.println("--- sortirano ubacivanje ---"); compareSortedInsertion(seq); - System.out.println("custom insertion\n :" + customSortedInsertionTestMulti(seq, TEST_NUMBER)); - System.out.println("custom insertion\n :" + customSortedInsertionTestMulti(seq, TEST_NUMBER)); + System.out.printf("custom insertion%n :%1$10.2f%n", customSortedInsertionTestMulti(seq, TEST_NUMBER)); + System.out.printf("custom insertion%n :%1$10.2f%n", customSortedInsertionTestMulti(seq, TEST_NUMBER)); + System.out.println("--- uklanjanja ---"); compareRemoval(10000); } - private static double customSortedInsertionTestMulti(int[] seq, int numtests) { + 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 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.printf("ll:%1$10.2f%n", insertionTestMulti(ll, seq, nt)); + System.out.printf("al:%1$10.2f%n", insertionTestMulti(al, seq, nt)); + System.out.printf("al:%1$10.2f%n", insertionTestMulti(al, seq, nt)); + System.out.printf("ll:%1$10.2f%n", insertionTestMulti(ll, seq, nt)); + } + + private static double insertionTestMulti(List l, int[] seq, int testNumber) { long sum = 0; - for (int i = 0; i < numtests; i++) { - sum += customSortedInsertion(seq); + 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) / numtests; + return ((double) sum) / testNumber; } - private static long customSortedInsertion(int[] seq) { - SortiranaListaBrojeva slb = new SortiranaListaBrojeva(); + private static long insertionTest(List l, int[] seq) { long startTime = System.nanoTime(); - for (int i : seq) { - slb.dodaj(i); - } + for (int i : seq) + l.add(0, i); return System.nanoTime() - startTime; } @@ -67,22 +94,56 @@ public class ListCompare { 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)); + System.out.printf("ll:%1$10.2f%n", sortedInsertionTestMulti(ll, seq, TEST_NUMBER)); + System.out.printf("al:%1$10.2f%n", sortedInsertionTestMulti(al, seq, TEST_NUMBER)); + System.out.printf("al:%1$10.2f%n", sortedInsertionTestMulti(al, seq, TEST_NUMBER)); + System.out.printf("ll:%1$10.2f%n", 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 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 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 compareRemoval(int seqLength) { @@ -126,56 +187,6 @@ public class ListCompare { 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++) { @@ -189,13 +200,6 @@ public class ListCompare { 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)); @@ -209,27 +213,29 @@ public class ListCompare { } 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.printf("contains al:%1$10.2f%n" , containsTestMulti(al, seqLength + 1, TEST_NUMBER)); + System.out.printf("contains ll:%1$10.2f%n" , containsTestMulti(ll, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-rucn al:%1$10.2f%n" , forSearchTestMulti(al, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-rucn ll:%1$10.2f%n" , forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-each al:%1$10.2f%n" , forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-each ll:%1$10.2f%n" , forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER)); - System.out.println("custom sort:" + customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER)); + System.out.printf("custom sort:%1$10.2f%n" , customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER)); al.set(seqLength / 3, seqLength + 1); ll.set(seqLength / 3, seqLength + 1); + // ovaj moramo uzeti jer je sortirano + int el3 = l.element(seqLength / 3); 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.printf("contains al:%1$10.2f%n" , containsTestMulti(al, seqLength + 1, TEST_NUMBER)); + System.out.printf("contains ll:%1$10.2f%n" , containsTestMulti(ll, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-rucn al:%1$10.2f%n" , forSearchTestMulti(al, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-rucn ll:%1$10.2f%n" , forSearchTestMulti(ll, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-each al:%1$10.2f%n" , forEachSearchTestMulti(al, seqLength + 1, TEST_NUMBER)); + System.out.printf("for-each ll:%1$10.2f%n" , forEachSearchTestMulti(ll, seqLength + 1, TEST_NUMBER)); - System.out.println("custom sort:" + customContainsSortedTestMulti(l, seqLength + 1, TEST_NUMBER)); + System.out.printf("custom sort:%1$10.2f%n" , customContainsSortedTestMulti(l, el3, TEST_NUMBER)); } private static double containsTestMulti(List l, int num, int numTests) { @@ -332,15 +338,35 @@ class SortiranaListaBrojeva { 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; - } + Element novi = new Element(s); + novi.veza = prethodni.veza; + prethodni.veza = novi; } } } + public int element(int k) { + if (k < 0) { + throw new IndexOutOfBoundsException( + "Ne postoje elementi na negativnim pozicijama!"); + } + + Element tekuci = prvi; + int brojac = 0; + + while (tekuci != null && k > brojac) { + tekuci = tekuci.veza; + brojac++; + } + + if (tekuci != null) { + return tekuci.info; + } else { + throw new IndexOutOfBoundsException("Lista je kraca od " + + k); + } + } + /** Vraca da li String {@code s} postoji u listi. */ public boolean uListi(int s) { Element tekuci = prvi; -- 2.17.1