我正在尝试实现Karmarkar-Karp启发式数字分割算法的k-分割版本。但我在第二阶段中遇到了困难,即从差集重建数字分割。
我能找到的唯一详细描述第二阶段伪代码的来源是论文的第58页:多标准图分区的多物理模拟负载平衡。
给定多重集合S = [1,7,5,10,9,3],将其划分为三个(k=3)子集,算法经历了两个阶段。
第一阶段:
首先按降序对S进行排序:
S = [10,9,7,5,3,1]
然后,将S中的每个数字转换为大小为k的元组,第一个条目是数字本身,其他条目都是零:
M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
这创建了矩阵M。
在每一步中,从M中删除(a, b, c)和(x, y, z),并在原地形成一个新的元组:E := (a + x, b + y, c + z)。该元组通过其最小值进行归一化,并按降序排序,然后按顺序插入回M中。在每个步骤中,算法通过将它们放入两个堆栈中来记忆旧值数组([a, x], [b, y], [c, z])和用于归一化的数字。
针对旧值数组中的每个元组,它会计算一个在 M 中搜索的值。
然后在 M 中搜索包含该值的分区,并用该元组替换该值:
在每次迭代中,它不会将两个元组放入同一个分区。因此,[0,1] 进入最后一个分区:
我能找到的唯一详细描述第二阶段伪代码的来源是论文的第58页:多标准图分区的多物理模拟负载平衡。
给定多重集合S = [1,7,5,10,9,3],将其划分为三个(k=3)子集,算法经历了两个阶段。
第一阶段:
首先按降序对S进行排序:
S = [10,9,7,5,3,1]
然后,将S中的每个数字转换为大小为k的元组,第一个条目是数字本身,其他条目都是零:
M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
这创建了矩阵M。
在每一步中,从M中删除(a, b, c)和(x, y, z),并在原地形成一个新的元组:E := (a + x, b + y, c + z)。该元组通过其最小值进行归一化,并按降序排序,然后按顺序插入回M中。在每个步骤中,算法通过将它们放入两个堆栈中来记忆旧值数组([a, x], [b, y], [c, z])和用于归一化的数字。
M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
Old values: []
Norm. numbers: []
M = [[10,9,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
Old values: [([10,0],[0,0],[0,9])]
Norm. numbers: [0]
M = [[5,0,0],[3,0,0],[3,2,0],[1,0,0]]
Old values: [([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [7,0]
M = [[5,3,0],[3,2,0],[1,0,0]]
Old values: [([5,0],[0,0],[0,3]), ([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [0,7,0]
M = [[2,2,0],[1,0,0]]
Old values: [([5,0],[3,2],[0,3]), ([5,0],[0,0],[0,3]), ([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [3,0,7,0]
M = [[1,1,0]]
Old values: [([2,0],[2,0],[0,1]), ([5,0],[3,2],[0,3]), ([5,0],[0,0],[0,3]), ([10,0],[9,0],[0,7]), ([10,0],[0,0],[0,9])]
Norm. numbers: [1,3,0,7,0]
第二阶段:
第二阶段从差集、记忆的旧值和归一化数字中构建分区。
在每个步骤中,它会弹出记忆的旧值数组和归一化数字:
M = [[1],[1],[0]]
Old values: [[2,0],[2,0],[0,1]]
Norm. number: 1
针对旧值数组中的每个元组,它会计算一个在 M 中搜索的值。
[2,0]: 2 + 0 - 1 = 1
然后在 M 中搜索包含该值的分区,并用该元组替换该值:
[[2,0],[1],[0]]
[2,0]: 2 + 0 - 1 = 1
=> [[2,0],[2,0],[0]]
在每次迭代中,它不会将两个元组放入同一个分区。因此,[0,1] 进入最后一个分区:
[0,1]: 0 + 1 - 1 = 0
=> [[2,0],[2,0],[0,1]]
等等:
M = [[2,0],[2,0],[0,1]]
Old values: [[5,0],[3,2],[0,3]]
Norm. number: 3
M = [[0,0,5],[0,3,2],[1,0,3]]
Old values: [[5,0],[0,0],[0,3]]
Norm. number: 0
问题来了:
M = [[0,0,0,5],[3,2,0,0],[1,0,0,3]]
Old values: [[10,0],[9,0],[0,7]]
Norm. number: 7
[10,0]: 10 + 0 - 7 = 3
=> [[0,0,0,5],[10,0,2,0,0],[1,0,0,3]]
[9,0]: 9 + 0 - 7 = 2
=> ???
我已经在这个迭代中将[10,0]元组放入了[3,2,0,0]分区,所以我不能再将另一个元组放入其中。但是,M没有包含值2的其它分区。
如果允许在出现这种情况时将多个元组放入同一个分区,那么得到的分区将远非最优:
[[0,0,0,0,5,7],[0,0,0,0,0,0,10,9],[1,0,0,3]]
我认为我可以使用最大二分匹配来解决这个问题,但这感觉像是一个肮脏的技巧。
我是否漏掉了一些重要的步骤或者有更好的方法来重构分区?
结论:
David Eisenstat提供了一个优雅且快速的C++面向对象实现算法。
但是,由于我的工作需要,我需要将其改写为PHP语言。直接翻译实现代码会导致内存效率低下和速度慢。内存效率低下是因为每个数字都被包装成一个子集对象。而且,使用PHP对对象数组进行排序比对数字数组进行排序要慢一个数量级。例如,在使用这种方法将500000个数字分成100个子集时,需要138秒,而我的贪心算法实现只需要9秒。经过两天的性能分析,我使用数组重新编写了PHP实现。它看起来很丑陋,但在k值较低时,它的性能优于我的贪心算法实现,并且在k值较高时速度不会太慢:
K: 2
Greedy: 330 (seconds)
Karmarkar–Karp: 6
K: 4
Greedy: 177
Karmarkar–Karp: 6
K: 8
Greedy: 85
Karmarkar–Karp: 6
K: 16
Greedy: 43
Karmarkar–Karp: 8
K: 32
Greedy: 21
Karmarkar–Karp: 11
K: 64
Greedy: 11
Karmarkar–Karp: 20
K: 128
Greedy: 8
Karmarkar–Karp: 33
K: 256
Greedy: 3
Karmarkar–Karp: 61
我希望David Eisenstat的答案和我的解决方案都能对您有所帮助。
<?php
function greedy(array $array, int $k) : array
{
$result = new \Ds\PriorityQueue();
for ($i = 0; $i < $k; $i++)
{
$result->push([], 0);
}
sort($array, SORT_NUMERIC);
while (!empty($array))
{
$number = array_pop($array);
$smallestSumArray = $result->pop();
$smallestSumArray [] = $number;
$sum = array_sum($smallestSumArray);
$result->push($smallestSumArray, -$sum);
}
return $result->toArray();
}
function karmarkarKarp(array $array, int $k) : array
{
$id = PHP_INT_MIN;
$heap = new \Ds\PriorityQueue();
$idToNumbers = new \Ds\Map();
$idToSum = new \Ds\Map();
/**
* Convert every number into an ID that is connected with a numbers array using $idToNumbers map
* and with a sum using $idToSum map
*/
foreach ($array as $number)
{
$idToNumbers[$id] = new \Ds\Stack([$number]);
$idToSum[$id] = $number;
$heap->push([$id], $number);
++$id;
}
//Partitioning:
$sumToId = [];
while ($heap->count() > 1)
{
/** @var array $a */
$a = $heap->pop();
/** @var array $b */
$b = $heap->pop();
for ($i = 0; $i < $k; $i++)
{
$reverseI = $k - 1 - $i;
if (!isset($a[$i]) && !isset($b[$reverseI])) // Instead of filling k-tuple with zeroes just check that a position is set
{
continue;
}
if (!isset($a[$i]) || !isset($b[$reverseI]))
{
$Ai = $a[$i] ?? $b[$reverseI];
unset($a[$i], $b[$reverseI]);
$sum = $idToSum[$Ai];
isset($sumToId[$sum]) ? $sumToId[$sum] []= $Ai : $sumToId[$sum] = [$Ai];
continue;
}
/** @var int $Ai */
$Ai = $a[$i];
/** @var int $Bk */
$Bk = $b[$reverseI];
unset($a[$i], $b[$reverseI]);
$aNumbers = $idToNumbers[$Ai];
$bNumbers = $idToNumbers[$Bk];
while (!$bNumbers->isEmpty())
{
$aNumbers->push($bNumbers->pop());
}
$sum = $idToSum[$Ai] + $idToSum[$Bk];
$idToSum[$Ai] = $sum;
isset($sumToId[$sum]) ? $sumToId[$sum] []= $Ai : $sumToId[$sum] = [$Ai];
$idToNumbers->remove($Bk);
$idToSum->remove($Bk);
}
krsort($sumToId); // It's faster than using usort() to sort $a by sums in $idToSum map
$a = array_merge(...$sumToId);
$sumToId = [];
$difference = $idToSum[$a[0]] - (isset($a[$k -1]) ? $idToSum[$a[$k -1]] : 0);
$heap->push($a, $difference);
}
//Preparing the resulting array:
/** @var array $last */
$last = $heap->pop();
array_walk($last, function (&$item) use ($idToNumbers) {
/** @var \Ds\Stack $numbersStack */
$numbersStack = $idToNumbers[$item];
$item = [];
while (!$numbersStack->isEmpty())
{
$item []= $numbersStack->pop();
}
});
return $last;
}
$randomArray = [];
for ($i = 0; $i < 500000; $i++)
{
$randomArray []= random_int(1, 6000);
}
for ($k = 2; $k <= 256; $k *= 2)
{
echo PHP_EOL . 'K: ' . $k;
$time = time();
$result = greedy($randomArray, $k);
echo PHP_EOL . 'Greedy: ' . (time() - $time);
gc_mem_caches();
$time = time();
$result = karmarkarKarp($randomArray, $k);
echo PHP_EOL . 'Karmarkar–Karp: ' . (time() - $time) . PHP_EOL;
gc_mem_caches();
}