[Python-ideas] add a list.swap() method

Raymond Hettinger python at rcn.com
Thu Jun 25 23:58:24 CEST 2009

[Josiah Carlson]
> If you're really swapping contents that often, you may want to
> consider a different design with a better algorithm (swap 2 pointers
> rather than n+m), rather than speeding up the slow algorithm.

That is what the OP was requesting.  He needs a pointer swap
for speed.  His problem is that his input is a regular list and the
target is a custom list subclass.  Python currently provides no
way for the subclass to steal the pointer from a regular list.

My recommended approach for him is to write a simple, reusable list
subclass in C, one that knows how to steal a pointer from a regular list.
Then he could subclass from that C extension:

class MyFastListBasedThingie(myextensions.SwappableList):
   def __init__(self, some_regular_list):
        if type(some_regular_list) == list:     # an exact match
             self.swap_list_pointers(some_regular_list)  # the fast way
             self.extend(some_regular_list)    # the slow way
             del some_regular_list[:]

The advantage of this design is that it puts responsibility for swapping
in the hands of the class that knows all of the relevant information
(MyFastListBasedThingie knows its own invariants and it knows
that the regular list input is an exact list with no special invariants).
See http://en.wikipedia.org/wiki/GRASP_(Object_Oriented_Design)
for the InformationExpert pattern.

The other advantage is that it leaves the API for general purpose lists
completely unmolested. That API needs to be as friendly as possible.

[Kristján Valur Jónsson]
> There is precedence, I think.
> list.reverse() is semantically identical to
> list[:] = reversed(list)

It's not identical.  There is no list copy or mutation.  Instead it returns either a custom list iterator provided by the listobject 
itself (which knows its own invariants) or it returns an iterator that calls the list's own __getitem__ method.  There is no danger 
to the target of reversed().

> Same goes for sort(), really.

The sort() method is closer in spirit.  It does mutate the list in-place, so any list subclasses must either disable sort() by 
overriding it or it needs to limit its invariants to ones that aren't affected by the mutation.  This is unfortunate because it 
places a burden on every class that inherits from list.  So even though you've found a precedent, I don't think it is something that 
we want to have more of.

Also, the situation for swap() is made more difficult because there are two parties (the swapper and the swappee).  With sort(), a 
subclass is giving permission for mutation by not overriding the sort method.  With swap(), the swappee has no say in the matter. 
There is no way for a swappee's class to declare that its invariants do not support swapping.  The situation is even more acute when 
the swappee is a C extension inheriting from list -- violating its invariants may crash the interpreter.


More information about the Python-ideas mailing list