[R] Zero Index Origin?

[Peter Wolf]

Sorting is a wonderful topic! Especially because you can discuss different
fundamental ideas like brute force, divide and conquer, and questions of
efficiency, tradeoffs of space and time, etc. In this way  sort.6  is 
one of a
sequence of sorting algorithms. Each of them demonstrates a specific point
for teaching purposes. You are right: in sort.6 a[0] plays the role of a 
sentinel.
So the main points are:

  1) What is the new idea found in sort.6 (compared to sort.5 -- a 
solution without sentinel)?
  2) Are there other ideas for improvements concerning space and time 
(this leads to sort.7, etc.)?
  3) What about readability: what is the best notation for human readers?
  4) What should be considered and changed in the light of a specific 
computer language?

Your remarks show that often an example initiates a desire  to start  a 
discussion
of one of the four questions. That's what we want to have in the 
classroom, too.
In case of sort.6 my situation was that I have a lot of nice slides with 
algorithms
in pseudo code and I wanted to get them running for demonstration. For APL
is a little bit out of fashion I used my favorite computer language: R.

Thank you for your comments -- which increase the set of R programming 
pearls
and will enrich the discussion in my lectures

Peter Wolf


Richard A. O'Keefe wrote:

>I asked where index origin 0 would help.
>(I am familiar with Dijkstra's article on why counting should start
>at 0 and agree whole-heartedly.  I am also convinced that "kicking
>against the goads" is not helpful.)
>
>Peter Wolf <s-plus at wiwi.uni-bielefeld.de>
>has provided two examples.
>
>(1) Converting pseudo-code which assumes index origin 0.
>
>    I've done this myself, although not yet in R.  I've also done it
>    the other way, converting index origin 1 code to C.
>
>    A good method, I've found, is to to start by converting to
>    index-free form.  This applies whatever the source and target
>    languages are.
>
>(2) A sorting algorithm.
>
>    sort.6 <- function (a) {
>       n <- length(a)
>       adapt <- function (i) {i+1}
>       a <- c(0,a)
>       for (i in 2:n) {
>	  j <- i-1
>	  a[adapt(0)] <- a[adapt(i)]
>	  while (a[adapt(j)] > a[adapt(0)]) {
>	     a[adapt(j+1)] <- a[adapt(j)]
>	     j <- j-1
>	  }
>	  a[adapt(j+1)] <- a[adapt(0)]
>       }
>       a[-1]
>    }
>
>    The really interesting thing here is that this basically is an
>    index origin 1 algorithm.  The original array and the final result
>    start at 1, not 0, and position 0 is used for a "sentinel".
>
>    Let's convert it to 1-origin.  I'll skip the details of how I
>    did it because that's not the point I want to make.
>
>    sort.VI <- function (a) {
>       a <- c(0, a)
>       for (i in 3:length(a)) {
>	  j <- i-1
>	  a[1] <- a[i]
>	  while (a[j] > a[1]) {
>	     a[j+1] <- a[j]
>	     j <- j-1
>	  }
>	  a[j+1] <- a[1]
>       }
>       a[-1]
>    }
>
>    What do you get if you move up to index-free form?
>
>    sort.six <- function (a) {
>	s <- c()
>	for (x in a) {
>	    f <- s <= x
>	    s <- c(s[f], x, s[!f])    # insert x stably into s
>	}
>	s
>    }
>
>    It's clear that sort.six is shorter, clearer, and easier to get
>    right than sort.VI.  But how much do we have to pay for this?
>    How much efficiency do we lose?
>
>    > a <- runif(400)
>    > system.time(sort.VI(a))
>    [1]  3.64  0.02 12.56  0.00  0.00
>    > system.time(sort.six(a))
>    [1] 0.15 0.01 0.16 0.00 0.00
>
>    We don't lose any efficiency at all.  We gain, considerably.
>    (Not as much as we'd gain by using the built-in sort(), of course.)
>
>I expect that this will happen fairly often:  rewriting the code to be
>index-free will *usually* make it shorter and clearer, and will *always*
>make it easier to adapt to a language with a different index origin.
>When the target language is R or S, the result is likely to be faster
>than a direct conversion.
>  
>
---------------------------------------------------------

Gabor Grothendieck wrote:

......

and Prof Brian Ripley wrote:

: since you can shift whole blocks at a time rather than use a while loop.

In words the algorithm runs from 2 through length(a) inserting
the current element into the subarray to its left, so to follow up
Prof Riley's suggestion to replace the while loop with code that
copies whole blocks at a time we have the following which does
not seem to suffer from lack of 0-origin and is clearer than
the double loop approach:

sort.6a <- function(a) {
	for(i in 2:length(a)){ # insert a[i] into subvector to left of it
		left <- a[1:(i-1)]
		sel <- left < a[i]
		a[1:i] <- c( left[sel], a[i], left[!sel] )
	}
	a
}

-----------------------------------------

Prof Brian Ripley wrote:

I think that is an excellent illustration of my point:


>If you are writing code that works with single elements, you are
>probably a lot better off writing C code to link into R (and C is
>0-based ...).
>  
>

but even in R it is not following


>However, the R thinking is to work with whole objects (vectors, arrays,
>lists ...) and you rather rarely need to know what numbers are in an 
>index vector. 
>  
>

since you can shift whole blocks at a time rather than use a while loop.