“In-place” might be less in-place than you think

int remove_spaces(char *s)
{
  char *readptr = s;
  char *writeptr = s;
  while (*readptr)
  {
    if (!isspace(*readptr))
    {
      *writeptr++ = *readptr++;
    }
    else
    {
      ++readptr;
    }
  }
  *writeptr = 0;
  return writeptr - s;
}

3 comments

1. That seems a little dishonest!

   It’s ironic that these terms (and big O notation) seem to try to abstract away details of the machine you are working on to get to some core values or truths to be able to compare algorithms. They do end up making assumption about the type of machine you are working on though. In this case, that small amounts of memory is free, which may not be the case if you are on some exotic device.

   This sort of stuff is a reason I’ve never really been into big O notation… it is helpful as a general guide, but it doesn’t account for cache coherency, disk access times, etc, so an algorithm could look fine on paper, but be terrible when implemented.

   I’m sure that’s not a popular opinion though and might make me look ignorant to people who disagree (:

2. I think an example might help build the intuition around why we want “in-place” to mean “logarithmic extra space”. Consider an algorithm that finds an element in a forward range (not sure whether this code will be readable):

   template
   IteratorType find(R seq, ValueType elem) {
     using I = IteratorType(R);
   
     I it = begin(seq);
     while (it != end(seq)) {
       if (*it == elem) return it;
       ++it;
     }
   
     return it;
   
   }
   

   Now, let’s assume that seq has $N-1$ different elements in it. Our iterator it can take on $N$ different possible values, then (it can point to every element in the seq, as well as a one-past-the-end value). This means the iterator will occupy $\log_2(N)$ bits of memory. The in-place definition captures the intuition that we can store some fixed number of iterators (i.e., $\log_2(N)^k$ bits of memory).

   It may seem like we could pick $N$ large enough so seq occupies all addressable memory—if we could never have a seq larger than available memory, $N$ would be constant, so $\log_2(N)^k$ would also be constant. This is very tempting, but our find algorithm says nothing about every element of seq needing to live in memory at the same time. On a 32-bit machine, this limits the amount of information we can process as a sequence to 4 GB—we can’t even search through a DVD, which can store and perform random access on just under 5 GB. Often it’s to pretend $N$ is constant, but sometimes it’s not. The caller will know, but the algorithm will not.

   To address the above comment, one of the great strengths of Generic Programming in this way is that you are abstracting away algorithms in a way that you can still reason about what the machine is actually doing. At the caller side, for instance, we probably have the information whether the elements of seq live in memory or not, and thus whether I can be stored without heap allocation. For instance, if seq of type R is really a std::vector, all elements live in memory, and so I—that is, std::vector::iterator—can have constant size, at least sizeof(std::size_t). Thinking of “in-place” as “can allocate a fixed number of iterators”, we can know the algorithm doesn’t need to go off to the heap to allocate anything, and all iterators can be stored on the stack (thread-locally, so we don’t have to worry about cache-coherency, and they will probably be hot in cache as well). On the other hand, if we make a range dvd::seeker, we can choose the size of the iterator to be 64-bits, a double word. Arithmetic may be slower, but we haven’t lost correctness. In short, our find works on any type imaginable, and is just as efficient as if you had hand-written it for that type. (And, if we have a better way to write the algorithm itself, we can specialize find.)

   Hope this helps readers get a little intuition for why we call something “in-place” when it doesn’t take a constant amount of extra space.

   Cheers,

3. This definition of in-place allows Quicksort to be considered in-place. The maximum depth of the recursion stack for Quicksort is O(log N).

This site uses Akismet to reduce spam. Learn how your comment data is processed.