/** IMPORTANT UPDATE:
This implementation contains two serious FLAWS.
INSTEAD you should see how it is done correctly at: http://i...content-available-to-author-only...e.com/JOJ05
1. Using indexes to iterate over a linked-list is BAD. The index value need to be calculated for each index update.
2. Using ArrayList but treating it as a List incurs sever overhead.
CORRECTING: Both fixes a lot of performance issues. There will still be a factor 2-3 times slower linked-list then ArrayList
*/
/**
* Java example of the original C++ std::vector vs std::list comparison.
* Insertion of random elements, after linear traversal to get to the right position.
* Insertion in sorted order.
*
* Java version of C++ std::vector (dynamic array) is ArrayList
* Java version of C++ std::list (linked list) is LinkedList
*
* The original author was George Aristy. The code was hacked by KjellKod
* to use in codeproject article. This code was originally a java blog response from
* http://l...content-available-to-author-only...t.com/2012/03/performance-comparison-linked-list-vs.html?m=1 */
import java.util.ArrayList;
import java.util.Date;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Vector;
/**
* Original author was George Aristy but hacked by KjellKod
* to use in codeproject article.
*/
public class Main {
/**
* @param args the command line arguments
*/
try{
print("Compare silly-linear sorted insertion of random values: Times in microseconds (us)");
print("#Elements, LinkedList, ArrayList, Vector");
listVsVectorLinearPerformance(100);
listVsVectorLinearPerformance(200);
listVsVectorLinearPerformance(500);
listVsVectorLinearPerformance(1000);
listVsVectorLinearPerformance(2000);
listVsVectorLinearPerformance(3000);
listVsVectorLinearPerformance(4000);
}
finally { /* */ }
}
private static void listVsVectorLinearPerformance(int size) {
// TODO code application logic here
int arraySize = size;
int maxArraySize = size;
do {
LinkedList<Integer> linkedList = new LinkedList<Integer>();
linkedList.add(-1);
ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
Vector<Integer> vector = new Vector<Integer>();
vector.add(-1);
for(int i = 0; i < array.length; i++){
array
[i
] = random.
nextInt(Integer.
MAX_VALUE); }
long before
= System.
nanoTime(); linearInsertion(array, linkedList);
long linkedListTime
= (System.
nanoTime() - before
)/1000;
linearInsertion(array, arrayList);
long arrayListTime
= (System.
nanoTime() - before
)/1000;
linearInsertion(array, vector);
Long vectorTime
= (System.
nanoTime() - before
)/1000;
print(arraySize + ",\t\t" + linkedListTime + ",\t\t" + arrayListTime + "\t " + vectorTime);
arraySize+=10000;
}while(arraySize <= maxArraySize);
//print("Elapsed time (ms): " + (new Date().getTime() - now.getTime()));
//print("");
}
private static void linearInsertion
(Integer[] intArray, List
<Integer
> list
){ /*int list_size = list.size();*/
for(int i = 0; i < list.size(); i++){
if(integer.compareTo(list.get(i)) >= 0){
list.add(i, integer);
break;
}
}
}
}
private static void print
(String msg
){ }
}