Fast deterministic approximate and exact parallel sorting
Fast deterministic approximate and exact parallel sorting
复制标题
快速确定性近似和精确并行排序
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
R. Raman
中科院分区：
文献类型：
--
作者：
T. Hagerup;R. Raman
填充排序要求n个输入键在一个位置略多于n的数组中按排序顺序输出，未使用的位置用一个特殊的空值填充。我们证明了具有h个处理器的确定性CRCW PRAM可以在~（log log k）s内对n个密钥进行填充排序。2°（* 0 g”-10 g *“+1）时间，对于任意k，其中4 s k s n，这接近于Q（log n/log k）的已知下界。因此，我们能够提高以前的最好的结果确定性亚对数标准排序。其他结果包括确定性算法与最佳加速近似前缀求和和填充排序独立均匀分布的随机变量。在第一种情况下，运行时间是O（（log log n）4/log log log n），在第二种情况下，平均运行时间是O（（log log n）4 /log（4）n）。
Padded sorting requires n input keys to be output in sorted order in an array with slightly more than n locations, unused locations being filled with a special null value. We show that a deterministic CRCW PRAM with h processors can padded-sort n keys in ~(log log k)s . 2°(*0g” ‘-lOg* ‘+1) time, for any k with 4 s k s n, which is close to a known lower bound of Q(log n/log k). As a consequence, we are able to improve the best previous result on deterministic sublogarithmic standard sorting. Other results include deterministic algorithms with optimal speedup for approximate prefix summation and for padded-sorting independent uniformly distributed random variables. In the first case the running time is O((log log n)4/log log log n), and in the second case the average running time is O((log log log n)4 /log(4) n).