arrays - 如何将数组拆分为偶数 block 以进行并行处理

Question

我有大量按发票日期排序的发票数据。我想按日期的某些函数汇总数据，例如:按月、季度等。由于数组非常大，我想利用多线程，并在不同线程中并行处理数组的几个部分。

正在寻找一种算法将数组拆分为 N 个 block ，大小尽可能相似，条件是数组中没有两个元素的日期转换函数会产生相同的结果分为两个不同的 block 。

因此，例如，如果我选择按月对其进行分区，则 2014 年 11 月的所有发票都将由同一线程处理。

我只是想知道这是否是一个已知的名称问题，算法已经存在，这将使我免于重新发明轮子。

Answer 1

对于您的情况(和任何情况)，多线程可能会或可能不会加速您的应用程序。这取决于无数因素。

也就是说，一个常见的模式是有一堆 worker threads in a pool .

伪代码应该是这样的:

while your array is not empty 
  if there is at least one idle worker
    pick one idle thread and process element 0 from the array
    Remove element 0 from the array
    Process the element
  else wait for a worker thread to be idle

我不会费心按月或类似方式拆分，因为这会导致其他问题，您有几个月没有数据或几个月有大量数据，这会扭曲并行性。

如果你真的想要排序，那么你的工作线程可以在正确的地方插入处理过的数据。但是要小心同步。如果你有一个线程运行上面的 while，那么你是正确的，但是如果多个线程试图插入到“结果数组”，那么你需要在插入之前锁定它

根据您的评论进行编辑:

如果你真的想避免同步并认为让所有线程写入同一个数组会起作用(某些语言可能不允许这样做，真的不确定)，那么将所有数据放在一个数组中，将数组分成 N 等份M 长度的 block 。创建一个包含 NxM 个存储桶的结果数组，然后当您有一个空闲的 worker 启动时，将它分配给第 N 个 block 和第 N 个存储桶。

在执行结束时，您的数据将被排序并连续