When performing a merge sort in two lists, both lists having 10000 random integers, but one of the lists have its values being read from a file, and other being randomly generated by java. My problem is, why the mergeSort() is way slower when the list values comes from a file?
First I though that the problem was with the file reading, but the list and its values are created relatively fast(10ms), the slowness begins in the mergeSort(), and I don't know why one is faster than the other.
Main.java
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
ForkJoinPool pool = new ForkJoinPool();
String filePath = "10000.txt";
Vector<Integer> listFromFile = new Vector<Integer>();
Vector<Integer> listRandom = new Vector<Integer>();
Random rand = new Random();
FileInputStream fis = new FileInputStream(filePath);
BufferedReader reader = new BufferedReader(new InputStreamReader(fis));
//10 ms
for (int i = 0; i < 100000; i++) {
int num = rand.nextInt();
listRandom.add(num);
}
String line;
while ((line = reader.readLine()) != null) {
listFromFile.add(Integer.parseInt(line));
}
Instant start = Instant.now();
//way faster 400 ms
MergeSort sort = new MergeSort(listRandom);
//slower 37000 ms
MergeSort sort = new MergeSort(listFromFile);
Vector<Integer> result = pool.invoke(sort);
Instant end = Instant.now();
Duration timeElapsed = Duration.between(start, end);
System.out.println("Time taken: "+ timeElapsed.toMillis() +" milliseconds");
}
}
MergeSort.java
public class MergeSort extends RecursiveTask<Vector<Integer>> {
private final Vector<Integer> list;
public MergeSort(Vector<Integer> list) {
this.list = list;
}
@Override
protected Vector<Integer> compute(){
if (list.size() <= 1) {
return list;
}
Vector<Integer> left = new Vector<Integer>();
Vector<Integer> right = new Vector<Integer>();
for (int i = 0; i < list.size(); i++) {
if (i < list.size() / 2) {
left.add(list.get(i));
} else {
right.add(list.get(i));
}
}
MergeSort _left = new MergeSort(left);
MergeSort _right = new MergeSort(right);
_left.fork();
_right.fork();
Vector<Integer> leftSorted = _left.join();
Vector<Integer> rightSorted = _right.join();
return merge(leftSorted, rightSorted);
}
static Vector<Integer> merge(Vector<Integer> left, Vector<Integer> right) {
Vector<Integer> result = new Vector<Integer>();
while (!left.isEmpty() && !right.isEmpty()) {
if (left.get(0) <= right.get(0)) {
result.add(left.get(0));
left.remove(0);
} else {
result.add(right.get(0));
right.remove(0);
}
}
while (!left.isEmpty()) {
result.add(left.get(0));
left.remove(0);
}
while (!right.isEmpty()) {
result.add(right.get(0));
right.remove(0);
}
return result;
}
}
Aucun commentaire:
Enregistrer un commentaire