[Subversion] / PEAK-Rules / peak / rules / indexing.py  

Diff of /PEAK-Rules/peak/rules/indexing.py

Parent Directory | Revision Log

version 2307, Thu May 31 17:33:09 2007 UTC version 2308, Tue Jun 12 04:51:21 2007 UTC
Line 1 
Line 1 
   import sys
   from peak.rules.core import Aspect, abstract, Dispatching, Engine
   
 try:  try:
     set = set      set = set
     frozenset = frozenset      frozenset = frozenset
Line 5 
Line 8 
     from sets import Set as set      from sets import Set as set
     from sets import ImmutableSet as frozenset      from sets import ImmutableSet as frozenset
   
   class Ordering(Aspect):
       """Track inter-expression ordering constraints"""
   
 class AbstractIndex:      def __init__(self, owner, expr):
     def __init__(self):  
         self.constraints = set()          self.constraints = set()
   
     def add_constraint(self, guards):      def requires(self, guards):
         c = frozenset(guards)          c = frozenset(guards)
         cs = self.constraints          cs = self.constraints
         if c in cs:          if c in cs:
Line 22 
Line 26 
                 cs.remove(oldc)                  cs.remove(oldc)
         cs.add(c)          cs.add(c)
   
     def is_legal(self, indexes):      def can_precede(self, exprs):
         if not self.constraints:          if not self.constraints:
             return True              return True
         for c in self.constraints:          for c in self.constraints:
             for i in c:              for e in c:
                 if i in indexes:                  if e in exprs:
                     break                      break
             else:              else:
                 return True                  return True
Line 35 
Line 39 
             return False              return False
   
   
   def define_ordering(ob, seq):
       items = []
       for key in seq:
           Ordering(ob, key).requires(items)
           items.append(key)
   
   def to_bits(ints):
       """Return a bitset encoding the numbers contained in sequence `ints`"""
       b = 0
       for i in ints:
           b |= 1<<i
       return b
   
   if sys.version<"2.4":
       def to_bits(ints):
           """Return a bitset encoding the numbers contained in sequence `ints`"""
           b = 0
           for i in ints:
               if i>31:    # under 2.3, this operation does the wrong thing
                   i = long(i)
               b |= 1<<i
           return b
   
   
   def from_bits(n):
       """Yield the (ascending) numbers contained in bitset n"""
       b = 0
       while n:
           while not n & 15:
               n >>= 4
               b += 4
           if n & 1:
               yield b
           n >>= 1
           b += 1
   
   
   
   
   
   
   class TreeBuilder(object):
       """Template methods for the Chambers&Chen dispatch tree algorithm"""
   
 class TreeBuilder:      def build_root(self, cases, exprs):
     def __init__(self):  
         self.memo = {}          self.memo = {}
           return self.build(cases, exprs)
   
     def build(self, cases, indexes):      def build(self, cases, exprs):
         key = (cases, indexes)          key = (cases, exprs)
         if key in self.memo:          if key in self.memo:
             return self.memo[key]              return self.memo[key]
   
         if not indexes:          if not exprs:
             node = self.build_leaf(cases)              node = self.build_leaf(cases)
         else:          else:
             best, rest = self.best_index(cases, indexes)              best, rest = self.best_expr(cases, exprs)
             assert len(rest) < len(indexes)              assert len(rest) < len(exprs)
   
             if best is None:              if best is None:
                 # No best index found, recurse                  # No best expression found, recurse
                 node = self.build(cases, rest)                  node = self.build(cases, rest)
             else:              else:
                 node = self.build_node(best, cases, rest)                  node = self.build_node(best, cases, rest)
Line 63 
Line 107 
         self.memo[key] = node          self.memo[key] = node
         return node          return node
   
     def build_node(self, index, cases, remaining_indexes):      def build_node(self, expr, cases, remaining_exprs):
         raise NotImplementedError          raise NotImplementedError
   
     def build_leaf(self, cases):      def build_leaf(self, cases):
         raise NotImplementedError          raise NotImplementedError
   
       def selectivity(self, expression, cases):
           """Return (seedcount,totalcases) selectivity statistics"""
           raise NotImplementedError
   
       def cost(self, expr, remaining_exprs):
           return 1
   
   
       def best_expr(self, cases, exprs):
           best_expr = None
   
   
   
   
   
   
     def best_index(self, cases, indexes):  
         best_index = None  
         best_spread = None          best_spread = None
   
         to_do = list(indexes)          to_do = list(exprs)
         remaining = dict.fromkeys(indexes)          remaining = dict.fromkeys(exprs)
         active_cases = len(cases)          active_cases = len(cases)
         skipped = []          skipped = []
   
         while to_do:          while to_do:
             index = to_do.pop()              expr = to_do.pop()
             if not index.is_legal(remaining):              if not Ordering(self, expr).can_precede(remaining):
                 # Skip criteria that have unchecked prerequisites                  # Skip criteria that have unchecked prerequisites
                 skipped.append(index)                  skipped.append(expr)
                 continue                  continue
   
             branches, total_cases = index.selectivity(cases)              branches, total_cases = self.selectivity(expr, cases)
   
             if total_cases == active_cases * branches:              if total_cases == active_cases * branches:
                 # None of the index keys for this expression eliminate any                  # None of the branches for this expression eliminate any
                 # cases, so this expression isn't needed for dispatching                  # cases, so this expression isn't needed for dispatching
                 del remaining[index]                  del remaining[expr]
   
                 # recheck skipped indexes that might be legal now                  # recheck skipped exprs that might be legal now
                 to_do.extend(skipped)                  to_do.extend(skipped)
                 skipped = []                  skipped = []
                 continue                  continue
   
             spread = float(total_cases) / branches              spread = float(total_cases) / branches
             if best_index is None or spread < best_spread:              if best_expr is None or spread < best_spread:
                 best_index, best_spread = index, spread                  best_expr, best_spread = expr, spread
             #    best_cost = self.cost(index, remaining)                  best_cost = self.cost(expr, remaining)
             #elif spread==best_spread:              elif spread==best_spread:
             #    cost = self.cost(index, remaining)                  cost = self.cost(expr, remaining)
             #    if cost < best_cost:                  if cost < best_cost:
             #        best_index, best_cost = index, cost                      best_expr, best_cost = expr, cost
   
         if best_index is not None:          if best_expr is not None:
             del remaining[best_index]              del remaining[best_expr]
         return best_index, frozenset(remaining)          return best_expr, frozenset(remaining)
   

Generate output suitable for use with a patch program
Legend:
Removed from v.2307  
changed lines
  Added in v.2308
cvs-admin@eby-sarna.com

Powered by ViewCVS 1.0-dev

ViewCVS and CVS Help