算法

多线程归并排序

Posted by 刘知安 on 2019-12-01
文章目录
  1. 1.前言
  2. 2.实现
  3. 3.结果

1.前言

今天一次偶然的机会，需要做一个多线程下的归并排序测试，然后在网上查看了几个资料，大致了解了思路后自己对着写了一遍，大概做法是这样：

思路就是 “divide and conquer”策略，线程A会把arr拆分成两个，然后新建两个子线程A1和A2，子线程又会递归地创建它们的子线程（A1创建2个，A2也创建两个），也就是说，线程A有个子线程，4个孙子线程这样一直下去。。。你可以根据你的CPU核数来选择，我的是4核的电脑。

2.实现

我觉得还是看代码来的实在，直接放在这里吧，以后有需要再看看，

自定义的Runnable类

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Sorting implements Runnable {
    private int[] arr;
    private int threadCount;

    public Sorting(int[] arr, int threadCount) {
        this.arr = arr;
        this.threadCount = threadCount;
    }
    
    public void run() {
        MergeSort.concurrentMergeSort(arr, threadCount);
    }
}

具体执行逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;


public class MergeSort {

    private static final Random RNG = new Random(10982755L);
    final static int THREAD_MAX = Runtime.getRuntime().availableProcessors();

    public static void main(String... args) {
        System.out.println("Cores of my CPU: " + THREAD_MAX);
        for (int num_cores = 1; num_cores <= THREAD_MAX*2; num_cores = num_cores*2) {
            System.out.println("Current cores number: " + num_cores);
            int arrLen = 32768;  // 2^15
            for (int i = 0; i < 5; i++) {

                int[] arr = randomIntArray(arrLen);
                // System.out.println("======Before sorting ======");
                // System.out.println(Arrays.toString(arr));
                long start = System.currentTimeMillis();
                concurrentMergeSort(arr);
                long end = System.currentTimeMillis();
//            System.out.println("======After sorting ======");
//            System.out.println(Arrays.toString(arr));
                if (!sorted(arr)) {
                    System.err.println("The final array is not sorted");
                    System.exit(0);
                }
                System.out.printf("%10d numbers: %6d ms%n", arrLen, end - start);
                arrLen <<= 2;

            }
        }
    }

    // A public concurrent Merge Sort function for user call without num_threads given
    public static void concurrentMergeSort(int[] arr) {
        int numCores = 4;
        concurrentMergeSort(arr, numCores);
    }

    public static void concurrentMergeSort(int[] arr, int threadCount) {
        if (threadCount <= 1)
            // if use only single thread
            mergeSort(arr);
        else {

            // split array in half
            int[] leftArr = Arrays.copyOfRange(arr, 0, arr.length / 2);
            int[] rightArr = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

            // multi-thread sorting
            Thread lThread = new Thread(new Sorting(leftArr, threadCount / 2));
            Thread rThread = new Thread(new Sorting(rightArr, threadCount / 2));
            lThread.start();
            rThread.start();

            // wait sub-threads result
            try {
                lThread.join();
                rThread.join();
            } catch (InterruptedException ie) {
            }

            // merge them back together
            merge(leftArr, leftArr, arr);
        }
    }

    // 单线程归并排序
    private static void mergeSort(int[] arr) {
        // if length of arr is one, we do nothing, just in-place return it

        // for length grater than 1
        if (arr.length >= 2) {
            // split the original arr into 2 halves
            // Then, sort them respectively
            int[] leftArr = Arrays.copyOfRange(arr, 0, arr.length / 2);
            int[] rightArr = Arrays.copyOfRange(arr, arr.length / 2, arr.length);
            mergeSort(leftArr);
            mergeSort(rightArr);

            // merge the sorted left part and right part
            merge(leftArr, rightArr, arr);
        }

    }

    // merge the sorted left and right arrays into output array.
    public static void merge(int[] left, int[] right, int[] res) {
        int i1 = 0;
        int i2 = 0;
        for (int i = 0; i < res.length; i++) {
            if (i2 >= right.length || (i1 < left.length && left[i1] < right[i2])) {
                res[i] = left[i1];
                i1++;
            } else {
                res[i] = right[i2];
                i2++;
            }
        }
    }

    private static int[] randomIntArray(int arrLen) {
        int[] arr = new int[arrLen];
        for (int i = 0; i < arr.length; i++)
            arr[i] = RNG.nextInt(arrLen * 10);
        return arr;
    }

    public static boolean sorted(int[] arr) {
        return !IntStream.range(1, arr.length)
                .mapToObj(i -> arr[i - 1] > arr[i])
                .findFirst().orElse(false);
    }
}

3.结果

我的电脑是4核的，从结果上可以看到，当指定线程数从从1加到4核时，平均执行耗时有减少，数据量越大越明显，特别是从2核加到4核时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Cores of my CPU: 4
Current cores number: 1
     32768 numbers:     13 ms
    131072 numbers:     18 ms
    524288 numbers:     54 ms
   2097152 numbers:    266 ms
   8388608 numbers:    864 ms
Current cores number: 2
     32768 numbers:      2 ms
    131072 numbers:     11 ms
    524288 numbers:     42 ms
   2097152 numbers:    158 ms
   8388608 numbers:    860 ms
Current cores number: 4
     32768 numbers:      2 ms
    131072 numbers:      5 ms
    524288 numbers:     28 ms
   2097152 numbers:    126 ms
   8388608 numbers:    524 ms
Current cores number: 8
     32768 numbers:      2 ms
    131072 numbers:      5 ms
    524288 numbers:     24 ms
   2097152 numbers:    109 ms
   8388608 numbers:    532 ms

Process finished with exit code 0

FEATURED TAGS
算法
FRIENDS