3
$\begingroup$

"In-place" is a seemingly informal adjective used to describe algorithms. Does it have a precise definition?

To further clarify the discussion, what models of computation can we say are in-place? We can probably say whether a specific C program running on a specific machine is in-place. Can we say whether a C program is in-place, independent of its implementation? Can we say whether a Turing machine is in-place? Can we identify in-place algorithms with known complexity classes?

|cite|improve this question
$\endgroup$
  • $\begingroup$ A C program is fairly low-level, and is close to its implementation from a theoretical standpoint. Now a Haskell program would be a different story. $\endgroup$ – Suresh Venkat Jan 30 '14 at 16:26
  • $\begingroup$ So what you are suggesting is that whether a program is in-place might not be completely captured by a high-level specification of its underlying algorithm, e.g. its Haskell code? $\endgroup$ – Siddharth Jan 31 '14 at 8:05
  • 1
    $\begingroup$ I think what I'm saying is that we can talk about an algorithm being in-place, but not really about a program. $\endgroup$ – Suresh Venkat Jan 31 '14 at 18:39
5
$\begingroup$

An in-place algorithm assumes its input is given in working memory, and it cannot use any other working memory than what the input initially occupies. We can consider any fixed amount of working memory to be part of the algorithm itself.

For example,

  1. finite automata are in-place;
  2. pushdown automata are not;
  3. linear bounded automata are;
  4. Turing machines are not.

A formalization of the notion can be a random-access machine with limited memory.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I don't understand. What's wrong with it? $\endgroup$ – brandjon Jan 31 '14 at 20:32
1
$\begingroup$

In place means you overwrite the memory location of the input with the output, and you are allowed to cannibalize this buffer for use in the computation.

void* in_place(void* ptr, int buffer_size) //If you prefer C notation

What goes in that function is arbitrary. In practice this is both a blessing and a curse. You have the freedom to recycle the buffer, but you are burdened by losing bits of the input as you overwrite them with the output.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The function isn't quite arbitrary: it doesn't use any additional memory (beyond a fixed amount). $\endgroup$ – reinierpost Jan 30 '14 at 16:58
  • 1
    $\begingroup$ Try applying a permutation in place. You can't as far we know without at least O(log n) extra space. cstheory.stackexchange.com/questions/6711/… $\endgroup$ – Chad Brewbaker Jan 30 '14 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.