Changeset 1549

Ignore:
Timestamp:
Oct 22, 2011, 2:04:00 PM (7 years ago)
Message:

Update parlensort doc

File:
1 edited

Legend:

Unmodified
 r1302 \maketitle \section{The Idea} \section{Length-Group Bitstreams} Given streams $S$ and $E$ that mark the starts and ends of Names. ends of Names of length 1, $E_1$, and the stream of ends of Names of greater than length 1, $E_{>1}$, as follows. Here  $n(S)$ is the bitstream next'' operation, shifting the stream forward one position. \begin{eqnarray*} \end{eqnarray*} \section{Parallel Hashing} Given length groups identified as in the previous section, it is possible to perform parallel hash value calculation for names in each group as follows. The first step is to create hash streams. Let $B_0, B_1, \ldots, B_7$ be the {\em basis} bitstreams determined by character stream transposition.   That is, the $k$th basis bitstream $B_k$ consists of the $k$th bit of each character in the source data stream. Then we may compute hash streams by some bitwise logical combination of basis bit streams. For example, the following two hash streams may be useful. \begin{eqnarray*} h_a & = & B_2 \oplus B_4 \oplus B_6 \\ h_b & = & B_3 \oplus B_5 \oplus B_7 \\ \end{eqnarray*} \section{Follow-up} lengths?   This avoids allocation of length-based position arrays, the memory operations of insertion of positions into those arrays, bounds-checking on those arrays and maintaining an auxiliary array of lengths of the each array. arrays and maintaining an auxiliary array of lengths of each array. A further benefit may be from the programming side: the length sorting can