«

> On Behalf Of John Nagle
> What's the cheapest way to test for an empty dictionary in Python?
>
> if len(dict.keys() > 0) :
>
> is expensive for large dictionaries, and makes loops O(N^2).

I believe that the following is fairly efficient:

>>> def dict_is_empty(D):
for k in D:
return False
return True

>>> dict_is_empty(dict(a=1))
False
>>> dict_is_empty({})
True

Regards,
Ryan Ginstrom

On Sun, 23 Mar 2008 08:53:02 -0700
John Nagle <> wrote:
> What's the cheapest way to test for an empty dictionary in Python?
>
> if len(dict.keys() > 0) :
>
> is expensive for large dictionaries, and makes loops O(N^2).

Try this:

if dict:

It should be faster as it only checks whether or not there are
any members and does not run keys() or len() on the dictionary. Of
course, you should test it.

--
D'Arcy J.M. Cain <> | Democracy is three wolves
http://www.druid.net/darcy/ | and a sheep voting on
+1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.

What's the cheapest way to test for an empty dictionary in Python?

if len(dict.keys() > 0) :

is expensive for large dictionaries, and makes loops O(N^2).

John Nagle

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John Nagle wrote:
> What's the cheapest way to test for an empty dictionary in Python?
>
> if len(dict.keys() > 0) :
>
> is expensive for large dictionaries, and makes loops O(N^2).
>
> John Nagle

if dict:
...



- --
- ---[Office 68.7F]--[Outside 42.9F]--[Server 100.4F]--[Coaster 68.0F]---
- ---[ KLAHOWYA WSF (366773110) @ 47 31.2076 -122 27.2249 ]---
Software, Linux, Microcontrollers http://www.brianlane.com
AIS Parser SDK http://www.aisparser.com
Movie Landmarks Search Engine http://www.movielandmarks.com

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)
Comment: Remember Lexington Green!

iD8DBQFH5nz/Iftj/pcSws0RAnnMAJoDX9P0cK+RshuvuRRfkyJ4CPwqxACeMWkF
pq7AKr/qzVWyVat0QiTtUfo=
=bpei
-----END PGP SIGNATURE-----

On Mar 23, 3:53 pm, John Nagle <na...@animats.com> wrote:
> What's the cheapest way to test for an empty dictionary in Python?
>
> if len(dict.keys() > 0) :
>
> is expensive for large dictionaries, and makes loops O(N^2).
>
> John Nagle

As others have stated, if <container object>: is false for built-in
container types such as dicts, lists, sets, tuples,...
Its nice to make any of your owh container types follow the same
convention too.

- Paddy.

John Nagle <> writes:
> What's the cheapest way to test for an empty dictionary in Python?
>
> if len(dict.keys() > 0) :

I like to think len(dict) is constant time but I haven't checked the code.
Same for bool(dict) (which is what you get when you run "if dict: ...").

On Mar 23, 4:14 pm, Paddy <paddy3...@googlemail.com> wrote:
> On Mar 23, 3:53 pm, John Nagle <na...@animats.com> wrote:
>
> > What's the cheapest way to test for an empty dictionary in Python?
>
> > if len(dict.keys() > 0) :
>
> > is expensive for large dictionaries, and makes loops O(N^2).
>
> > John Nagle
>
> As others have stated, if <container object>: is false for built-in
> container types such as dicts, lists, sets, tuples,...
> Its nice to make any of your own container types follow the same
> convention too.
>
> - Paddy.

I missed out *empty* didn't I.
Its false for empty container types.

- Paddy.

Brian Lane wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> John Nagle wrote:
>> What's the cheapest way to test for an empty dictionary in Python?
>>
>> if len(dict.keys()) :
>>
>> is expensive for large dictionaries, and makes loops O(N^2).
>>
>> John Nagle
>
> if dict:

Cute.

I'd already figured out that

len(dict)

works, which is probably better than

len(dict.keys() > 0

which requires creating a list.

John Nagle

On Mar 23, 5:45*pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> John Nagle <na...@animats.com> writes:
> > * *What's the cheapest way to test for an empty dictionary in Python?
>
> > * *if len(dict.keys() > 0) :
>
> I like to think len(dict) is constant time but I haven't checked the code.
> Same for bool(dict) (which is what you get when you run "if dict: ...").

It has to be constant time as it is a lower bound for inserts (which
average to constant time).

--
Arnaud

On Mar 24, 2:53 am, John Nagle <na...@animats.com> wrote:
> What's the cheapest way to test for an empty dictionary in Python?
>
> if len(dict.keys() > 0) :

TypeError: object of type 'bool' has no len()

I presume you meant
if len(dict.keys()) > 0:

>
> is expensive for large dictionaries, and makes loops O(N^2).

I don't understand "makes loops O(N^2)" ... what I see in the
dict_keys function in Objects/dictobject.c is that it makes one linear
pass through its table, ignoring unused and formerly-used slots; seems
like O(N) where N is the size of the table. Where did you get O(N^2)
from?