Optimal parallel string algorithms: sorting, merging and computing the minimum
Optimal parallel string algorithms: sorting, merging and computing the minimum
复制标题
最优并行字符串算法：排序、合并和计算最小值
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
T. Hagerup
中科院分区：
文献类型：
--
作者：
T. Hagerup
我们研究字符串的基本比较问题，配备了通常的字典序~g。对于每个问题的研究，我们给出了一个并行算法，是最佳的至少有一个标准，没有最佳算法是以前已知的。具体地说，我们的主要结果是：●两个排序的字符串序列，共包含n个字符，在EREW PRAM上使用O（n）操作可以在O（log n）时间内合并。就运行时间和操作数量而言，这都是最佳的。●一个字符串序列，由n中大小多项式的整数艾德，可以在O（log n/log log n）时间内使用O（n log log n）操作在CRCW PRAM上排序。对于任何多项式数目的处理器，运行时间都是最优的.·包含总共n个字符的字符串序列中的最小字符串可以使用（预期）O（n）操作在（预期）时间内找到，从随机CRC W PRAM上的O（1）到确定性EREW PRAM上的O（log n log log n）。
We study fundamental comparison problems on strings of characters, equipped with the usual lexicographical order~g. For each problem studied, we give a parallel algorithm that is optimal with respect to at least one criterion for which no optimal algorithm was previously known. Specifically, our main results are: ● Two sorted sequences of strings, cent aining altogether n characters, can be merged in O(log n) time using O(n) operations on an EREW PRAM. This is optimal as regards both the runnin g time and the number of operations. ● A sequence of strings, cent -g altogether n characters represent ed by integers of size polynomial in n, can be sorted in O(log n/log log n) time using O(n log log n) operations on a CRCW PRAM. The rurmin g time is opt imal for any polynomial number of processors. ● The minimum string in a sequence of strings containing altogether n characters can be found using (expected) O(n) operations in (expected) time ranging from O(1) on a randomized CRC W PRAM to O(log n log log n) on a deterministic EREW PRAM.