Changeset 4886


Ignore:
Timestamp:
09/10/11 22:26:23 (3 years ago)
Author:
wehart
Message:

Reworking the implementation of the RangeSet? class. This class is
now a virtual concrete class, which means that the set elements are
not explicitly constructed. This offers a space savings, and in
most cases a time savings (at least for construction).

However, this changes some fundamental behavior in RangeSet?:

  1. You cannot add, remove or discard elements of a RangeSet?, since it is

virtual.

  1. If the filter or validate methods are specified, then the cost

of using RangeSet? objects becomes much more expensive (i.e. as
expensive as the old implementation). Specifically:

  1. All elements need to be generated to determine the set length
  2. Set membership needs to call these methods

If the filter and validate functions are expensive, then the RangeSet?
object may be more expensive to use than the old implementation.

Since 99% of all uses of RangeSet? look like the following:

RangeSet?(1,10)

this should be a big improvement for the typical user.

Location:
coopr.pyomo/trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • coopr.pyomo/trunk/coopr/pyomo/base/rangeset.py

    r4430 r4886  
    1111__all__ = ['RangeSet'] 
    1212 
     13import math 
    1314import itertools 
    1415import sets 
    1516import expr 
     17import set_types 
     18from misc import apply_indexed_rule 
    1619from numvalue import value 
    1720from pyutilib.component.core import * 
     
    4346 
    4447class RangeSet(sets._SetContainer): 
    45     """A set that represents a list of integer values""" 
     48    """A set that represents a list of numeric values""" 
    4649 
    47     alias("RangeSet", "A sequence of numeric values.  RangeSet(start,end,step) is a sequence starting a value 'start', and increasing in values by 'step' until a value greater than of equal to 'end' is reached.") 
     50    alias("RangeSet", "A sequence of numeric values.  RangeSet(start,end,step) is a sequence starting a value 'start', and increasing in values by 'step' until a value greater than or equal to 'end' is reached.") 
    4851 
    4952    def __init__(self,*args,**kwds): 
     
    5255        sets._SetContainer.__init__(self,*tmp,**kwds) 
    5356        self._type=RangeSet 
    54         self.ordered=True 
    5557        if len(args) == 1: 
    5658            self._start=1 
     
    6567            self._end=args[1] 
    6668            self._step=args[2] 
     69        self.ordered=True 
     70        self.value = None 
     71        self.virtual = True 
     72        self.concrete = True 
     73        self._len = 0 
    6774 
    6875    def construct(self, values=None): 
     
    8592            self._step_val = value(self._step) 
    8693 
    87         if self.validate is None: 
    88             self.validate=RangeSetValidator(self._start_val, self._end_val, self._step_val) 
     94        if type(self._start_val) is int and type(self._step) is int and type(self._end_val) is int: 
     95            self.domain = set_types.Integers 
     96        else: 
     97            self.domain = set_types.Reals 
     98        lb = self._start_val 
    8999 
    90         # 
    91         # Generate set, and track the bounds 
    92         # 
    93         lb = self._start_val 
    94         ub = self._start_val 
     100        if self.filter is None and self.validate is None: 
     101            self._len = int(math.floor((self._end_val-self._start_val+self._step_val+1e-7)//self._step_val)) 
     102            ub = self._start_val + (self._len-1)*self._step_val 
     103        else: 
     104            ub = self._start_val 
     105            ctr=0 
     106            for i in self: 
     107                ub = i 
     108                ctr += 1 
     109            self._len = ctr 
     110        self._bounds = (lb,ub) 
    95111 
    96         for i in itertools.islice(count(), (self._end_val-self._start_val+self._step_val+1e-7)//self._step_val): 
    97             val = self._start_val + i*self._step_val 
    98             if self._verify(val, False): 
    99                 ub=val 
    100                 self.add(val) 
     112    def __len__(self): 
     113        return self._len 
    101114 
    102         # 
    103         # Apply the filter, if present 
    104         # 
    105         if self.filter is not None: 
    106             self._apply_filter() 
    107             lb = min(self.value) 
    108             ub = max(self.value) 
     115    def __iter__(self): 
     116        if self.filter is None and self.validate is None: 
     117            for i in itertools.islice(count(), (self._end_val-self._start_val+self._step_val+1e-7)//self._step_val): 
     118                yield self._start_val + i*self._step_val 
     119        else: 
     120            for i in itertools.islice(count(), (self._end_val-self._start_val+self._step_val+1e-7)//self._step_val): 
     121                val = self._start_val + i*self._step_val 
     122                if not self.filter is None and not apply_indexed_rule(self, self.filter, self.model(), val): 
     123                    continue 
     124                if not self.validate is None and not apply_indexed_rule(self, self.validate, self.model(), val): 
     125                    continue 
     126                yield val 
    109127 
    110         # Assign bounds 
    111         self._bounds=(lb,ub) 
     128    def data(self): 
     129        """The underlying set data.""" 
     130        return set(self) 
     131 
     132    def first(self): 
     133        return self._bounds[0] 
     134 
     135    def last(self): 
     136        return self._bounds[1] 
     137 
     138    def member(self, key): 
     139        if key >= 1: 
     140            if key > self._len: 
     141                raise IndexError, "Cannot index a RangeSet past the last element" 
     142            return self._start_val + (key-1)*self._step_val 
     143        elif key < 0: 
     144            if self._len+key < 0: 
     145                raise IndexError, "Cannot index a RangeSet past the first element" 
     146            return self._start_val + (self._len+key)*self._step_val 
     147        else: 
     148            raise IndexError, "Valid index values for sets are 1 .. len(set) or -1 .. -len(set)" 
     149 
     150    def __eq__(self, other): 
     151        """ Equality comparison """ 
     152        if other is None: 
     153            return False 
     154        tmp = self._set_repn(other) 
     155        if self.dimen != other.dimen: 
     156            return False 
     157        ctr = 0 
     158        for i in self: 
     159            if not i in other: 
     160                return False 
     161            ctr += 1 
     162        return ctr == len(other) 
     163 
     164    def _set_contains(self, element): 
     165        if not type(element) in [int,float]: 
     166            return False 
     167        if not self.filter is None and not self.filter(element): 
     168            return False 
     169        if not self.validate is None and not self.validate(element): 
     170            return False 
     171        tmp = (element - self._start_val)//self._step_val 
     172        itmp = int(tmp) 
     173        if math.fabs(tmp-itmp) > 1e-7: 
     174            return False 
     175        if itmp < 0 or itmp > self._len: 
     176            return False 
     177        return True 
     178 
  • coopr.pyomo/trunk/coopr/pyomo/tests/examples/test6.txt

    r4715 r4886  
    6060    A sequence of numeric values.  RangeSet(start,end,step) is 
    6161    a sequence starting a value 'start', and increasing in 
    62     values by 'step' until a value greater than of equal to 
     62    values by 'step' until a value greater than or equal to 
    6363    'end' is reached. 
    6464 
  • coopr.pyomo/trunk/coopr/pyomo/tests/unit/test_set.py

    r4685 r4886  
    364364        self.e6=6 
    365365 
     366    def test_member(self): 
     367        self.assertEqual(self.instance.A.member(-1),5) 
     368        self.assertEqual(self.instance.A.member(-2),4) 
     369        self.assertEqual(self.instance.A.member(-3),3) 
     370        self.assertEqual(self.instance.A.member(-4),2) 
     371        self.assertEqual(self.instance.A.member(-5),1) 
     372        self.assertEqual(self.instance.A.member(1),1) 
     373        self.assertEqual(self.instance.A.member(2),2) 
     374        self.assertEqual(self.instance.A.member(3),3) 
     375        self.assertEqual(self.instance.A.member(4),4) 
     376        self.assertEqual(self.instance.A.member(5),5) 
     377        try: 
     378            self.instance.A.member(6) 
     379            self.fail("Expected IndexError") 
     380        except IndexError: 
     381            pass 
     382        try: 
     383            self.instance.A.member(-6) 
     384            self.fail("Expected IndexError") 
     385        except IndexError: 
     386            pass 
     387        try: 
     388            self.instance.A.member(0) 
     389            self.fail("Expected IndexError") 
     390        except IndexError: 
     391            pass 
     392 
     393    def test_clear(self): 
     394        """Check the clear() method empties the set""" 
     395        try: 
     396            self.instance.A.clear() 
     397            self.fail("Expected TypeError because a RangeSet is a virtual set") 
     398        except TypeError: 
     399            pass 
     400 
     401    def test_virtual(self): 
     402        """Check if this is a virtual set""" 
     403        self.assertEqual( self.instance.A.virtual, True) 
     404 
    366405    def test_bounds(self): 
    367406        """Verify the bounds on this set""" 
     
    370409    def test_addValid(self): 
    371410        """Check that we can add valid set elements""" 
    372         try: 
    373             self.instance.A.add(self.e6) 
    374             self.instance.A.add(self.e3) 
    375         except ValueError: 
    376             pass 
    377         else: 
    378             self.fail("Should fail when adding an element that already exists in a set.") 
    379         self.assertEqual( len(self.instance.A), 5) 
     411        pass 
    380412 
    381413    def test_addInvalid(self): 
     
    385417        # is, the default within is None 
    386418        # 
    387         self.assertEqual( self.instance.A.within, None) 
    388419        try: 
    389420            self.instance.A.add('2','3','4') 
    390         except ValueError: 
    391             pass 
    392         else: 
    393             self.fail("test_addInvalid") 
    394         self.assertFalse( '2' in self.instance.A, "Found invalid new element in A") 
     421            self.fail("Expected to generate an error when we remove an element from a RangeSet") 
     422        except TypeError: 
     423            pass 
     424        self.assertFalse( '2' in self.instance.A, "Value we attempted to add is not in A") 
    395425 
    396426    def test_removeValid(self): 
    397427        """Check that we can remove a valid set element""" 
    398         self.instance.A.remove(self.e3) 
    399         self.assertEqual( len(self.instance.A), 4) 
    400         self.assertFalse( self.e3 in self.instance.A, "Found element in A that we removed") 
     428        try: 
     429            self.instance.A.remove(self.e3) 
     430            self.fail("Expected to generate an error when we remove an element from a RangeSet") 
     431        except KeyError: 
     432            pass 
     433        self.assertEqual( len(self.instance.A), 5) 
     434        self.assertTrue( self.e3 in self.instance.A, "Element is still in A") 
    401435 
    402436    def test_removeInvalid(self): 
     
    407441    def test_remove(self): 
    408442        """ Check that the elements are properly removed  by .remove """ 
    409         self.instance.tmp = RangeSet(0,10) 
    410         self.instance.tmp.construct() 
    411         self.instance.tmp.remove(0) 
    412         self.instance.tmp.remove(5) 
    413         self.instance.tmp.remove(10) 
    414         self.assertEqual([x for x in self.instance.tmp] == [1,2,3,4,6,7,8,9], True) 
     443        pass 
    415444 
    416445    def test_discardValid(self): 
    417446        """Check that we can discard a valid set element""" 
    418         self.instance.A.discard(self.e3) 
    419         self.assertEqual( len(self.instance.A), 4) 
    420         self.assertFalse( self.e3 in self.instance.A, "Found element in A that we removed") 
     447        try: 
     448            self.instance.A.discard(self.e3) 
     449            self.fail("Expected to generate an error when we discare an element from a RangeSet") 
     450        except KeyError: 
     451            pass 
     452        self.assertEqual( len(self.instance.A), 5) 
     453        self.assertTrue( self.e3 in self.instance.A, "Found element in A that attemped to discard") 
    421454 
    422455    def test_discardInvalid(self): 
    423456        """Check that we fail to remove an invalid set element without an exception""" 
    424         self.instance.A.discard(self.e6) 
    425         self.assertEqual( len(self.instance.A), 5) 
     457        pass 
    426458 
    427459    def test_contains(self): 
     
    573605            tmp.append(i) 
    574606        self.assertEqual(tmp, range(1,11,2)) 
    575         try: 
    576             instance.d.add(2) 
    577             self.fail("Only odd values allowed") 
    578         except ValueError: 
    579             pass 
    580         try: 
    581             instance.d.add(0) 
    582             self.fail("Only positive values allowed") 
    583         except ValueError: 
    584             pass 
    585607        self.assertEqual( instance.d.bounds(), (1,9)) 
    586608 
  • coopr.pyomo/trunk/examples/pyomo/tutorials/set.out

    r4715 r4886  
    104104 
    1051051 RangeSet Declarations 
    106    V_index :    Dim=0   Dimen=1         Size=4  Domain=None     Ordered=True    Bounds=(1, 4) 
     106   V_index :    Dim=0   Dimen=1         Size=4  Domain=Integers         Ordered=True    Bounds=(1, 4) 
    107107         Model=unknown 
    108            [1, 2, 3, 4] 
     108          Virtual 
    109109 
    1101100 Param Declarations 
Note: See TracChangeset for help on using the changeset viewer.