import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.util.Vector;
public class Main {
static class Result {
int size;
long linkedListTime;
long arrayListTime;
long vectorTime;
public Result(int size) {
this.size = size;
}
}
// warm up code to make the benchmark more accurate
for (int i = 0; i < 100; i++)
listVsVectorLinearPerformance(1000);
// print the header
System.
out.
printf("%-15s %-20s %-20s %-20s%n",
"#Elements", "LinkedList", "ArrayList", "Vector");
// perform the benchmarking
printResult(listVsVectorLinearPerformance(100));
printResult(listVsVectorLinearPerformance(200));
printResult(listVsVectorLinearPerformance(500));
printResult(listVsVectorLinearPerformance(1000));
printResult(listVsVectorLinearPerformance(2000));
printResult(listVsVectorLinearPerformance(3000));
printResult(listVsVectorLinearPerformance(4000));
}
private static void printResult(Result r) {
long min
= Math.
min(r.
linkedListTime,
Math.
min(r.
arrayListTime, r.
vectorTime));
System.
out.
printf("%-15d %-10d (%-3.0f%%) %-10d (%-3.0f%%) %-10d (%-3.0f%%)%n",
r.size,
r.linkedListTime, (100 * (double) r.linkedListTime) / min,
r.arrayListTime, (100 * (double) r.arrayListTime) / min,
r.vectorTime, (100 * (double) r.vectorTime) / min);
}
private static Result listVsVectorLinearPerformance(int size) {
LinkedList
<Integer
> linkedList
= new LinkedList
<Integer
>(Arrays.
asList(-1)); ArrayList
<Integer
> arrayList
= new ArrayList
<Integer
>(Arrays.
asList(-1)); Vector
<Integer
> vector
= new Vector
<Integer
>(Arrays.
asList(-1));
for (int i = 0; i < array.length; i++)
array
[i
] = random.
nextInt(Integer.
MAX_VALUE);
Result result = new Result(size);
long before
= System.
nanoTime(); linearInsertion(array, linkedList);
result.
linkedListTime = (System.
nanoTime() - before
) / 1000;
linearInsertion(array, arrayList);
result.
arrayListTime = (System.
nanoTime() - before
) / 1000;
linearInsertion(array, vector);
result.
vectorTime = (System.
nanoTime() - before
) / 1000;
// check that they are equal
if (!(linkedList.equals(arrayList) && arrayList.equals(vector)))
return result;
}
private static void linearInsertion
(Integer[] intArray, LinkedList
<Integer
> list
) { for (ListIterator<Integer> it = list.listIterator(); it.hasNext();) {
if (integer.compareTo(it.next()) >= 0) {
it.previous(); // should be added before element
it.add(integer);
break;
}
}
}
}
private static void linearInsertion
(Integer[] intArray, List
<Integer
> list
) { for (int i = 0; i < list.size(); i++) {
if (integer.compareTo(list.get(i)) >= 0) {
list.add(i, integer);
break;
}
}
}
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuQXJyYXlzOwppbXBvcnQgamF2YS51dGlsLkxpbmtlZExpc3Q7CmltcG9ydCBqYXZhLnV0aWwuTGlzdDsKaW1wb3J0IGphdmEudXRpbC5MaXN0SXRlcmF0b3I7CmltcG9ydCBqYXZhLnV0aWwuUmFuZG9tOwppbXBvcnQgamF2YS51dGlsLlZlY3RvcjsKCnB1YmxpYyBjbGFzcyBNYWluIHsKCglzdGF0aWMgY2xhc3MgUmVzdWx0IHsKCQlpbnQgc2l6ZTsKCQlsb25nIGxpbmtlZExpc3RUaW1lOwoJCWxvbmcgYXJyYXlMaXN0VGltZTsKCQlsb25nIHZlY3RvclRpbWU7CgkJCgkJcHVibGljIFJlc3VsdChpbnQgc2l6ZSkgewoJCQl0aGlzLnNpemUgPSBzaXplOwoJCX0KCX0KCQoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIEV4Y2VwdGlvbiB7CgoJCS8vIHdhcm0gdXAgY29kZSB0byBtYWtlIHRoZSBiZW5jaG1hcmsgbW9yZSBhY2N1cmF0ZQoJCWZvciAoaW50IGkgPSAwOyBpIDwgMTAwOyBpKyspCgkJCWxpc3RWc1ZlY3RvckxpbmVhclBlcmZvcm1hbmNlKDEwMDApOwoKCQkvLyBwcmludCB0aGUgaGVhZGVyCgkJU3lzdGVtLm91dC5wcmludGYoIiUtMTVzICUtMjBzICUtMjBzICUtMjBzJW4iLCAKCQkJCQkJICAiI0VsZW1lbnRzIiwgICJMaW5rZWRMaXN0IiwgIkFycmF5TGlzdCIsICJWZWN0b3IiKTsKCgkJLy8gcGVyZm9ybSB0aGUgYmVuY2htYXJraW5nCgkJcHJpbnRSZXN1bHQobGlzdFZzVmVjdG9yTGluZWFyUGVyZm9ybWFuY2UoMTAwKSk7CgkJcHJpbnRSZXN1bHQobGlzdFZzVmVjdG9yTGluZWFyUGVyZm9ybWFuY2UoMjAwKSk7CgkJcHJpbnRSZXN1bHQobGlzdFZzVmVjdG9yTGluZWFyUGVyZm9ybWFuY2UoNTAwKSk7CgkJcHJpbnRSZXN1bHQobGlzdFZzVmVjdG9yTGluZWFyUGVyZm9ybWFuY2UoMTAwMCkpOwoJCXByaW50UmVzdWx0KGxpc3RWc1ZlY3RvckxpbmVhclBlcmZvcm1hbmNlKDIwMDApKTsKCQlwcmludFJlc3VsdChsaXN0VnNWZWN0b3JMaW5lYXJQZXJmb3JtYW5jZSgzMDAwKSk7CgkJcHJpbnRSZXN1bHQobGlzdFZzVmVjdG9yTGluZWFyUGVyZm9ybWFuY2UoNDAwMCkpOwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgcHJpbnRSZXN1bHQoUmVzdWx0IHIpIHsKCQkKCQlsb25nIG1pbiA9IE1hdGgubWluKHIubGlua2VkTGlzdFRpbWUsIE1hdGgubWluKHIuYXJyYXlMaXN0VGltZSwgci52ZWN0b3JUaW1lKSk7CgkJCgkJU3lzdGVtLm91dC5wcmludGYoIiUtMTVkICUtMTBkICglLTMuMGYlJSkgICAgJS0xMGQgKCUtMy4wZiUlKSAgICAlLTEwZCAoJS0zLjBmJSUpJW4iLCAKCQkJCXIuc2l6ZSwgCgkJCQlyLmxpbmtlZExpc3RUaW1lLCAoMTAwICogKGRvdWJsZSkgci5saW5rZWRMaXN0VGltZSkgLyBtaW4sCgkJCQlyLmFycmF5TGlzdFRpbWUsICAoMTAwICogKGRvdWJsZSkgci5hcnJheUxpc3RUaW1lKSAvIG1pbiwKCQkJCXIudmVjdG9yVGltZSwgICAgICgxMDAgKiAoZG91YmxlKSByLnZlY3RvclRpbWUpIC8gbWluKTsKCX0KCglwcml2YXRlIHN0YXRpYyBSZXN1bHQgbGlzdFZzVmVjdG9yTGluZWFyUGVyZm9ybWFuY2UoaW50IHNpemUpIHsKCgkJSW50ZWdlcltdIGFycmF5ID0gbmV3IEludGVnZXJbc2l6ZV07CgkJUmFuZG9tIHJhbmRvbSA9IG5ldyBSYW5kb20oMTIzNDU2Nzg5TCk7CgkJCgkJTGlua2VkTGlzdDxJbnRlZ2VyPiBsaW5rZWRMaXN0ID0gbmV3IExpbmtlZExpc3Q8SW50ZWdlcj4oQXJyYXlzLmFzTGlzdCgtMSkpOwoJCUFycmF5TGlzdDxJbnRlZ2VyPiBhcnJheUxpc3QgPSBuZXcgQXJyYXlMaXN0PEludGVnZXI+KEFycmF5cy5hc0xpc3QoLTEpKTsKCQlWZWN0b3I8SW50ZWdlcj4gdmVjdG9yID0gbmV3IFZlY3RvcjxJbnRlZ2VyPihBcnJheXMuYXNMaXN0KC0xKSk7CgoJCWZvciAoaW50IGkgPSAwOyBpIDwgYXJyYXkubGVuZ3RoOyBpKyspIAoJCQlhcnJheVtpXSA9IHJhbmRvbS5uZXh0SW50KEludGVnZXIuTUFYX1ZBTFVFKTsKCgkJUmVzdWx0IHJlc3VsdCA9IG5ldyBSZXN1bHQoc2l6ZSk7CgkJCgkJbG9uZyBiZWZvcmUgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlsaW5lYXJJbnNlcnRpb24oYXJyYXksIGxpbmtlZExpc3QpOwoJCXJlc3VsdC5saW5rZWRMaXN0VGltZSA9IChTeXN0ZW0ubmFub1RpbWUoKSAtIGJlZm9yZSkgLyAxMDAwOwoKCQliZWZvcmUgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlsaW5lYXJJbnNlcnRpb24oYXJyYXksIGFycmF5TGlzdCk7CgkJcmVzdWx0LmFycmF5TGlzdFRpbWUgPSAoU3lzdGVtLm5hbm9UaW1lKCkgLSBiZWZvcmUpIC8gMTAwMDsKCgkJYmVmb3JlID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJbGluZWFySW5zZXJ0aW9uKGFycmF5LCB2ZWN0b3IpOwoJCXJlc3VsdC52ZWN0b3JUaW1lID0gKFN5c3RlbS5uYW5vVGltZSgpIC0gYmVmb3JlKSAvIDEwMDA7CgoJCS8vIGNoZWNrIHRoYXQgdGhleSBhcmUgZXF1YWwKCQlpZiAoIShsaW5rZWRMaXN0LmVxdWFscyhhcnJheUxpc3QpICYmIGFycmF5TGlzdC5lcXVhbHModmVjdG9yKSkpCgkJCXRocm93IG5ldyBSdW50aW1lRXhjZXB0aW9uKCJOb3QgZXF1YWwuLi4iKTsKCQkKCQlyZXR1cm4gcmVzdWx0OwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgbGluZWFySW5zZXJ0aW9uKEludGVnZXJbXSBpbnRBcnJheSwgTGlua2VkTGlzdDxJbnRlZ2VyPiBsaXN0KSB7CgkJZm9yIChJbnRlZ2VyIGludGVnZXIgOiBpbnRBcnJheSkgewoJCQlmb3IgKExpc3RJdGVyYXRvcjxJbnRlZ2VyPiBpdCA9IGxpc3QubGlzdEl0ZXJhdG9yKCk7IGl0Lmhhc05leHQoKTspIHsKCQkJCWlmIChpbnRlZ2VyLmNvbXBhcmVUbyhpdC5uZXh0KCkpID49IDApIHsKCQkJCQlpdC5wcmV2aW91cygpOyAvLyBzaG91bGQgYmUgYWRkZWQgYmVmb3JlIGVsZW1lbnQKCQkJCQlpdC5hZGQoaW50ZWdlcik7CgkJCQkJYnJlYWs7CgkJCQl9CgkJCX0KCQl9Cgl9CgoJcHJpdmF0ZSBzdGF0aWMgdm9pZCBsaW5lYXJJbnNlcnRpb24oSW50ZWdlcltdIGludEFycmF5LCBMaXN0PEludGVnZXI+IGxpc3QpIHsKCQlmb3IgKEludGVnZXIgaW50ZWdlciA6IGludEFycmF5KSB7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgbGlzdC5zaXplKCk7IGkrKykgewoJCQkJaWYgKGludGVnZXIuY29tcGFyZVRvKGxpc3QuZ2V0KGkpKSA+PSAwKSB7CgkJCQkJbGlzdC5hZGQoaSwgaW50ZWdlcik7CgkJCQkJYnJlYWs7CgkJCQl9CgkJCX0KCQl9Cgl9Cn0K