[python-nl] fast & simple ?

[Jasper Spaans]

Hoi,

Op 5 mrt 2009, om 06:07 heeft Floris van Manen het volgende geschreven:

> On Mar 4, 2009, at 23:59, eric casteleijn wrote:
>
>> Geen idee wat je code moet doen, en dus hoe die te verbeteren.
>
> OK, zonder KAPITALEN :-)
> De bedoeling is om in een gegeven lijst met tuples, dat punt te  
> vinden dat met de index r in de fact colom wordt aangewezen en  
> waarvan de waarde dan in de data colom staat.
> De waarden voor fact zijn ook tussen 0..1 en oplopend gesorteerd. Ze  
> markeren een gebied.
> Waarbij r tussen 0..1 zoek je eerst het interval N .. N+1 waar factN  
> < r < factN+1
> vervolgens is het resultaat de interpolatie tussen dataN en dataN+1


Grappig -- ditzelfde heb ik 2 jaar terug ook eens nodig gehad, maar  
toen ben ik niet verder gekomen dan een class met functies als:

     def find_before(self, target):
         # XXX this should be done using a btree. today, we don't

en vervolgens een lineaire search over m'n items, want zo performance  
behoeftig was ik niet.

Van Jan-Wijbrand Kolman kreeg ik toen de hint om eens te kijken naar  
BTrees uit ZODB, want één van de dingen die in de interface van die  
classes beloofd wordt is namelijk:

     def maxKey(key=None):
         """Return the maximum key.

         If a key argument if provided and not None, return the  
largest key
         that is less than or equal to the argument.  Raise an  
exception if
         no such key exists.
         """

     def minKey(key=None):
         """Return the minimum key.

         If a key argument if provided and not None, return the  
smallest key
         that is greater than or equal to the argument.  Raise an  
exception
         if no such key exists.

en die zijn in C geïmplementeerd, dus potentieel iets rapper dan een  
pure python implementatie. Voordeel is bovendien dat je nu je  
(lelijke) FACT en DATA indices kwijtraakt, want je slaat je data  
gewoon in een dict-achtige op.

Werkt dus als volgt als je keys integers zijn, je float geval is left  
as an exercise to the reader [0]:

 >>> import BTrees
 >>> a = BTrees.IOBTree.IOBTree()
 >>> a[0] = 1
 >>> a[2] = 3
 >>> a.maxKey(1)
0
 >>> a.minKey(1)
2

en je kan los met die interpolatie.

HTH,
Jasper

[0] Bovendien loop je het risico dat je in dat geval terug naar  
pythonland moet voor elke comparison, dus misschien ben je je voordeel  
dan kwijt, maar zeker weten doe ik dat ook weer niet. Je code wordt er  
wel leesbaarder van in ieder geval.
-- 
Jasper Spaans                                          http://jasper.es/
              This line was last modified 0 seconds ago.