方法
- 从每个线程的资源列表中，我们创建一个合并列表，称为
CountedResourceList存储<resource-id, total occurrence count of that id>，按计数的递减顺序排列。这将花费 O(rt*log(rt)) 时间。为什么？下面的示例运行中对此进行了解释。同样在同一迭代中，我们创建了一个 HashMap，以便我们可以在 O(1) 时间内找到该资源 ID 将被放置在哪个线程的列表中（基于那些可以关联的人的倒排索引的想法）。
- 接下来，我们创建一个矩阵 - 称为
SortedListMatrix- t 行和 r 列。在这个矩阵中，我们首先将资源 IDCountedResourceList放入该线程的行中，该行最初包含这个最大出现的资源 ID。这样，resource-ids 会按照从最发生到最少发生的顺序耗尽。
- 为了帮助插入资源 ID，我们还创建了一个
int[t] FreeColumnCount用于记录每个线程的总空闲列数。由于具有较少空闲槽的线程在发生冲突时移动资源 ID 的能力较小，因此资源 ID 将首先填充到包含该资源 ID 的线程的空闲槽最少的行中。
- 从包含最高出现资源 ID 的第一个线程的第 0 列开始，我们使用公式选择要放置下一个 id 的位置
row = GetRowForResource(id) in the HashMap, and column = (column+1)%r。如果一行中的结果列被占用，我们通过使用相同的列值公式迭代来获取下一个未占用的列值，而不更改行。因此 -列会被环绕，并且行是从 HashMap 确定的，因此资源 ID 进入正确的列表并且位于冲突最少的位置。
- 完全填充此矩阵后，从第 0 行开始，并将这些行分配给每个线程作为新的最少冲突资源列表。
Attn：我断断续续地提到了几个步骤的复杂性，但很快就会更新整体运行时的复杂性。现在我正在尝试提出一个正确的算法。
样品运行
初步假设和定义：
- 线程数 = t，从线程 0 开始到 t-1
- 每个线程的资源数 = r
- 为线程准备资源列表的总资源将>= r
让我们从 t = 4 的情况开始。T0 = {4, 3, 5}，T1 = {1, 2, 6}，T2 = {3, 1, 2}，T4 = {2, 7, 1}。现在，我知道这个列表已经没有任何冲突了。应该有一个预处理步骤来确定是否应该首先进行一些重新安排。就像如果列表已经有可能的最小冲突或者如果没有冲突，则应该按原样返回列表。不过，让我们看看伪代码的实际作用。
首先，我们读取所有列表中的所有资源，并将它们放入单独的资源 ID 桶中。利用Counting Sort，这将是一个线性步骤，需要O(tr + constant)时间。但是，由于这只会给出资源 id 的计数，因此我们需要进一步使用Merge Sort以按出现次数减少的顺序对 id 进行排序。这一步将花费O((rt) log(rt))。结果将是按出现降序排序的列表或 id -
CountedResourceList= <3 次, id 1>, <3 次, id 2>, <2 次, id 3>, <1 次, id 4, 5, 6, 7>
在同一次迭代中，我们还创建了 HashMap 和FreeColumnCount数组。
接下来，我们创建SortedListMatrix从row = first thread 开始填充以包含最大出现的 resource-id （通过调用 GetRowForResource(id)），column = 0。矩阵最初为空，然后填充如下：
Initially:
{_, _, _}
{_, _, _}
{_, _, _}
{_, _, _}
Taking 1st element '1' at (1, 0):
{_, _, _}
{1, _, _}
{_, _, _}
{_, _, _}
Taking 2nd element '1' at (2, 1):
{_, _, _}
{1, _, _}
{_, 1, _}
{_, _, _}
Taking 3rd element '1' at (3, 2):
{_, _, _}
{1, _, _}
{_, 1, _}
{_, _, 1}
Taking 4th element '2' at (1, 1) as (1, 0) is already occupied:
{_, _, _}
{1, 2, _}
{_, 1, _}
{_, _, 1}
Taking 5th element '2' at (2, 2):
{_, _, _}
{1, 2, _}
{_, 1, 2}
{_, _, 1}
Taking 6th element '2' at (3, 0):
{_, _, _}
{1, 2, _}
{_, 1, 2}
{2, _, 1}
Taking 7th element '3' at (0, 0) because row 2 has least free slots:
{_, _, _}
{1, 2, _}
{3, 1, 2}
{2, _, 1}
Taking 8th element '3' at (0, 1):
{_, 3, _}
{1, 2, _}
{3, 1, 2}
{2, _, 1}
Taking 9th element '4' at (0, 2):
{_, 3, 4}
{1, 2, _}
{3, 1, 2}
{2, _, 1}
Taking 10th element '5' at (0, 0):
{5, 3, 4}
{1, 2, _}
{3, 1, 2}
{2, _, 1}
Taking 11th element '6' at (1, 2):
{5, 3, 4}
{1, 2, 6}
{3, 1, 2}
{2, _, 1}
Taking 12th element '7' at (3, 1):
{5, 3, 4}
{1, 2, 6}
{3, 1, 2}
{2, 7, 1}
上述步骤的运行时复杂度将为O(rt)。
当矩阵完全填充后，T0 将被分配第 0 行作为其资源列表，T1 作为第 1 行...
