Sort one sequence by O(n) in time and O(1) in space

[Oscar Benjamin]

On 10 February 2014 15:52, Chris Angelico <rosuav at gmail.com> wrote:
> On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin
> <oscar.j.benjamin at gmail.com> wrote:
>> Something like
>>
>>     mylist[:] = reorder_generator(mylist)
>>
>> won't work because the generator would need to access the data
>> non-sequentially (it would need to read elements after they were
>> overwritten).
>
> This would have O(1) space and O(n) time. It's absolutely perfect...
> except that you now don't technically have a list any more:
>
> mylist = reorder_generator(mylist)
>
> You can iterate over it, but can't index it. But hey, it complies with
> the space/time requirements!

That is very likely a practical solution for many problems involving
transposition. Doing this in Python is pretty artificial since a new
list object will likely use a lot less memory than the elements it
contains.

The practical use for such algorithms is in something like C and even
then it's often better to simply iterate in a different order. The
advantage of physically transposing the data is to improve memory
locality but this only makes sense if your transpose algorithm itself
has a good memory access pattern (which is likely impossible with O(1)
storage).


Oscar