Self optimizing iterable
Gabriel Genellina
gagsl-py2 at yahoo.com.ar
Fri Jul 17 21:09:22 EDT 2009
En Fri, 17 Jul 2009 21:31:44 -0300, Zac Burns <zac256 at gmail.com> escribió:
> I would like a set like object that when iterated maintains a count of
> where iteration stopped and then re-orders itself based on that count
> so that the iteration stopped on the most bubble to the top.
>
> An example use case for this would be for something like a large table
> of regular expressions that would be iterated over trying to match in
> some string. If some regular expressions are more statistically more
> successful then the iteration will generally be short.
If you require a certain order, it's not a set; better to use a list.
The code below extends the builtin list type to add a "promote" method;
lst.promote(3) "bubbles" lst[3] up (exchanging lst[3] with lst[2]). It's
thread safe, and O(1).
<code>
import threading
class XList(list):
#
@property
def lock(self):
lock = getattr(self, '_lock', None)
if lock is None: lock = self._lock = threading.Lock()
return lock
#
def promote(self, index):
if index<0: index += len(self)
if index>0:
with self.lock:
self[index], self[index-1] = self[index-1], self[index]
</code>
py> a = XList('python')
py> a
['p', 'y', 't', 'h', 'o', 'n']
py> a.promote(3)
py> a
['p', 'y', 'h', 't', 'o', 'n']
py> a.promote(2)
py> a
['p', 'h', 'y', 't', 'o', 'n']
py> a.promote(-1)
py> a
['p', 'h', 'y', 't', 'n', 'o']
py> a.promote(0)
py> a
['p', 'h', 'y', 't', 'n', 'o']
An example, looking for a matching regular expression:
for index,expr in enumerate(exprlist):
m = expr.match(txt)
if m:
dosomethingwith(m)
exprlist.promote(index)
break
After many calls, the most frequently matched expressions appear towards
the front of the list.
> Extend to also include a mapping version
I'm unsure if this point is still applicable. I'm using a list here, not a
set as in your original proposal.
--
Gabriel Genellina
More information about the Python-list
mailing list