{"id":1098,"date":"2015-05-05T10:34:46","date_gmt":"2015-05-05T17:34:46","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1098"},"modified":"2015-05-05T10:34:46","modified_gmt":"2015-05-05T17:34:46","slug":"in-place-might-be-less-in-place-than-you-think","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1098","title":{"rendered":"“In-place” might be less in-place than you think"},"content":{"rendered":"

The intuitive view of algorithms that work in-place is that (it sounds obvious) they don’t use any extra space. Canonically in C\/C++ we think of something like reversing an array, or that interview staple, removing spaces from an ASCII string, which we might write as:<\/p>\n

\r\nint remove_spaces(char *s)\r\n{\r\n  char *readptr = s;\r\n  char *writeptr = s;\r\n  while (*readptr)\r\n  {\r\n    if (!isspace(*readptr))\r\n    {\r\n      *writeptr++ = *readptr++;\r\n    }\r\n    else\r\n    {\r\n      ++readptr;\r\n    }\r\n  }\r\n  *writeptr = 0;\r\n  return writeptr - s;\r\n}\r\n<\/pre>\n
But “in-place” has a technical definition that is actually more relaxed than using no extra space, because this intuitive sense is too limiting under a formal analysis. As Wikipedia<\/a> says:<\/p>\n
In computational complexity theory<\/a>, in-place algorithms include all algorithms with O(1) space complexity, the class DSPACE<\/a>(1). This class is very limited; it equals the regular languages<\/a>.[1]<\/a><\/sup> In fact, it does not even include any of the examples listed above.<\/p>\n
For this reason, we also consider algorithms in L, the class of problems requiring O(log n<\/em>) additional space, to be in-place. <\/p><\/blockquote>\n
And in the recent book From Mathematics to Generic Programming<\/a> by Alexander Stepanov (original author of the STL) and Daniel Rose, page 215 offers the definition:<\/p>\n
An algorithm is in-place<\/strong> (also called polylog space<\/strong>) if for an input of length n<\/em> it uses O((log n<\/em>)k<\/em><\/sup>) additional space, where k<\/em> is a constant.<\/p><\/blockquote>\n
(I highly recommend the book, by the way.) If you’re only used to thinking about “in-place” intuitively, you could probably be persuaded that using constant extra space is admissible – after all, one probably has to use a few stack variables – but I think the idea that an algorithm is entitled to call itself “in-place” if it uses logarithmic extra space might be surprising. But that’s the technical definition; an author is entitled to call his or her algorithm “in-place” even though it uses O(log n<\/em>) extra space (and includes the requirement to allocate that space).<\/p>\n","protected":false},"excerpt":{"rendered":"
The intuitive view of algorithms that work in-place is that (it sounds obvious) they don’t use any extra space. Canonically in C\/C++ we think of something like reversing an array, or that interview staple, removing spaces from an ASCII string, which we might write as: int remove_spaces(char *s) { char…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-1098","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1098","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1098"}],"version-history":[{"count":1,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1098\/revisions"}],"predecessor-version":[{"id":1099,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1098\/revisions\/1099"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1098"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1098"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1098"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}