论文标题
统一链接列表收缩
Uniform Linked Lists Contraction
论文作者
论文摘要
我们提出了一种链接列表收缩的平行算法（EREW PRAM算法）。我们表明，当我们为合适常数$ c $的尺寸$ n $到尺寸$ n/c $的链接列表时，我们可以将链接的列表包装到3次颜色的常数$ 1 <d \ d \ leq c $的尺寸$ n/d $的数组中。因此，对于一组链接列表，总共$ n $元素和最长列表具有$ l $元素，我们的算法将它们与$ o（n \ log i/p+（\ log log^{（i）N+\ log I）\ log i \ log \ log \ log \ log \ log l+l log l log l log l log l l log l log l log l log l）$ time to $ $ i $ pram，wher $ \ log^{（1）} n = \ log n $和$ \ log^{（t）} n = \ log \ log \ log \ log^{（t-1）n $和$ \ log^*n = \ n = \ min \ {I | \ log^{（i）} n <10 \} $。当$ i $是常数时，我们会得到时间$ o（n/p+\ log^{（i）} n \ log \ log \ log l+\ log l）$。因此，当$ l =ω（\ log^{（c）} n）$对于任何常数$ c $，我们就可以实现$ o（n/p+\ log l）$ time。以前的最佳确定性EREW PRAM算法具有时间$ o（n/p+\ log n）$，而最佳CRCW PRAM算法的时间$ O（n/p+\ log n/\ log n/\ log n/\ log \ log n+\ log l log l）$。 关键字：并行算法，链接列表，链接列表收缩，统一链接列表收缩，EREW PRAM。
We present a parallel algorithm (EREW PRAM algorithm) for linked lists contraction. We show that when we contract a linked list from size $n$ to size $n/c$ for a suitable constant $c$ we can pack the linked list into an array of size $n/d$ for a constant $1 < d\leq c$ in the time of 3 coloring the list. Thus for a set of linked lists with a total of $n$ elements and the longest list has $l$ elements our algorithm contracts them in $O(n\log i/p+(\log^{(i)}n+\log i )\log \log l+ \log l)$ time, for an arbitrary constructible integer $i$, with $p$ processors on the EREW PRAM, where $\log^{(1)} n =\log n$ and $\log^{(t)}n=\log \log^{(t-1)} n$ and $\log^*n=\min \{ i|\log^{(i)} n < 10\}$. When $i$ is a constant we get time $O(n/p+\log^{(i)}n\log \log l+\log l)$. Thus when $l=Ω(\log^{(c)}n)$ for any constant $c$ we achieve $O(n/p+\log l)$ time. The previous best deterministic EREW PRAM algorithm has time $O(n/p+\log n)$ and best CRCW PRAM algorithm has time $O(n/p+\log n/\log \log n+\log l)$. Keywords: Parallel algorithms, linked list, linked list contraction, uniform linked list contraction, EREW PRAM.
