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

Path	csiph.com!usenet.pasdenom.info!news.etla.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<rosuav@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.004
X-Spam-Evidence	'H': 0.99; 'S': 0.00; 'granted,': 0.07; 'assuming': 0.09; 'variant': 0.09; 'cc:addr:python-list': 0.11; 'after,': 0.16; 'ah,': 0.16; 'enough.': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'generator.': 0.16; 'iterating': 0.16; 'itertools': 0.16; 'operation,': 0.16; 'operation.': 0.16; 'subject:Sort': 0.16; 'such,': 0.16; ':-)': 0.16; 'wrote:': 0.18; 'feb': 0.22; 'memory': 0.22; 'cc:addr:python.org': 0.22; '(or': 0.24; 'cc:2**0': 0.24; 'sort': 0.25; 'right.': 0.26; 'header:In-Reply-To:1': 0.27; 'chris': 0.29; 'am,': 0.29; 'raise': 0.29; 'subject:) ': 0.29; 'words': 0.29; 'message-id:@mail.gmail.com': 0.30; 'end,': 0.31; 'quite': 0.32; 'entirely': 0.33; 'subject:time': 0.33; 'problem': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'really': 0.36; 'subject:one': 0.36; 'done': 0.36; "didn't": 0.36; 'list.': 0.37; 'clear': 0.37; 'read': 0.60; 'till': 0.61; 'zip': 0.64; 'carefully': 0.74; 'subject:space': 0.84; 'to:none': 0.92
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type; bh=juu5Tn9s4/+0CQNSLOv8l120Zi1ghIAffu1G0y5u4CU=; b=H4Fk8MTBYHSRt6tg2W8enayO25kBCh4UYgYQDe+rLcJLsfBp/yBl4lQlzRQw8OXJnM ujk8loBeFn8sVfcJOirEMRjp/yQ+G7ILHq8gx2CJbeyU53hfW8XYctJwON9z2pFFjvZU hkVaEfvbysjyJunsRSblDalQFjmpu99sp8TuDukeBcahEghO+3zxqWP54GgzdSHNYG9I FCVXwKBZeJynRDgXqIwSOUNj9Y5/CA8ZuCEuU4zvX4/bmU2iNbFMNoIfTJncYIvPYial LAYCtPhoOhOz2naAGZBzczXNUytsFaB3bqCzELizV1WWLUpggyt5CdetuRtPXAXDdYj0 x9NQ==
MIME-Version	1.0
X-Received	by 10.68.98.3 with SMTP id ee3mr38510713pbb.31.1392045788759; Mon, 10 Feb 2014 07:23:08 -0800 (PST)
In-Reply-To	<2079199387413737237.368296sturla.molden-gmail.com@news.gmane.org>
References	<ae372652-0f1c-4d79-82db-a522eb592579@googlegroups.com> <roy-29BD70.10050209022014@news.panix.com> <52f80bca$0$29972$c3e8da3$5496439d@news.astraweb.com> <9671c418-cde8-4857-85ec-52380f8390eb@googlegroups.com> <433934582413720306.205290sturla.molden-gmail.com@news.gmane.org> <CAPTjJmpOfmZurvceoXcx-J3meLOzKSz7RYvaQ1AXpsW0oBMt2A@mail.gmail.com> <2079199387413737237.368296sturla.molden-gmail.com@news.gmane.org>
Date	Tue, 11 Feb 2014 02:23:08 +1100
Subject	Re: Sort one sequence by O(n) in time and O(1) in space
From	Chris Angelico <rosuav@gmail.com>
Cc	"python-list@python.org" <python-list@python.org>
Content-Type	text/plain; charset=UTF-8
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.6627.1392045798.18130.python-list@python.org> (permalink)
Lines	18
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1392045798 news.xs4all.nl 2923 [2001:888:2000:d::a6]:51377
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:65824

Show key headers only | View raw

On Tue, Feb 11, 2014 at 2:03 AM, 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.

Right. I poked around in itertools but nothing was quite what I was
after, so I ended up writing my own generator. But it's still a zip
operation, and as such, is just a variant form of iterating over the
original list. All I do is follow a pattern other than the Red King's
"Begin at the beginning, go on till you come to the end, then raise
StopIteration" (or words to that effect).

Thread

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

csiph-web