Self optimizing iterable

[Gabriel Genellina]

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