so i've been tasked assignment compare linkedlists , arraylists 2 different things.
part 1) randomly select locations inside list , increment values 1 each list type
part 2) double each list size adding random locations, , remove same amount of random locations bring list down original size.
i feel i've accomplished pretty teacher saying part 1 arraylist should faster (which in code). saying linkedlist should wayyy faster in part 2, exact opposite me... way slower.. i've adding in syso's @ different locations verify lists being modified correctly , , cant figure out why not working out way says should be.
can spot i've done wrong (if anything?). thank much
import java.util.arraylist; import java.util.linkedlist; import java.util.list; import javax.swing.joptionpane; public class linkedlistversusarraylist { public static void main(string[] args) { long starttime, endtime, duration; list<double> ll = new linkedlist<double>(); arraylist<double> al = new arraylist<double>(); int size = integer.parseint(joptionpane.showinputdialog("pick list size (whole number please)")); //fills linked list random doubles (int = 0; < size; i++){ ll.add(math.random()); } //fills arraylist random doubles (int = 0; < size; i++){ al.add(math.random()); } // //part 1 // system.out.println("\npart 1:\nboth lists full of random numbers. \ni cycle through " + "and incremiment random locations " +size+ " times each list.\n"); //testing linkedlist first random access starttime = system.nanotime(); (int = 0; < size; i++){ int x = (int)(ll.size()*math.random()); double y = ll.get(x); ll.set(x, y+1); } endtime = system.nanotime(); duration = (endtime - starttime); system.out.println("linked list took: " +(duration/1000000) +" milli seconds"); //testing arraylist random access starttime = system.nanotime(); (int = 0; < size; i++){ int x = (int)(al.size()*math.random()); double y = al.get(x); al.set(x, y+1); } endtime = system.nanotime(); duration = (endtime - starttime); system.out.println("array list took: " +(duration/1000000) +" milli seconds"); // //part 2 // system.out.println("\npart 2:\nboth lists "+size+" slots added them in random locations.\n" + "after complete, remove "+size+" slots each list @ random\n"); //testing linkedlist first random adding/subtracting starttime = system.nanotime(); //add (int = 0; < size; i++){ int x = (int)(ll.size()*math.random()); ll.add(x, 1.0); } //delete (int = 0; < size; i++){ int x = (int)(ll.size()*math.random()); ll.remove(x); } endtime = system.nanotime(); duration = (endtime - starttime); system.out.println("linked list took: " +(duration/1000000) +" milli seconds"); //testing arraylist random adding/subtracting starttime = system.nanotime(); //add (int = 0; < size; i++){ int x = (int)(al.size()*math.random()); al.add(x, 1.0); } //delete (int = 0; < size; i++){ int x = (int)(al.size()*math.random()); al.remove(x); } endtime = system.nanotime(); duration = (endtime - starttime); system.out.println("array list took: " +(duration/1000000) +" milli seconds"); } }
apart microbenchmarking issues code doesn't control for, teacher's expectations case 2 wrong. disregarding cost of accessing random element of linkedlist (the prerequisite inserting @ spot) , overestimating cost of inserting arraylist. cost of copying contiguous blocks of memory lower cost of chasing long chain of pointers, required access random element of linkedlist.
in reality linkedlist has narrow area of application improvement on arraylist. example, try insert near front of list. way you'll emphasize cost of moving elements in arraylist , de-emphasize cost of accessing member of linkedlist.
Comments
Post a Comment