lundi 7 août 2023

Merge sort performing slower if list comes from a file

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