MPI-I-91-106
Fast parallel space allocation, estimation an integer sorting
Hagerup, Torben
June 1991, 28 pages.
.
Status: available - back from printing
We show that each of the following problems can be solved
fast and with optimal speedup with high probability on a
randomized CRCW PRAM using
$O(n)$ space:
Space allocation: Given $n$ nonnegative integers
$x_1,\ldots,x_n$, allocate $n$ blocks of consecutive
memory cells of sizes $x_1,\ldots,x_n$ from a base
segment of $O(\sum_{i=1}^n x_i)$ consecutive
memory cells;
Estimation: Given $n$ integers %$x_1,\ldots,x_n$
in the range $1\Ttwodots n$, compute ``good'' estimates
of the number of occurrences of each value
in the range $1\Ttwodots n$;
Integer chain-sorting: Given $n$ integers $x_1,\ldots,x_n$
in the range $1\Ttwodots n$, construct a linked list
containing the integers $1,\ldots,n$ such that for all
$i,j\in\{1,\ldots,n\}$, if $i$ precedes $j$ in the
list, then $x_i\le x_j$.
\noindent
The running times achieved are $O(\Tlogstar n)$ for
problem (1) and $O((\Tlogstar n)^2)$ for
problems (2) and~(3).
Moreover, given slightly superlinear processor
and space bounds, these problems or variations
of them can be solved in
constant expected time.
-
- Attachement: MPI-I-91-106.pdf (15501 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-106
BibTeX
@TECHREPORT{Hagerup91a,
AUTHOR = {Hagerup, Torben},
TITLE = {Fast parallel space allocation, estimation an integer sorting},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-91-106},
MONTH = {June},
YEAR = {1991},
ISSN = {0946-011X},
}