Karmarkar-Karp启发式多路划分算法如何进行分区重构?
我正在实现Karmarkar-Karp启发式数字划分算法的k分区版本,卡在第二阶段从生成的差集重构数字分区的步骤。目前能找到的唯一完整描述该第二阶段伪代码的资料是《Load balancing of multiphysics simulations by multi-criteria graph partitioning》论文的第58页。
以多重集S = [1,7,5,10,9,3]划分为3个(k=3)子集为例,算法分为两个阶段:
阶段1
首先将S降序排序:S = [10,9,7,5,3,1]
之后将S中的每个数字转换为长度为k的元组,第一个元素为数字本身,其余为0,生成矩阵M:M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0]]
每一步从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]
阶段2
第二阶段基于生成的差集、存储的旧值和归一化数值构建分区,每一步弹出存储的旧值数组和归一化数值,执行过程如下:
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++ OOP实现,但我工作中需要将其改写为PHP版本。直接转译的实现内存效率低、运行速度慢:内存效率低是因为每个数字都被封装为Subset对象,运行慢是因为PHP中对象数组的排序速度比数字数组慢一个数量级。例如使用该方案将50万个数字划分为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(); }
内容的提问来源于stack exchange,提问作者Egor Nelyubov

