Path: csiph.com!x330-a1.tempe.blueboxinc.net!feeder3.hal-mli.net!nx02.iad01.newshosting.com!newshosting.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; b=cRrRonSwl645j831CoJc9H78TwvstPbExc2RrRBy7vvemUN+TivNXjEUXMF8DpgDch GOpWaTr55SkoY8y6OmV5zqumDMjhklxJH2i7SpRaIRjQO1qcnE/F4EEfA0whepPC0Qgo 3N0Mz7WeCjpTwqbbM35ZFWYJTL/EIvDO9/Mpw=
MIME-Version: 1.0
In-Reply-To: <5b73ae60-506f-45e4-a82c-e59571252d47@w4g2000yqm.googlegroups.com>
References: <5b73ae60-506f-45e4-a82c-e59571252d47@w4g2000yqm.googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 20 Jun 2011 13:59:57 -0600
Subject: Re: Is there any advantage or disadvantage to using sets over list comps to ensure a list of unique entries?
To: deathweaselx86 <deathweasel@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.191.1308600028.1164.python-list@python.org>
Lines: 33
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8028

On Mon, Jun 20, 2011 at 1:43 PM, deathweaselx86 <deathweasel@gmail.com> wrote:
> Howdy guys, I am new.
>
> I've been converting lists to sets, then back to lists again to get
> unique lists.
> e.g
>
> Python 2.5.2 (r252:60911, Jan 20 2010, 21:48:48)
> [GCC 4.2.4 (Ubuntu 4.2.4-1ubuntu3)] on linux2
> Type "help", "copyright", "credits" or "license" for more information.
>>>> foo = ['1','2','3']
>>>> bar = ['2','5']
>>>> foo.extend(bar)
>>>> foo = list(set(foo))
>>>> foo
> ['1', '3', '2', '5']
>
> I used to use list comps to do this instead.
>>>> foo = ['1','2','3']
>>>> bar = ['2','5']
>>>> foo.extend([a for a in bar if a not in foo])
>>>> foo
> ['1', '2', '3', '5']
>
> A very long time ago, we all used dictionaries, but I'm not interested
> in that ever again. ;-)
> Is there any performance hit to using one of these methods over the
> other for rather large lists?

Yes.  In the second approach, "if a not in foo" is O(n) if foo is a
list, and since you're doing it m times, that's O(n * m).

The first approach is merely O(n + m).