Testing for an empty dictionary in Python

**Ryan Ginstrom** · Mar 23 '08, 03:55 PM

RE: Testing for an empty dictionary in Python

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

**D'Arcy J.M. Cain** · Mar 23 '08, 03:55 PM

Re: Testing for an empty dictionary in Python

On Sun, 23 Mar 2008 08:53:02 -0700
John Nagle <nagle@animats. comwrote:

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 <darcy@druid.ne t | 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.

**Brian Lane** · Mar 23 '08, 03:55 PM

Re: Testing for an empty dictionary in Python

-----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, Microcontroller s 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/pcSws0RAnnMAJoD X9P0cK+RshuvuRR fkyJ4CPwqxACeMW kF
pq7AKr/qzVWyVat0QiTtUf o=
=bpei
-----END PGP SIGNATURE-----

**Paddy** · Mar 23 '08, 04:15 PM

Re: Testing for an empty dictionary in Python

On Mar 23, 3:53 pm, John Nagle <na...@animats. comwrote:

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.

**Paul Rubin** · Mar 23 '08, 05:55 PM

Re: Testing for an empty dictionary in Python

John Nagle <nagle@animats. comwrites:

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

**Paddy** · Mar 23 '08, 06:05 PM

Re: Testing for an empty dictionary in Python

On Mar 23, 4:14 pm, Paddy <paddy3...@goog lemail.comwrote :

On Mar 23, 3:53 pm, John Nagle <na...@animats. comwrote:
>

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.

**John Nagle** · Mar 23 '08, 07:55 PM

Re: Testing for an empty dictionary in Python

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

**Arnaud Delobelle** · Mar 23 '08, 08:15 PM

Re: Testing for an empty dictionary in Python

On Mar 23, 5:45 pm, Paul Rubin <http://phr...@NOSPAM.i nvalidwrote:

John Nagle <na...@animats. comwrites:

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

**Steven D'Aprano** · Mar 24 '08, 02:45 AM

Re: Testing for an empty dictionary in Python

On Sun, 23 Mar 2008 18:56:51 -0700, John Machin wrote:

>Python knows the truth value of built-in types like dicts without
>actually converting them to bools, or for that matter calling __len__
>or __nonzero__ on them.

>
What the 2.5.1 interpreter does is call PyObject_IsTrue , which checks to
see if the built_in or extension type is a mapping (not just a dict)
with a length method and if so calls it; similarly for sequences:
>
else if (v->ob_type->tp_as_mappin g != NULL &&
v->ob_type->tp_as_mappin g->mp_length != NULL)
res = (*v->ob_type->tp_as_mappin g->mp_length)(v );
else if (v->ob_type->tp_as_sequen ce != NULL &&
v->ob_type->tp_as_sequen ce->sq_length != NULL)
res = (*v->ob_type->tp_as_sequen ce->sq_length)(v );
>
Was that what you meant by "without ... calling __len__"?

What I meant was that the interpreter *didn't* do was lookup the name
'__len__' via the normal method resolution procedure. There's no need to
search the dict's __dict__ attribute looking for an attribute named
__len__, or indeed any sort of search at all. It's a direct pointer
lookup to get to mp_length.

I didn't mean to imply that Python magically knew whether a dict was
empty without actually checking to see if it were empty. Apologies for
being less than clear.

Also, since I frequently criticize others for confusing implementation
details with Python the language, I should criticize myself as well. What
I described is specific to the CPython implementation -- there's no
requirement for other Python versions to do the same thing.

--
Steven