Testing for an empty dictionary in Python

[Ryan Ginstrom]

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:
for k in D:
return False
return True
True

Regards,
Ryan Ginstrom

 

[D'Arcy J.M. Cain]

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.

 

[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).

John Nagle

 

[Brian Lane]

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

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-----

 

[Paddy]

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]

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]

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]

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



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]

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

 

[John Machin]

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?

 

[Steven D'Aprano]

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

Except that "if dict" doesn't needlessly and wastefully create a bool.
1.8825540542602539


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.

 

[John Machin]

Except that "if dict" doesn't needlessly and wastefully create a bool.


1.8825540542602539

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_mapping != NULL &&
v->ob_type->tp_as_mapping->mp_length != NULL)
res = (*v->ob_type->tp_as_mapping->mp_length)(v);
else if (v->ob_type->tp_as_sequence != NULL &&
v->ob_type->tp_as_sequence->sq_length != NULL)
res = (*v->ob_type->tp_as_sequence->sq_length)(v);

Was that what you meant by "without ... calling __len__"?

 

[Steven D'Aprano]

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_mapping != NULL &&
v->ob_type->tp_as_mapping->mp_length != NULL)
res = (*v->ob_type->tp_as_mapping->mp_length)(v);
else if (v->ob_type->tp_as_sequence != NULL &&
v->ob_type->tp_as_sequence->sq_length != NULL)
res = (*v->ob_type->tp_as_sequence->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.

 

[Bryan Olson]

Try this:

if dict:

D'Arcy is right; that's the way to go. I'll add that 'dict' is the name
of the built-in class, so an instance is usually best named something else.

 

[John Nagle]

D'Arcy is right; that's the way to go. I'll add that 'dict' is the name
of the built-in class, so an instance is usually best named something else.

Is this a documented language feature? The only references to this in
the spec are vague. In "3.4.5 Emulating container types" there's

"Also, an object that doesn't define a __nonzero__() method and whose __len__()
method returns zero is considered to be false in a Boolean context."

That's as close as the reference manual seems to come.
There are mentions that in Python 3K, __nonzero__ should be replaced by
__bool__. But I'm not finding anything in the spec that actually says that
sequences, used in a Boolean context, are False if empty and True if nonempty.

In fact, "5.8 Comparing Sequences and Other Types" in the Tutorial ("Note that
comparing objects of different types is legal. The outcome is deterministic but
arbitrary: the types are ordered by their name.Thus, a list is always smaller
than a string, a string is always smaller than a tuple, etc.") might lead one to
think that this wasn't the case.

John Nagle

 

[Dennis Lee Bieber]

Is this a documented language feature? The only references to this in
the spec are vague. In "3.4.5 Emulating container types" there's

Library reference manual (v2.4 here):

"""
2.3.1 Truth Value Testing
Any object can be tested for truth value, for use in an if or while
condition or as operand of the Boolean operations below. The following
values are considered false:

None

False

zero of any numeric type, for example, 0, 0L, 0.0, 0j.

any empty sequence, for example, '', (), [].

any empty mapping, for example, {}.

instances of user-defined classes, if the class defines a
__nonzero__() or __len__() method, when that method returns the integer
zero or bool value False.

All other values are considered true -- so objects of many types are
always true.

Operations and built-in functions that have a Boolean result always
return 0 or False for false and 1 or True for true, unless otherwise
stated. (Important exception: the Boolean operations "or" and "and"
always return one of their operands.)
"""

--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/