Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #65745 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 04:13 -0800
    Re: Sort one sequence by O(n) in time and O(1) in space Asaf Las <roegltd@gmail.com> - 2014-02-09 04:29 -0800
    Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-09 23:39 +1100
      Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:09 -0800
        Re: Sort one sequence by O(n) in time and O(1) in space Dave Angel <davea@davea.name> - 2014-02-09 22:00 -0500
    Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 13:41 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 14:30 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Ni Wesley <nispray@gmail.com> - 2014-02-09 22:40 +0800
    Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 10:05 -0500
      Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 23:14 +0000
        Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 19:15 -0500
        Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:26 -0800
          Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 10:20 +0000
            Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve@pearwood.info> - 2014-02-11 05:20 +0000
              Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-12 11:56 +1300
            Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
            Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
          Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-10 21:37 +1100
          Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 15:03 +0000
          Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:23 +1100
          Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 15:45 +0000
          Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:52 +1100
            Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-11 13:19 +1300
          Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 16:41 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 15:48 +0000
      Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:07 -0800
    Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 21:31 +0000

Page 2 of 2 — ← Prev page 1 [2]

#65827

On 10 February 2014 15:03, Sturla Molden <sturla.molden@gmail.com> wrote:
> Chris Angelico <rosuav@gmail.com> wrote:
>
>> That's assuming it really is a sort operation. The problem description
>> isn't entirely clear on this point, but if it's actually a zip, then
>> it can definitely be done in O(n).
>
> Ah, I didn't read it carefully enough. :-)
>
> Granted, a zip can be done in O(n) time and O(1) memory using a generator,
> which by the way is what itertools.izip does.

Yes but turning the generator into a list takes O(N) storage (for the
new list!). The OP wants to rearrange a list in-place.

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).

The way to do this is to find the cycles of data movement i.e. the
sets of indices for which a permutation occurs. If you know the size
of the input then you can find these once and hard-code them.
Otherwise you need an algorithm that finds each cycle exactly once
using O(1) storage which is definitely not trivial.

You can see the top-level code that fftw uses for this here (I think
this code is very hard to follow without prior experience of their
code base - I certainly don't understand it):
https://github.com/FFTW/fftw3/blob/master/rdft/vrank3-transpose.c#L159

I'm not even sure if that really is O(1) storage though: it may be
something like O(MN/gcd(M, N)).

This page describes the general problem

    http://en.wikipedia.org/wiki/In-place_matrix_transposition

and mentions the existence of "more complicated" algorithms that can
use O(N+M) or O(log(MN)) storage.

So I don't think an O(1) storage O(N) operations solution exists for
the general M*N case although it may be possible for the
specialisation to 2*M. (I haven't tried this but if you're interested
see what cycles come up for different input sizes and whether there's
a pattern that can be predicted using O(1) storage).


Oscar

[toc] | [prev] | [next] | [standalone]

#65828

On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin
<oscar.j.benjamin@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!

ChrisA

[toc] | [prev] | [next] | [standalone]

#65852

Chris Angelico wrote:
> mylist = reorder_generator(mylist)
> 
> You can iterate over it, but can't index it. But hey, it complies with
> the space/time requirements!

Rather than a generator, you could use a view object
that rearranges the indices when you access an element.
That would comply with the space/time requirements
and be indexable as well.

Actually it would do better than meet the requirements,
since in a sense it would be O(1) in both space and time!

-- 
Greg

[toc] | [prev] | [next] | [standalone]

#65831

On 10 February 2014 15:52, Chris Angelico <rosuav@gmail.com> wrote:
> On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin
> <oscar.j.benjamin@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

[toc] | [prev] | [next] | [standalone]

#65767

[Multipart message — attachments visible in raw view] — view raw

Please don't top-post.

On Feb 9, 2014 2:40 PM, "Ni Wesley" <nispray@gmail.com> wrote:
>
> Yes, with no new list, otherwise, space won't to be O(1)

Did you read the link I posted:

>> http://en.wikipedia.org/wiki/In-place_matrix_transposition

Oscar

[toc] | [prev] | [next] | [standalone]

#65792

在 2014年2月9日星期日UTC+8下午11时48分17秒，Oscar Benjamin写道：
> Please don't top-post.
> 
> On Feb 9, 2014 2:40 PM, "Ni Wesley" <nis...@gmail.com> wrote:
> 
> >
> 
> > Yes, with no new list, otherwise, space won't to be O(1)
> 
> Did you read the link I posted:
> 
> >> http://en.wikipedia.org/wiki/In-place_matrix_transposition
> 
> 
> Oscar

Sorry getting a network problem these two days.
I am reading :-)

[toc] | [prev] | [next] | [standalone]

#65780

On Sun, 09 Feb 2014 04:13:50 -0800, Wesley wrote:

> Hi guys,
>    Here is one question related to algorithm.
> Details here:
> 
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx
> always exist in pair. So, now, how to change the sequence to
> a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).


Time complexity O(n) implies that you can iterate over the list at most a 
constant number of times. Space complexity O(1) implies that you can only 
use a small, constant amount of extra space, which means that you have to 
modify the input sequence in place.

This is a kind of shuffle. Imagine you pull out all the spades ♠ and 
hearts ♡ from a deck of cards, and sort them individually:

cards = ['A♠', '2♠', '3♠', '4♠',  ... 'K♠', 
         'A♡', '2♡', '3♡', '4♡',  ... 'K♡']

You want to move the cards so that you end up with the spades and hearts 
interleaved:

cards = ['A♠', 'A♡', '2♠', '2♡', '3♠', '3♡', 
         '4♠', '4♡', ... 'K♠', 'K♡']


This is called a "riffle shuffle" or "Faro shuffle", and there are two 
kinds, an in-shuffle and an out-shuffle, which differ in which card ends 
up on top. The obvious way to do it is to split the deck down the middle 
into two sets of cards, then riffle them together, one card from the left 
hand following by one card from the right (or visa versa):

left = cards[:len(cards)//2]
right = cards[len(cards)//2:]
cards = []
for l, r in zip(left, right):
    cards.append(l)
    cards.append(r)


but this doesn't use constant space, since it uses extra space 
proportional to N. Since this sounds like homework, I'm not going to tell 
you how to do this using only constant space, but it may help if you 
actually sit down with a set of cards, lay them out in order, and see how 
you might do it by hand.



-- 
Steven

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.python

csiph-web