Python Cookbook 2Nd Edition Jun 1002005 [Electronic resources] نسخه متنی

Recipe 5.12. Performing Frequent Membership Tests on a Sequence

Credit: Alex Martelli

Problem

You need to
perform frequent tests for membership in a sequence. The
O(n) behavior of repeated in
operators hurts performance, but you can't switch to
using just a dictionary or set instead of the
sequence, because you also need to keep the
sequence's order.

Solution

Say you need to append items to a list only if
they're not already in the list. One sound approach
to this task is the following function:

def addUnique(baseList, otherList):
auxDict = dict.fromkeys(baseList)
for item in otherList:
if item not in auxDict:
baseList.append(item)
auxDict[item] = None

If your code has to run only under Python 2.4, you can get exactly
the same effect with an auxiliary set rather than an auxiliary
dictionary.

Discussion

A simple (naive?) approach to this recipe's task
looks good:

def addUnique_simple(baseList, otherList):
for item in otherList:
if item not in baseList:
baseList.append(item)

and it may be sort of OK, if the lists are very
small.

However, the simple approach can be quite slow if the lists are not
small. When you check if item not in baseList,
Python can implement the in operator in only one
way: an internal loop over the elements of baseList,
ending with a result of true as soon as an element
compares equal to item, with a result of
False if the loop terminates without having found
any equality. On average, executing the
in-operator takes time proportional to
len(baseList). addUnique_simple
executes the in-operator
len(otherList) times, so, in all, it takes time
proportional to the product of the lengths of
the two lists.

In the addUnique function shown in the
"Solution", we first build the
auxiliary dictionary auxDict, a step that takes time
proportional to len(baseList). Then, the
in-operator inside the loop checks for membership
in a dicta step that makes all the
difference because checking for membership in a
dict takes roughly constant time, independent of
the number of items in the dict! So, the
for loop takes time proportional to
len(otherList), and the entire function takes time
proportional to the sum of the lengths of the
two lists.

The analysis of the running times should in fact go quite a bit
deeper, because the length of baseList is not
constant in addUnique_simple; baseList grows each
time an item is processed that was not already
there. But the gist of the (surprisingly complicated) analysis is not
very different from what this simplified version indicates. We can
check this by measuring. When each list holds 10 integers, with an
overlap of 50%, the simple version is about 30% slower than the one
shown in the "Solution", the kind
of slowdown that can normally be ignored. But with lists of 100
integers each, again with 50% overlap, the simple version is
twelve times slower than the one shown in the
"Solution"a level of
slowdown that can never be ignored, and it only gets worse if the
lists get really substantial.

Sometimes, you could obtain even better overall performance for your
program by permanently placing the auxiliary dict
alongside the sequence, encapsulating both into one object. However,
in this case, you must maintain the dict as the
sequence gets modified, to ensure it stays in sync with the
sequence's current membership. This maintenance task
is not trivial, and it can be architected in many different ways.
Here is one such way, which does the syncing "just
in time," rebuilding the auxiliary
dict when a membership test is required and the
dictionary is possibly out of sync with the list's
contents. Since it costs very little, the following class optimizes
the index method, as well as membership tests:

class list_with_aux_dict(list):
def _ _init_ _(self, iterable=( )):
list._ _init_ _(self, iterable)
self._dict_ok = False
def _rebuild_dict(self):
self._dict = {  }
for i, item in enumerate(self):
if item not in self._dict:
self._dict[item] = i
self._dict_ok = True
def _ _contains_ _(self, item):
if not self._dict_ok:
self._rebuild_dict( )
return item in self._dict
def index(self, item):
if not self._dict_ok:
self._rebuild_dict( )
try: return self._dict[item]
except KeyError: raise ValueError
def _wrapMutatorMethod(methname):
_method = getattr(list, methname)
def wrapper(self, *args):
# Reset 'dictionary OK' flag, then delegate to the real mutator method
self._dict_ok = False
return _method(self, *args)
# in Python 2.4, only: wrapper._ _name_ _ = _method._ _name_ _
setattr(list_with_aux_dict, methname, wrapper)
for meth in 'setitem delitem setslice delslice iadd'.split( ):
_wrapMutatorMethod('_ _%s_ _' % meth)
for meth in 'append insert pop remove extend'.split( ):
_wrapMutatorMethod(meth)
del _wrapMethod # remove auxiliary function, not needed any more

The list_with_aux_dict class extends
list and delegates to it every method, except
_ _contains_ _ and index. Every
method that can modify list membership is wrapped in a closure that
resets a flag asserting that the auxiliary dictionary is OK.
Python's in-operator calls the
_ _contains_ _ method.
list_with_aux_dict's _
_contains_ _ method rebuilds the auxiliary dictionary,
unless the flag is set (when the flag is set, rebuilding is
unnecessary); the index method works the same way.

Instead of building and installing wrapping closures for all the
mutating methods of the list into the
list_with_aux_dict class with a helper function, as
the recipe does, we could write all the def
statements for the wrapper methods in the body of
list_with_aux_dict. However, the code for the class
as presented has the important advantage of minimizing boilerplate
(repetitious plumbing code that is boring and voluminous, and thus a
likely home for bugs). Python's strengths at
introspection and dynamic modification give you a choice: you can
build method wrappers, as this recipe does, in a smart and concise
way; or, you can choose to code the boilerplate anyway, if you prefer
to avoid what some would call the black magic of introspection and
dynamic modification of class objects.

The architecture of class list_with_aux_dict caters
well to a rather common pattern of use, where sequence-modifying
operations happen in bunches, followed by a period of time in which
the sequence is not modified, but several membership tests may be
performed. However, the addUnique_simple function
shown earlier would not get any performance benefit if argument
baseList was an instance of this
recipe's list_with_aux_dict rather
than a plain list: the function interleaves
membership tests and sequence modifications. Therefore, too many
rebuilds of the auxiliary dictionary for
list_with_aux_dict would impede the
function's performance. (Unless a typical case was
for a vast majority of the items of
otherList to be already contained in
baseList, so that very few modifications
occurred compared to the number of membership tests.)

An important requisite for any of these membership-test optimizations
is that the values in the sequence must be hashable (otherwise, of
course, they cannot be keys in a dict, nor items
in a set). For example, a list of tuples might be
subjected to this recipe's treatment, but for a list
of lists, the recipe as it stands is just not applicable.

See Also

The Library Reference and Python in
a Nutshell sections on sequence types and mapping
types.