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: 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: <52f80bca$0$29972$c3e8da3$5496439d@news.astraweb.com> <9671c418-cde8-4857-85ec-52380f8390eb@googlegroups.com> <433934582413720306.205290sturla.molden-gmail.com@news.gmane.org> <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 Cc: "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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: 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 On Tue, Feb 11, 2014 at 2:03 AM, Sturla Molden wrote: > Chris Angelico 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).