如何在java中使用多线程对记录列表进行排序？

Question

我在java中自学多线程。我的虚拟示例是我有一大堆我想要排序的记录（一个2D数组）。单线程方法是使用循环遍历记录列表和排序。我想用多线程程序对固定数量的线程进行排序，在这种情况下，2.一个线程将对列表的前半部分进行排序，第二个线程将对剩下的一半进行排序。然后我想输出现在排序的记录列表的结果。

如何创建一个工作线程池并对记录列表进行排序？我需要担心data是共享资源吗？如何将每个线程的结果返回到原始记录列表？以下是我的代码。

import java.util.*; 

class RunnableProcess implements Runnable { 
    private int[] data; 

    public RunnableProcess(int[] data) { 
     this.data = data; 
    } 

    public void run() { 
    try { 

     // sort the records this thread has access to 
     for (int i = 0; i < data.length; i++) { 
     Arrays.sort(data[i]); 
     } 

    } catch(Exception ex) { 
     ex.printStackTrace(); 
    } 
    } 
} 

class BigData { 

    static int[][] data = new int[1000][1000]; 

    public static void main(String [] args) { 


    // Create records 
    for (int i = 0; i < data.length; i++) { 
     for (int j = 0; j < data[0].length; j++) { 
     data[i][j] = new Random().nextInt(999); 
     } 
    } 

    // Call on two threads to sort the data variable 
    // ExecutorService executor = Executors.newFixedThreadPool(2); 


    // Python type of idea: Pass half the records to each thread and start 
    // java doesn't support this so what is the java way of doing this? 

    // Thread thread = new Thread(new RunnableProcess(data[:499])); 
    // thread.start(); 

    // Thread thread = new Thread(new RunnableProcess(data[499:])); 
    // thread.start(); 

    } 
} 

我很乐意提供解决此问题的最佳方法。

Answer 1

Java不支持以与python相同的方式对本地数组进行分片。我们可以靠近，使用ArrayList。

首先，旁边。您随机生成数据的效率非常低。您正在为您生成的每个随机数字创建一个新的Random数字生成器对象。你只需要一台发电机，像这样：

Random rnd = new Random();      // Only created once 
for (int i = 0; i < data.length; i++) { 
    for (int j = 0; j < data[0].length; j++) { 
     data[i][j] = rnd.nextInt(999); 
    } 
} 

一旦你创建的数据，我们可以把这个本地int[][]二维阵列成List的记录，其中每个记录是int[] 1D阵列：

List<int[]> records = Arrays.asList(data); 

请注意，这不会复制数组中的值。它创建一个List视图的数组。存储在data中的值的任何更改都将反映在records中，反之亦然。

我们这样做，所以我们可以使用List#subList()方法将列表分成两个视图。

List<int[]> first_half = records.subList(0, 500); 
List<int[]> second_half = records.subList(500, 1000); 

再次，这些是视图，由原始列表支持（由原始数组支持）。通过视图进行的更改将反映在原始视图中。

因为我们现在有存储，而不是一个阵列中的List，记录，我们需要更新RunnableProcess使用这种新的格式：

class RunnableProcess implements Runnable { 
    private List<int[]> records; 

    public RunnableProcess(List<int[]> records) { 
     this.records = records; 
    } 

    @Override 
    public void run() { 
     // sort the records this thread has access to 
     for (int[] record : records) { 
      Arrays.sort(record); 
     } 
    } 
} 

现在我们已经将数据划分为两个独立的组，和可以在每组上操作的RunnableProcess。现在，我们可以开始多线程了。

ExecutorService executor = Executors.newFixedThreadPool(2); 

此执行服务创建两个线程池，并会一遍又一遍重复使用这些线程提交到这个执行后续任务。正因为如此，你做不是需要创建并开始自己的线程。执行者会照顾这一点。

executor.submit(new RunnableProcess(first_half)); 
executor.submit(new RunnableProcess(second_half)); 

因为我们想知道什么时候这些任务都完成后，我们需要保存Future从executor.submit()返回：

Future<?> task1 = executor.submit(new RunnableProcess(first_half)); 
Future<?> task2 = executor.submit(new RunnableProcess(second_half)); 

调用Future#get()等待完成任务，并检索结果任务。 （注：由于我们的Runnable不返回一个值，该值null将返回。）

task1.get(); // Wait for first task to finish ... 
task2.get(); // ... as well as the second task to finish. 

最后，你需要#shutdown()执行者，或你的程序可能无法正常终止。

executor.shutdown(); 

---

完整的示例：

List<int[]> records = Arrays.asList(data); 
List<int[]> first_half = records.subList(0, 500); 
List<int[]> second_half = records.subList(500, 1000); 

ExecutorService executor = Executors.newFixedThreadPool(2); 

try { 
    Future<?> task1 = executor.submit(new RunnableProcess(first_half)); 
    Future<?> task2 = executor.submit(new RunnableProcess(second_half)); 

    task1.get(); // Wait for first task to finish ... 
    task2.get(); // ... as well as the second task to finish. 
} catch (InterruptedException | ExecutionException e) { 
    e.printStackTrace(); 
} 

executor.shutdown(); 

---

我需要担心的数据是共享资源？

在这种情况下，没有。您的data是一组数组。每个线程仅引用data数组（作为List），以获得对int[]记录的引用。 data数组本身不被修改;只有记录是，但每个只由其中一个线程修改。

如何将每个线程的结果返回到原始记录列表？

由于记录正在“排序”排序，因此您的data变量已包含您的排序记录数组。对Future#get()的调用可确保每个Thread已完成其处理，以便可以再次从主线程安全地访问数据。