gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under
the git version control system
2059d059f7d791314635b2da460f3286365ead6f
1 import java
.util
.ArrayList
;
2 import java
.util
.Arrays
;
3 import java
.util
.LinkedList
;
5 import java
.util
.Random
;
8 * Primeri razlicitih operacija na klasama ArrayList i LinkedList i poredjenje
9 * performansi nad istim podacima.
11 * U nekim primerima se koriste i sopstvene implementacije klasa za poredjenje
14 * NAPOMENA: merenje vremena izvrsavanja u opstem slucaju nije najpouzdanije,
15 * posto racunar skoro nikad ne izvrsava samo taj jedan program.
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.
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.
27 public class ListCompare
{
29 private static final int SEQ_LENGTH
= 500;
30 private static final int TEST_NUMBER
= 100;
32 public static void main(String
[] args
) {
33 // generate random sequence of numbers
34 int[] seq
= genRandomSequence(SEQ_LENGTH
, new Random(123456789));
35 // insert into ArrayList and LinkedList
36 System
.out
.println("--- ubacivanje ---");
37 compareNormalInsertion();
39 System
.out
.println("--- contains operacija ---");
40 compareContains(1000);
42 System
.out
.println("--- sortirano ubacivanje ---");
43 compareSortedInsertion(seq
);
45 System
.out
.printf("custom insertion%n :%1$10.2f%n", customSortedInsertionTestMulti(seq
, TEST_NUMBER
));
46 System
.out
.printf("custom insertion%n :%1$10.2f%n", customSortedInsertionTestMulti(seq
, TEST_NUMBER
));
48 System
.out
.println("--- uklanjanja ---");
49 compareRemoval(10000);
52 private static int[] genRandomSequence(int length
, Random r
) {
53 int[] rez
= new int[length
];
54 for (int i
= 0; i
< length
; i
++)
55 rez
[i
] = r
.nextInt(length
);
59 private static void compareNormalInsertion() {
60 int[] seq
= genRandomSequence(10 * SEQ_LENGTH
, new Random(123456789));
61 ArrayList
<Integer
> al
= new ArrayList
<>();
62 LinkedList
<Integer
> ll
= new LinkedList
<>();
64 System
.out
.println("Normal insertion test");
65 System
.out
.printf("ll:%1$10.2f%n", insertionTestMulti(ll
, seq
, nt
));
66 System
.out
.printf("al:%1$10.2f%n", insertionTestMulti(al
, seq
, nt
));
67 System
.out
.printf("al:%1$10.2f%n", insertionTestMulti(al
, seq
, nt
));
68 System
.out
.printf("ll:%1$10.2f%n", insertionTestMulti(ll
, seq
, nt
));
71 private static double insertionTestMulti(List
<Integer
> l
, int[] seq
, int testNumber
) {
73 for (int i
= 0; i
< testNumber
; i
++) {
75 l
= l
.getClass().newInstance();
76 } catch (InstantiationException
| IllegalAccessException e
) {
79 sum
+= insertionTest(l
, seq
);
82 return ((double) sum
) / testNumber
;
85 private static long insertionTest(List
<Integer
> l
, int[] seq
) {
86 long startTime
= System
.nanoTime();
89 return System
.nanoTime() - startTime
;
92 private static void compareSortedInsertion(int[] seq
) {
93 ArrayList
<Integer
> al
= new ArrayList
<>();
94 LinkedList
<Integer
> ll
= new LinkedList
<>();
96 System
.out
.println("Sorted insertion test");
97 System
.out
.printf("ll:%1$10.2f%n", sortedInsertionTestMulti(ll
, seq
, TEST_NUMBER
));
98 System
.out
.printf("al:%1$10.2f%n", sortedInsertionTestMulti(al
, seq
, TEST_NUMBER
));
99 System
.out
.printf("al:%1$10.2f%n", sortedInsertionTestMulti(al
, seq
, TEST_NUMBER
));
100 System
.out
.printf("ll:%1$10.2f%n", sortedInsertionTestMulti(ll
, seq
, TEST_NUMBER
));
103 private static double sortedInsertionTestMulti(List
<Integer
> l
, int[] seq
, int numtests
) {
105 for (int i
= 0; i
< numtests
; i
++) {
107 l
= l
.getClass().newInstance();
108 } catch (InstantiationException
| IllegalAccessException e
) {
111 sum
+= sortedInsertionTest(l
, seq
);
114 return ((double) sum
) / numtests
;
117 private static long sortedInsertionTest(List
<Integer
> l
, int[] seq
) {
118 long startTime
= System
.nanoTime();
121 return System
.nanoTime() - startTime
;
124 private static void insertSorted(int num
, List
<Integer
> l
) {
126 while (i
< l
.size() && l
.get(i
) < num
) {
132 private static double customSortedInsertionTestMulti(int[] seq
, int numtests
) {
134 for (int i
= 0; i
< numtests
; i
++) {
135 sum
+= customSortedInsertion(seq
);
137 return ((double) sum
) / numtests
;
140 private static long customSortedInsertion(int[] seq
) {
141 SortiranaListaBrojeva slb
= new SortiranaListaBrojeva();
142 long startTime
= System
.nanoTime();
146 return System
.nanoTime() - startTime
;
149 private static void compareRemoval(int seqLength
) {
150 int[] seq
= genRandomSequence(seqLength
, new Random(123456789));
151 ArrayList
<Integer
> al
= new ArrayList
<>();
152 LinkedList
<Integer
> ll
= new LinkedList
<>();
153 SortiranaListaBrojeva l
= new SortiranaListaBrojeva();
159 System
.out
.println("test izbacivanja; duzina:" + seqLength
);
160 System
.out
.println("izbacivanje nepostojeceg:");
162 int testNumber
= TEST_NUMBER
;
163 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
164 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
165 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
166 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
169 System
.out
.println("izbacivanje postojeceg na procentu:" + perc
);
170 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
171 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
172 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
173 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
176 System
.out
.println("izbacivanje postojeceg na procentu:" + perc
);
177 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
178 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
179 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
180 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
183 System
.out
.println("izbacivanje postojeceg na procentu:" + perc
);
184 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
185 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
186 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
187 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
190 private static double removalTestMulti(List
<Integer
> l
, int num
, int testNumber
, double percentWhere
) {
192 for (int i
= 0; i
< testNumber
; i
++) {
193 if (percentWhere
>= 0) {
194 l
.add((int) (l
.size() * percentWhere
), num
);
196 long startTime
= System
.nanoTime();
197 l
.remove((Integer
) num
);
198 sum
+= System
.nanoTime() - startTime
;
200 return ((double) sum
) / testNumber
;
203 private static void compareContains(int seqLength
) {
205 int[] seq
= genRandomSequence(seqLength
, new Random(123456789));
206 ArrayList
<Integer
> al
= new ArrayList
<>();
207 LinkedList
<Integer
> ll
= new LinkedList
<>();
208 SortiranaListaBrojeva l
= new SortiranaListaBrojeva();
215 System
.out
.println("nepostojeci:");
216 System
.out
.printf("contains al:%1$10.2f%n" , containsTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
217 System
.out
.printf("contains ll:%1$10.2f%n" , containsTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
218 System
.out
.printf("for-rucn al:%1$10.2f%n" , forSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
219 System
.out
.printf("for-rucn ll:%1$10.2f%n" , forSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
220 System
.out
.printf("for-each al:%1$10.2f%n" , forEachSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
221 System
.out
.printf("for-each ll:%1$10.2f%n" , forEachSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
223 System
.out
.printf("custom sort:%1$10.2f%n" , customContainsSortedTestMulti(l
, seqLength
+ 1, TEST_NUMBER
));
225 al
.set(seqLength
/ 3, seqLength
+ 1);
226 ll
.set(seqLength
/ 3, seqLength
+ 1);
227 // ovaj moramo uzeti jer je sortirano
228 int el3
= l
.element(seqLength
/ 3);
229 System
.out
.println("postojeci:");
231 System
.out
.printf("contains al:%1$10.2f%n" , containsTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
232 System
.out
.printf("contains ll:%1$10.2f%n" , containsTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
233 System
.out
.printf("for-rucn al:%1$10.2f%n" , forSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
234 System
.out
.printf("for-rucn ll:%1$10.2f%n" , forSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
235 System
.out
.printf("for-each al:%1$10.2f%n" , forEachSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
236 System
.out
.printf("for-each ll:%1$10.2f%n" , forEachSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
238 System
.out
.printf("custom sort:%1$10.2f%n" , customContainsSortedTestMulti(l
, el3
, TEST_NUMBER
));
241 private static double containsTestMulti(List
<Integer
> l
, int num
, int numTests
) {
243 for (int i
= 0; i
< numTests
; i
++) {
244 long curr
= System
.nanoTime();
246 res
+= System
.nanoTime() - curr
;
248 return ((double) res
) / numTests
;
251 private static double forSearchTestMulti(List
<Integer
> l
, int num
, int numTests
) {
253 for (int i
= 0; i
< numTests
; i
++) {
254 long curr
= System
.nanoTime();
257 while (j
< l
.size() && !l
.get(j
).equals(num
))
260 res
+= System
.nanoTime() - curr
;
262 return ((double) res
) / numTests
;
265 private static double forEachSearchTestMulti(List
<Integer
> l
, int num
, int numTests
) {
267 for (int i
= 0; i
< numTests
; i
++) {
268 long curr
= System
.nanoTime();
274 res
+= System
.nanoTime() - curr
;
276 return ((double) res
) / numTests
;
279 private static double customContainsSortedTestMulti(SortiranaListaBrojeva l
, int num
, int numTests
) {
281 for (int i
= 0; i
< numTests
; i
++) {
282 long curr
= System
.nanoTime();
284 res
+= System
.nanoTime() - curr
;
286 return ((double) res
) / numTests
;
290 class SortiranaListaBrojeva
{
295 public Element(int s
) {
300 public String
toString() {
305 // pokazivac na prvi element liste
308 /** Kreira praznu listu stringova. */
309 public SortiranaListaBrojeva() {
313 /** Vraca da li je lista prazna */
314 public boolean jePrazna() {
318 public String
toString() {
319 String rez
= "Lista: [ ";
320 Element tekuci
= prvi
;
321 while (tekuci
!= null) {
322 rez
+= tekuci
.info
+ " ";
323 tekuci
= tekuci
.veza
;
329 public void dodaj(int s
) {
330 if (prvi
== null || prvi
.info
.compareTo(s
) > 0) {
331 Element novi
= new Element(s
);
335 if (!prvi
.info
.equals(s
)) {
336 Element prethodni
= prvi
;
338 while (prethodni
.veza
!= null && prethodni
.veza
.info
.compareTo(s
) < 0) {
339 prethodni
= prethodni
.veza
;
341 Element novi
= new Element(s
);
342 novi
.veza
= prethodni
.veza
;
343 prethodni
.veza
= novi
;
348 public int element(int k
) {
350 throw new IndexOutOfBoundsException(
351 "Ne postoje elementi na negativnim pozicijama!");
354 Element tekuci
= prvi
;
357 while (tekuci
!= null && k
> brojac
) {
358 tekuci
= tekuci
.veza
;
362 if (tekuci
!= null) {
365 throw new IndexOutOfBoundsException("Lista je kraca od "
370 /** Vraca da li String {@code s} postoji u listi. */
371 public boolean uListi(int s
) {
372 Element tekuci
= prvi
;
373 while (tekuci
!= null && tekuci
.info
.compareTo(s
) < 0) {
374 tekuci
= tekuci
.veza
;
377 // da li smo trenutno na elementu
378 return tekuci
!= null && tekuci
.info
.equals(s
);
Svarog.pmf.uns.ac.rs/gitweb
maintanance
Doni Pracner