In-place algorithm

In computer science, an in-place algorithm is an algorithm which transforms a data structure using a minimal, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes (although sometimes the output is simply of constant size). An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

Examples

Suppose we want to reverse an array of n items. One simple way to do this is:

function reverse(a[0..n]) allocate b[0..n] for i from 0 to n b[n - i] = a[i] return b Unfortunately, this requires O(n) space to create the array b, and allocation is often a slow operation. If we no longer need a, we can instead overwrite it with its own reversal using this in-place algorithm:

function reverse-in-place(a[0..n]) for i from 0 to floor(n/2) swap(a[i], a[n-i]) As another example, there are a number of sorting algorithms that can rearrange arrays into sorted order in-place, including:

Quicksort is commonly described as an in-place algorithm, but is not in fact one. Most implementations require O(log n) space to support its divide-and-conquer recursion.

Most selection algorithms are also in-place, although some considerably rearrange the input
array in the process of finding the final, constant-sized result.

In computational complexity

In computational complexity theory, in-place algorithms include all algorithms with O(1) space complexity, the class DSPACE(1). This class is very limited; it equals the regular languages¹. In fact, it does not even include any of the examples listed above.

For this reason, we also consider algorithms in L, the class of problems requiring O(log n) additional space, to be in-place. Although this seems to contradict our earlier definition, we have to consider that in the abstract world our input can be arbitrarily large. On a real computer, a pointer requires only a small fixed amount of space, because the amount of physical memory is limited, but in general O(log n) bits are required to specify an index into a list of size n.

Does this mean quicksort is in-place after all? Not at all — technically, it requires O(log² n) space, since each of its O(log n) stack frames contains a constant number of pointers (each of size O(log n)).

Identifying the in-place algorithms with L has some interesting implications; for example, it means that there is a (rather complex) in-place algorithm to determine whether a path exists between two nodes in an undirected graph², a problem that requires O(n) extra space using typical algorithms such as depth-first search (a visited bit for each node). This in turn yields in-place algorithms for problems such as determinining if a graph is bipartite or testing whether two graphs have the same number of connected componentss. See SL for more information.

In functional programming

Functional programming languages often discourage or don't support explicit in-place algorithms that overwrite data, since this is a type of side effect; instead, they only allow new data to be constructed. However, good functional language compilers will often recognize when an object very similar to an existing one is created and then the old one thrown away, and will optimize this into a simple mutation "under-the-hood".

Note that it is possible in principle to carefully construct in-place algorithms that don't modify data (unless the data is no longer being used), but this is rarely done in practice. See purely functional data structures.

References

Maciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. Structure in Complexity Theory Conference, pp.64-78. 1994.

Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94.

Footnotes

1. Liśkiewicz and Reischuk, pg.3, Theorem 2.

2. Reingold.

NodeWorks boosts web surfing!

Page Returned in 0.272 seconds - HTML Compressed 67.2%

This article is from Wikipedia. All text is available
under the terms of the GNU Free Documentation License.