The discussion of "radix partition trees" and "radix partition sort" has been going on for a while now, and I guess it's time to display my ignorance. glen herrmannsfeldt's comments in http://www.garlic.com/~lynn/2002q.html#10 below exactly match my notion of a radix sort. See http://en.wikipedia.org/wiki/Radix_sort for a description of LSD (least significant digit) radix sort. Very fast for short keys.
Googling "radix partition tree" finds a good result at (watch the break) http://delivery.acm.org/10.1145/330000/322146/p457-strong.pdf?key1=322146&key2=7165110021&coll=GUIDE&dl=GUIDE&CFID=11867738&CFTOKEN=24654762 from which the following is extracted: ---------------------- The radix partition tree is a binary tree of pointers set up to branch on bit values of the key rather than key comparisons. Radix partition trees can support the function NEXT HIGHER KEY by left to right tree traversal (as in B-trees), and they can support the function IS A PREFIX OF much more rapidly than any of the strategies we have studied. A study of radix partition tree strategies of[10] or Patrician strategies as presented in [3] is beyond the scope of this paper. However, under our uniformity assumptions, the radix partition tree is no faster and can be considerably slower than a full Binary Search (section size 1), which is in turn no faster than optimal Binary Search. ---------------------- Unfortunately, this seems to have little to do with sorts performed using CFC and UPT. In Knuth's terms, these instructions implement a loser tournament sort using a complete binary tree. The codeword created by CFC is a representation of the offset at which the comparison of two keys fails. The radix (2) of the keys has nothing to do with the result. The UPT instruction "percolates" an appropriate key upward - by comparing codewords - to the root of the tree where it becomes the "winner" of that round. The advantage is that costly key comparisons are reduced. So, if anyone can tell me how the term "radix partition" applies this process, I'll be really, really grateful. Keep in mind that I'm NOT arguing that it doesn't apply, I'm just trying to understand it. Thanks! Michael Stack At 07:18 PM 1/11/2008, you wrote: >The following message is a courtesy copy of an article >that has been posted to bit.listserv.ibm-main as well. > >[EMAIL PROTECTED] (W. Kevin Kelley) writes: >> I see that I screwed up and I owe Luther an apology. It should >> read "...tightest assembly language programs.." There were few problems with >> Luther's program (other than figuring out how they worked!). > >re: >http://www.garlic.com/~lynn/2008.html#65 Radix Partition Trees > > >a few old posts mentioning luther: >http://www.garlic.com/~lynn/98.html#19 S/360 operating systems geneaology >http://www.garlic.com/~lynn/98.html#20 Reviving the OS/360 thread (Questions >about OS/360) >http://www.garlic.com/~lynn/2001.html#2 A new "Remember when?" period >happening right now >http://www.garlic.com/~lynn/2001d.html#28 Very CISC Instuctions (Was: why the >machine word size ...) >http://www.garlic.com/~lynn/2001h.html#73 Most complex instructions >http://www.garlic.com/~lynn/2002.html#14 index searching >http://www.garlic.com/~lynn/2002d.html#18 Mainframers: Take back the light >(spotlight, that is) >http://www.garlic.com/~lynn/2002q.html#10 radix sort >http://www.garlic.com/~lynn/2003e.html#80 "Super-Cheap" Supercomputing >http://www.garlic.com/~lynn/2003i.html#58 assembler performance superiority: a >given >http://www.garlic.com/~lynn/2003i.html#83 A Dark Day >http://www.garlic.com/~lynn/2004l.html#10 Complex Instructions >http://www.garlic.com/~lynn/2005c.html#35 [Lit.] Buffer overruns >http://www.garlic.com/~lynn/2005c.html#38 [Lit.] Buffer overruns >http://www.garlic.com/~lynn/2005e.html#37 Where should the type information be? >http://www.garlic.com/~lynn/2007l.html#57 How would a relational operating >system look like? >http://www.garlic.com/~lynn/2007o.html#55 mainframe performance, was Is a RISC >chip more expensive? >http://www.garlic.com/~lynn/2007u.html#18 Folklore references to CP67 at >Lincoln Labs >http://www.garlic.com/~lynn/2008.html#68 Computer Science Education: Where Are >the Software Engineers of Tomorrow? > >---------------------------------------------------------------------- >For IBM-MAIN subscribe / signoff / archive access instructions, >send email to [EMAIL PROTECTED] with the message: GET IBM-MAIN INFO >Search the archives at http://bama.ua.edu/archives/ibm-main.html ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to [EMAIL PROTECTED] with the message: GET IBM-MAIN INFO Search the archives at http://bama.ua.edu/archives/ibm-main.html
