[EMAIL PROTECTED] (Michael Stack) writes: > 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.
re: http://www.garlic.com/~lynn/2008.html#64 Radix Partition Trees http://www.garlic.com/~lynn/2008.html#72 Radix Partition Trees my original comment was "for the fun of it" ... look at the mainframe instructions ... on par with other comments about considering red-black trees, etc. the other comment was with respect to Luther ... who I believe has been involved in both. note a radix partition tree implementation can use bit strings and involve the bit displacement/place that the strings differ ... in such a situation ... rather than doing something like calculating a key for the entry ... take the bit string value itself and create a tree with forks at where there is a bits different. radix as in numerical encoding system: http://en.wikipedia.org/wiki/Radix from above: The highest symbol of a positional numeral system usually has the value one less than the value of the radix of that numeral system. ... snip ... radix as in radix tree: Radix tree: http://en.wikipedia.org/wiki/Radix_tree from above: Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This doesn't seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes. In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons and require many fewer nodes. Hash tables are commonly said to have expected O(1) insertion and deletion times, but this is only true when considering computation of the hash of the key to be a constant time operation. When hashing the key is taken into account, hash tables have expected O(k) insertion and deletion times, but will take longer in the worst-case depending on how collisions are handled. Radix trees have worst-case O(k) insertion and deletion. The successor/predecessor operations of radix trees are also not implemented by hash tables. ... snip ... i.e. rather than treating each bit in a value for tree position ... deal only with the location where there are bit differences ... difference displacements that are shorter (nearer the front of the string) will appear higher in the tree. ---------------------------------------------------------------------- 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
