gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
/**
* 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;
+ private static int seq_length = 1000;
+ private static int test_repeats = 2000;
public static void main(String[] args) {
+ System.out.println(
+ "Broj puta koliko će se testovi ponavljati:" + test_repeats);
+ System.out.println("* ponegde će biti naznačeno ako je drugačije");
+ System.out.println(
+ "Sva vremena su izražena u nanosekundama, dato je prosečno vreme za jednu operaciju");
+ System.out.println();
+ System.out.println("al - ArrayList");
+ System.out.println("ll - LinkedList");
+ System.out.println("sl - naša sortirana lista");
+ System.out.println();
// generate random sequence of numbers
- int[] seq = genRandomSequence(SEQ_LENGTH, new Random(123456789));
+ int[] seq = genRandomSequence(seq_length, new Random(123456789));
+ int[] seqs = genRandomSequence(seq_length / 10, new Random(123456789));
// insert into ArrayList and LinkedList
+ System.out.println("--- ubacivanje ---");
compareNormalInsertion();
- compareContains(10000);
+ System.out.println("--- contains operacija ---");
+ compareContains(seq);
- compareSortedInsertion(seq);
-
- System.out.println("custom insertion\n :" + customSortedInsertionTestMulti(seq, TEST_NUMBER));
- System.out.println("custom insertion\n :" + customSortedInsertionTestMulti(seq, TEST_NUMBER));
+ System.out.println("--- sortirano ubacivanje ---");
+ System.out.println("broj elemenata:" + (seq_length / 10));
+ compareSortedInsertion(seqs);
+ System.out.printf("sl:%1$12.2f%n",
+ customSortedInsertionTestMulti(seqs, test_repeats));
+ System.out.printf("sl:%1$12.2f%n",
+ customSortedInsertionTestMulti(seqs, test_repeats));
+ System.out.println("--- uklanjanja ---");
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 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 compareSortedInsertion(int[] seq) {
+ private static void compareNormalInsertion() {
+ int duz = 10 * seq_length;
+ int[] seq = genRandomSequence(duz, new Random(123456789));
ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
+ int nt = test_repeats / 20;
+ System.out.printf("Broj brojeva: %1d; broj testiranja: %2d%n", duz, nt);
+ System.out.printf("ll:%1$12.2f%n", insertionTestMulti(ll, seq, nt));
+ System.out.printf("al:%1$12.2f%n", insertionTestMulti(al, seq, nt));
+ System.out.printf("al:%1$12.2f%n", insertionTestMulti(al, seq, nt));
+ System.out.printf("ll:%1$12.2f%n", insertionTestMulti(ll, seq, nt));
+ }
+
+ 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);
- 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));
+ }
+ return ((double) sum) / testNumber;
}
- 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 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 void compareRemoval(int seqLength) {
- int[] seq = genRandomSequence(seqLength, new Random(123456789));
+ private static void compareSortedInsertion(int[] seq) {
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));
+ System.out.println("Sortirano ubacivanje");
+ System.out.printf("ll:%1$12.2f%n",
+ sortedInsertionTestMulti(ll, seq, test_repeats));
+ System.out.printf("al:%1$12.2f%n",
+ sortedInsertionTestMulti(al, seq, test_repeats));
+ System.out.printf("al:%1$12.2f%n",
+ sortedInsertionTestMulti(al, seq, test_repeats));
+ System.out.printf("ll:%1$12.2f%n",
+ sortedInsertionTestMulti(ll, seq, test_repeats));
}
- private static double sortedInsertionTestMulti(List<Integer> l, int[] seq, int numtests) {
+ private static double sortedInsertionTestMulti(List<Integer> l, int[] seq,
+ int numtests) {
long sum = 0;
for (int i = 0; i < numtests; i++) {
try {
private static void insertSorted(int num, List<Integer> l) {
int i = 0;
- while (i < l.size() && l.get(i) < num) {
+ while (i < l.size() && l.get(i).compareTo(num) < 0) {
i++;
}
l.add(i, num);
}
- private static double insertionTestMulti(List<Integer> l, int[] seq, int testNumber) {
+ private static double customSortedInsertionTestMulti(int[] seq,
+ int numtests) {
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);
-
+ for (int i = 0; i < numtests; i++) {
+ sum += customSortedInsertion(seq);
}
- return ((double) sum) / testNumber;
+ return ((double) sum) / numtests;
}
- private static long insertionTest(List<Integer> l, int[] seq) {
+ private static long customSortedInsertion(int[] seq) {
+ SortiranaListaBrojeva slb = new SortiranaListaBrojeva();
long startTime = System.nanoTime();
- for (int i : seq)
- l.add(0, i);
+ for (int i : seq) {
+ slb.dodaj(i);
+ }
return System.nanoTime() - startTime;
}
- private static double removalTestMulti(List<Integer> l, int num, int testNumber, double percentWhere) {
+ 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; dužina:" + seqLength);
+ System.out.println("izbacivanje nepostojećeg:");
+ double perc = -1.0;
+ int testNumber = test_repeats;
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+
+ perc = 0.1;
+ System.out.println("izbacivanje postojećeg na procentu:" + perc);
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+
+ perc = 0.5;
+ System.out.println("izbacivanje postojećeg na procentu:" + perc);
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+
+ perc = 0.8;
+ System.out.println("izbacivanje postojećeg na procentu:" + perc);
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("ll:%1$12.2f\n",
+ removalTestMulti(ll, seqLength + 2, testNumber, perc));
+ System.out.printf("al:%1$12.2f\n",
+ removalTestMulti(al, seqLength + 2, testNumber, perc));
+ }
+
+ 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) {
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));
+ private static void compareContains(int[] seq) {
+ int seqLength = seq.length;
+ System.out.println("Broj brojeva:" + seqLength);
ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
SortiranaListaBrojeva l = new SortiranaListaBrojeva();
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));
+ System.out.println("- nepostojeći (-1):");
+ System.out.printf("contains al:%1$12.2f%n",
+ containsTestMulti(al, -1, test_repeats));
+ System.out.printf("contains ll:%1$12.2f%n",
+ containsTestMulti(ll, -1, test_repeats));
+ System.out.printf("petlja al:%1$12.2f%n",
+ loopSearchTestMulti(al, -1, test_repeats));
+ System.out.printf("petlja ll:%1$12.2f%n",
+ loopSearchTestMulti(ll, -1, test_repeats));
+ System.out.printf("for-each al:%1$12.2f%n",
+ forEachSearchTestMulti(al, -1, test_repeats));
+ System.out.printf("for-each ll:%1$12.2f%n",
+ forEachSearchTestMulti(ll, -1, test_repeats));
+
+ System.out.printf("sl uListi :%1$12.2f%n",
+ customContainsSortedTestMulti(l, -1, test_repeats));
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));
+ // ovaj moramo uzeti jer je sortirano
+ int el3 = l.element(seqLength / 3);
+ System.out.println("- postojeći (na trećini dužine):");
+
+ System.out.printf("contains al:%1$12.2f%n",
+ containsTestMulti(al, seqLength + 1, test_repeats));
+ System.out.printf("contains ll:%1$12.2f%n",
+ containsTestMulti(ll, seqLength + 1, test_repeats));
+ System.out.printf("for-ručn al:%1$12.2f%n",
+ loopSearchTestMulti(al, seqLength + 1, test_repeats));
+ System.out.printf("for-ručn ll:%1$12.2f%n",
+ loopSearchTestMulti(ll, seqLength + 1, test_repeats));
+ System.out.printf("for-each al:%1$12.2f%n",
+ forEachSearchTestMulti(al, seqLength + 1, test_repeats));
+ System.out.printf("for-each ll:%1$12.2f%n",
+ forEachSearchTestMulti(ll, seqLength + 1, test_repeats));
+
+ System.out.printf("sl uListi :%1$12.2f%n",
+ customContainsSortedTestMulti(l, el3, test_repeats));
}
- private static double containsTestMulti(List<Integer> l, int num, int numTests) {
+ 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();
return ((double) res) / numTests;
}
- private static double forSearchTestMulti(List<Integer> l, int num, int numTests) {
+ private static double loopSearchTestMulti(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))
+ int size = l.size();
+ while (j < 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) {
+ 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)
+ for (Integer el : l)
+ if (el.equals(num))
break;
res += System.nanoTime() - curr;
return ((double) res) / numTests;
}
- private static double customContainsSortedTestMulti(SortiranaListaBrojeva l, int num, int 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();
if (!prvi.info.equals(s)) {
Element prethodni = prvi;
- while (prethodni.veza != null && prethodni.veza.info.compareTo(s) < 0) {
+ 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;