Terry Reedy <[EMAIL PROTECTED]> writes:
> Mr.SpOOn wrote:
>> On Sun, Nov 16, 2008 at 7:15 PM, Arnaud Delobelle
>
>>> You should probably use the `bisect` module
>>> (http://docs.python.org/library/bisect.html) for searching and
>>> inserting into the list as it takes advantage of and ensures that the
>>> list keeps sorted. It also means that __contains__ and some other
>>> operations become O(log N) rather than O(N).
>>
>> This seems good too, but I'd always have to check the presence of an
>> element before inserting a new one and it's still not clear to me how
>> to do it.
>
> Read the doc on the bisect module. The first or second function is
> what you need. If you read bisect.py in /Lib, you will discover that
> only two of the 6 possible comparisons are used, so you only need to
> define those two if you want.
>
> The choice between using set and sorted versus list and bisect depends
> on how frequently you do which operations.
You can choose, but maybe you could use both? Use a set for checking
membership and a list for checking order. Keep them synchronized.
e.g.
class Hybrid(object):
def __init__(self, val=[]):
self.as_list = list(val)
self.as_set = set(val)
def __contains__(self, x):
return x in self.as_set
def append(self, x):
if x not in self.as_set:
self.as_set.add(x)
self.as_list.append(x)
def __iter__(self):
return iter(self.as_list)
# etc...
--
Arnaud
--
http://mail.python.org/mailman/listinfo/python-list
