Changeset 5860

Timestamp:

Oct 23, 2008, 9:28:02 AM (16 years ago)

Author:

ole

Message:

Thought of testing hash-collision and found issue with comparison
This is now fixed and tests verified.

Location:

anuga_core/source/anuga/caching

Files:

• caching.py (modified) (7 diffs)
• test_caching.py (modified) (2 diffs)

anuga_core/source/anuga/caching/caching.py

@@ -221 +221 @@
     be evaluated. If both evaluate and test are switched on, evaluate takes
     precedence.
+    ??NOTE: In case of hash collisions, this may return the wrong result as
+    ??it only checks if *a* cached result is present. 
     
   Obtain cache filenames:
@@ -1389 +1391 @@
   return(val)
 
-# -----------------------------------------------------------------------------
 
 
@@ -1402 +1403 @@
     """
 
-    try:
-        identical = (A == B)
-    except:
-        # E.g. if A and B are circular or otherwise can't be compared.
-        identical = False
-        
-        
-    if identical is False:    
-        # Use pickle to compare data
-        # The native pickler must be used
-        # since the faster cPickle does not 
-        # guarantee a unique translation
-        
-        import pickle as pickler # Use non-C version here
-        #import cPickle as pickler 
-        identical = (pickler.dumps(A,0) == pickler.dumps(B,0))
-
-    return(identical)
-
-
-def old_compare(A, B, ids=None):
-    """Safe comparison of general objects
-
-    USAGE:
-      compare(A,B)
-
-    DESCRIPTION:
-      Return 1 if A and B they are identical, 0 otherwise
-    """
-
-    # FIXME (Ole): This is probably obsolete now
-    
     from types import TupleType, ListType, DictType, InstanceType
-    
+    from Numeric import ArrayType, alltrue    
     
     # Keep track of unique id's to protect against infinite recursion
     if ids is None: ids = {}
-
 
     # Check if T has already been encountered
@@ -1453 +1421 @@
     
     
-    #print 'Comparing', A, B, (iA, iB)
-    #print ids
-    #raw_input()
-    
-    if type(A) in [TupleType, ListType] and type(B) in [TupleType, ListType]:
+    # Check if arguments are of same type
+    if type(A) != type(B):
+        return False
+        
+  
+    # Compare recursively based on argument type
+    if type(A) in [TupleType, ListType]:
         N = len(A)
         if len(B) != N: 
@@ -1466 +1436 @@
                 if not compare(A[i], B[i], ids): 
                     identical = False; break
-                
-    elif type(A) == DictType and type(B) == DictType:
+                    
+    elif type(A) == DictType:
         if len(A) != len(B):
             identical = False
-        else:    
-            identical = True
-            for key in A.keys():
-                if not B.has_key(key):
-                    identical = False; break
-          
-                if not compare(A[key], B[key], ids): 
-                    identical = False; break      
-    
-    elif type(A) == type(B) == types.InstanceType:    
+        else:                        
+            # Make dictionary ordering unique 
+            a = A.items(); a.sort()    
+            b = B.items(); b.sort()
+            
+            identical = compare(a, b, ids)
+            
+    elif type(A) == ArrayType:
+        # Use element by element comparison
+        identical = alltrue(A==B)
+
+    elif type(A) == InstanceType:
         # Take care of special case where elements are instances            
-        # Base comparison on attributes 
-                
-        a = A.__dict__                 
-        b = B.__dict__                             
-                
-        identical = compare(a, b, ids)                
-
-    
-        
+        # Base comparison on attributes     
+        identical = compare(A.__dict__, 
+                            B.__dict__, 
+                            ids)
     else:       
         # Fall back to general code
@@ -1495 +1462 @@
             identical = (A == B)
         except:
-            import pickle # Use non-C version here
+            import pickle
+            # Use pickle to compare data
+            # The native pickler must be used
+            # since the faster cPickle does not 
+            # guarantee a unique translation            
             try:
                 identical = (pickle.dumps(A,0) == pickle.dumps(B,0))
             except:
-                identical = 0
+                identical = False
 
     # Record result of comparison and return            
@@ -1506 +1477 @@
     return(identical)
 
+    
 # -----------------------------------------------------------------------------
 

anuga_core/source/anuga/caching/test_caching.py

@@ -163 +163 @@
             
 
+    def test_hash_collision(self):
+        """test_hash_collision(self):
+        
+        Test that hash collisons are dealt with correctly
+        """
+        
+        verbose = False
+        
+        # Make test input arguments
+        A0 = arange(5)*1.0
+        B = ('x', 15)
+        
+        # Create different A that hashes to the same address (having the same average)
+        A1 = array([2.0, 2.0, 2.0, 2.0, 2.0])        
+        
+        assert myhash(A0) == myhash(A1)
+            
+            
+        # Test caching
+        comprange = 2
+        for comp in range(comprange):
+        
+            # Clear
+            cache(f_numeric, (A0, A0), clear=1,
+                  compression=comp, verbose=verbose)        
+            cache(f_numeric, (A1, A1), clear=1,
+                  compression=comp, verbose=verbose)                          
+  
+  
+            # Evaluate and store
+            T1 = cache(f_numeric, (A0, A0), evaluate=1,
+                       compression=comp, verbose=verbose)
+
+            
+            # Check that A1 doesn't trigger retrieval of the previous result 
+            # even though it hashes to the same address
+            T2 = cache(f_numeric, (A1, A1), 
+                       compression=comp, verbose=verbose) 
+            
+
+            #print T1
+            #print T2
+            assert T2 != T1
+
+            
+
+            
+            
     def test_caching_of_dictionaries(self):
         """test_caching_of_dictionaries
@@ -771 +819 @@
 #-------------------------------------------------------------
 if __name__ == "__main__":
+    #suite = unittest.makeSuite(Test_Caching, 'test_hash_collision')
     suite = unittest.makeSuite(Test_Caching, 'test')
     runner = unittest.TextTestRunner()