Algorithm help per favore

Matt Shomphe MatthewS at HeyAnita.com
Thu Jun 19 17:40:53 CEST 2003


Erik Max Francis <max-resume at alcyone.com> wrote in message news:<3EF12866.CE8C3913 at alcyone.com>...

[snip]
> 
> This contains a particularly subtle bug lurking for user-defined
> sequence types which don't support the negative indices protocol.  A
> much more solid solution, in my opinion, would be to test the index
> _first_ and then test the subscripted value second:

That's something I did not consider (although in my defense, the
original poster was talking about iterating over a list:-)  ).


> 
> >>> l = [6, 3, 3, 3, 5, 7, 6, 3, 4, 4, 3]
> >>> [x for i, x in enumerate(l) if i == 0 or l[i - 1] != x]
> [6, 3, 5, 7, 6, 3, 4, 3]
> 
[snip]

> 
> In general practices, it's a good idea to test the more stringent
> condition first, before the second one, when you have short circuiting
> logical operators like you do in Python (and most other modern
> languages).

I agree, and would have done short-circuting except that I didn't
think that Python had this feature.  A quick test showed me that I was
wrong.

I wanted to change the solution anyway, since not everyone has
enumerate().  Although for this solution, the iterable object needs to
have __len__ defined:

>>> l = [6,3,3,4,5,6,7,7,7,8,8,9]
>>> [l[i] for i in xrange(len(l)) if i == 0 or l[i] != l[i-1]]
[6, 3, 4, 5, 6, 7, 8, 9]

Then, modifying your Range class:

>>> class Range:
	def __init__(self, n):
		self.n = n
	def __getitem__(self, i):
		if 0 <= i < self.n: return i
		else: raise IndexError
	def __len__(self):
		return(self.n)

	
>>> l = Range(10)
>>> [l[i] for i in xrange(len(l)) if i == 0 or l[i] != l[i-1]]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

I think this may be faster than calling enumerate() repeatedly.




More information about the Python-list mailing list