gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under
the git version control system
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
= 100;
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 compareNormalInsertion();
38 compareContains(10000);
40 compareSortedInsertion(seq
);
42 System
.out
.println("custom insertion\n :" + customSortedInsertionTestMulti(seq
, TEST_NUMBER
));
43 System
.out
.println("custom insertion\n :" + customSortedInsertionTestMulti(seq
, TEST_NUMBER
));
45 compareRemoval(10000);
48 private static double customSortedInsertionTestMulti(int[] seq
, int numtests
) {
50 for (int i
= 0; i
< numtests
; i
++) {
51 sum
+= customSortedInsertion(seq
);
53 return ((double) sum
) / numtests
;
56 private static long customSortedInsertion(int[] seq
) {
57 SortiranaListaBrojeva slb
= new SortiranaListaBrojeva();
58 long startTime
= System
.nanoTime();
62 return System
.nanoTime() - startTime
;
65 private static void compareSortedInsertion(int[] seq
) {
66 ArrayList
<Integer
> al
= new ArrayList
<>();
67 LinkedList
<Integer
> ll
= new LinkedList
<>();
69 System
.out
.println("Sorted insertion test");
70 System
.out
.println("ll:" + sortedInsertionTestMulti(ll
, seq
, TEST_NUMBER
));
71 System
.out
.println("al:" + sortedInsertionTestMulti(al
, seq
, TEST_NUMBER
));
72 System
.out
.println("al:" + sortedInsertionTestMulti(al
, seq
, TEST_NUMBER
));
73 System
.out
.println("ll:" + sortedInsertionTestMulti(ll
, seq
, TEST_NUMBER
));
76 private static void compareNormalInsertion() {
77 int[] seq
= genRandomSequence(10 * SEQ_LENGTH
, new Random(123456789));
78 ArrayList
<Integer
> al
= new ArrayList
<>();
79 LinkedList
<Integer
> ll
= new LinkedList
<>();
81 System
.out
.println("Normal insertion test");
82 System
.out
.println("ll:" + insertionTestMulti(ll
, seq
, nt
));
83 System
.out
.println("al:" + insertionTestMulti(al
, seq
, nt
));
84 System
.out
.println("al:" + insertionTestMulti(al
, seq
, nt
));
85 System
.out
.println("ll:" + insertionTestMulti(ll
, seq
, nt
));
88 private static void compareRemoval(int seqLength
) {
89 int[] seq
= genRandomSequence(seqLength
, new Random(123456789));
90 ArrayList
<Integer
> al
= new ArrayList
<>();
91 LinkedList
<Integer
> ll
= new LinkedList
<>();
92 SortiranaListaBrojeva l
= new SortiranaListaBrojeva();
98 System
.out
.println("test izbacivanja; duzina:" + seqLength
);
99 System
.out
.println("izbacivanje nepostojeceg:");
101 int testNumber
= TEST_NUMBER
;
102 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
103 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
104 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
105 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
108 System
.out
.println("izbacivanje postojeceg na procentu:" + perc
);
109 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
110 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
111 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
112 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
115 System
.out
.println("izbacivanje postojeceg na procentu:" + perc
);
116 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
117 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
118 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
119 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
122 System
.out
.println("izbacivanje postojeceg na procentu:" + perc
);
123 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
124 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
125 System
.out
.printf("ll:%1$10.2f\n", removalTestMulti(ll
, seqLength
+ 2, testNumber
, perc
));
126 System
.out
.printf("al:%1$10.2f\n", removalTestMulti(al
, seqLength
+ 2, testNumber
, perc
));
129 private static double sortedInsertionTestMulti(List
<Integer
> l
, int[] seq
, int numtests
) {
131 for (int i
= 0; i
< numtests
; i
++) {
133 l
= l
.getClass().newInstance();
134 } catch (InstantiationException
| IllegalAccessException e
) {
137 sum
+= sortedInsertionTest(l
, seq
);
140 return ((double) sum
) / numtests
;
143 private static long sortedInsertionTest(List
<Integer
> l
, int[] seq
) {
144 long startTime
= System
.nanoTime();
147 return System
.nanoTime() - startTime
;
150 private static void insertSorted(int num
, List
<Integer
> l
) {
152 while (i
< l
.size() && l
.get(i
) < num
) {
158 private static double insertionTestMulti(List
<Integer
> l
, int[] seq
, int testNumber
) {
160 for (int i
= 0; i
< testNumber
; i
++) {
162 l
= l
.getClass().newInstance();
163 } catch (InstantiationException
| IllegalAccessException e
) {
166 sum
+= insertionTest(l
, seq
);
169 return ((double) sum
) / testNumber
;
172 private static long insertionTest(List
<Integer
> l
, int[] seq
) {
173 long startTime
= System
.nanoTime();
176 return System
.nanoTime() - startTime
;
179 private static double removalTestMulti(List
<Integer
> l
, int num
, int testNumber
, double percentWhere
) {
181 for (int i
= 0; i
< testNumber
; i
++) {
182 if (percentWhere
>= 0) {
183 l
.add((int) (l
.size() * percentWhere
), num
);
185 long startTime
= System
.nanoTime();
186 l
.remove((Integer
) num
);
187 sum
+= System
.nanoTime() - startTime
;
189 return ((double) sum
) / testNumber
;
192 private static int[] genRandomSequence(int length
, Random r
) {
193 int[] rez
= new int[length
];
194 for (int i
= 0; i
< length
; i
++)
195 rez
[i
] = r
.nextInt(length
);
199 private static void compareContains(int seqLength
) {
201 int[] seq
= genRandomSequence(seqLength
, new Random(123456789));
202 ArrayList
<Integer
> al
= new ArrayList
<>();
203 LinkedList
<Integer
> ll
= new LinkedList
<>();
204 SortiranaListaBrojeva l
= new SortiranaListaBrojeva();
211 System
.out
.println("nepostojeci:");
212 System
.out
.println("contains al:" + containsTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
213 System
.out
.println("contains ll:" + containsTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
214 System
.out
.println("for-rucn al:" + forSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
215 System
.out
.println("for-rucn ll:" + forSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
216 System
.out
.println("for-each al:" + forEachSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
217 System
.out
.println("for-each ll:" + forEachSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
219 System
.out
.println("custom sort:" + customContainsSortedTestMulti(l
, seqLength
+ 1, TEST_NUMBER
));
221 al
.set(seqLength
/ 3, seqLength
+ 1);
222 ll
.set(seqLength
/ 3, seqLength
+ 1);
223 System
.out
.println("postojeci:");
225 System
.out
.println("contains al:" + containsTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
226 System
.out
.println("contains ll:" + containsTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
227 System
.out
.println("for-rucn al:" + forSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
228 System
.out
.println("for-rucn ll:" + forSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
229 System
.out
.println("for-each al:" + forEachSearchTestMulti(al
, seqLength
+ 1, TEST_NUMBER
));
230 System
.out
.println("for-each ll:" + forEachSearchTestMulti(ll
, seqLength
+ 1, TEST_NUMBER
));
232 System
.out
.println("custom sort:" + customContainsSortedTestMulti(l
, seqLength
+ 1, TEST_NUMBER
));
235 private static double containsTestMulti(List
<Integer
> l
, int num
, int numTests
) {
237 for (int i
= 0; i
< numTests
; i
++) {
238 long curr
= System
.nanoTime();
240 res
+= System
.nanoTime() - curr
;
242 return ((double) res
) / numTests
;
245 private static double forSearchTestMulti(List
<Integer
> l
, int num
, int numTests
) {
247 for (int i
= 0; i
< numTests
; i
++) {
248 long curr
= System
.nanoTime();
251 while (j
< l
.size() && !l
.get(j
).equals(num
))
254 res
+= System
.nanoTime() - curr
;
256 return ((double) res
) / numTests
;
259 private static double forEachSearchTestMulti(List
<Integer
> l
, int num
, int numTests
) {
261 for (int i
= 0; i
< numTests
; i
++) {
262 long curr
= System
.nanoTime();
268 res
+= System
.nanoTime() - curr
;
270 return ((double) res
) / numTests
;
273 private static double customContainsSortedTestMulti(SortiranaListaBrojeva l
, int num
, int numTests
) {
275 for (int i
= 0; i
< numTests
; i
++) {
276 long curr
= System
.nanoTime();
278 res
+= System
.nanoTime() - curr
;
280 return ((double) res
) / numTests
;
284 class SortiranaListaBrojeva
{
289 public Element(int s
) {
294 public String
toString() {
299 // pokazivac na prvi element liste
302 /** Kreira praznu listu stringova. */
303 public SortiranaListaBrojeva() {
307 /** Vraca da li je lista prazna */
308 public boolean jePrazna() {
312 public String
toString() {
313 String rez
= "Lista: [ ";
314 Element tekuci
= prvi
;
315 while (tekuci
!= null) {
316 rez
+= tekuci
.info
+ " ";
317 tekuci
= tekuci
.veza
;
323 public void dodaj(int s
) {
324 if (prvi
== null || prvi
.info
.compareTo(s
) > 0) {
325 Element novi
= new Element(s
);
329 if (!prvi
.info
.equals(s
)) {
330 Element prethodni
= prvi
;
332 while (prethodni
.veza
!= null && prethodni
.veza
.info
.compareTo(s
) < 0) {
333 prethodni
= prethodni
.veza
;
335 if (prethodni
.veza
== null || !prethodni
.veza
.info
.equals(s
)) {
336 Element novi
= new Element(s
);
337 novi
.veza
= prethodni
.veza
;
338 prethodni
.veza
= novi
;
344 /** Vraca da li String {@code s} postoji u listi. */
345 public boolean uListi(int s
) {
346 Element tekuci
= prvi
;
347 while (tekuci
!= null && tekuci
.info
.compareTo(s
) < 0) {
348 tekuci
= tekuci
.veza
;
351 // da li smo trenutno na elementu
352 return tekuci
!= null && tekuci
.info
.equals(s
);
Svarog.pmf.uns.ac.rs/gitweb
maintanance
Doni Pracner