[Python-ideas] add a list.swap() method
python at rcn.com
Thu Jun 25 23:58:24 CEST 2009
> 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:
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
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).
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