On 10 February 2014 15:52, Chris Angelico <ros...@gmail.com> wrote: > On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin > <oscar.j.benja...@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 -- https://mail.python.org/mailman/listinfo/python-list