[Insight-users] RE: Speed of Connected Components Filter

[Peter Cech]

On Wed, May 25, 2005 at 17:59:03 +0200, Peter Cech wrote:
> Hi,
> 
> after looking at the code, I have an idea to share.
> 
> Scenario 1 is quite costly, it always flattens whole table although
> significant fraction of the table is already flattened. But what we can
> do every time new equivalency is added, is to flatten only newly added
> equivalency (see add_flattened.patch attachment). It will help keep the
> equivalency tree shallow (but not flat). It should speed up scenarios
> 2 to 4. What do you think?
> 
> I have attached two patches for itkEquivalencyTable:

This time I really attached them. Sorry.

> add_flattened.patch
> Test of the idea described above. Proper implementation should provide
> another method (say AddFlattened) instead of changing Add, but it should
> suffice for testing and benchmarking.
> 
> flatten_optimize.patch
> Minor optimization to Flatten method, saves one hash table lookup per
> each element of table.
> 
> Please test the patches, I'm curious how much it helps.
> 
> Peter Cech
-------------- next part --------------
--- itkEquivalencyTable.cxx.orig2	2005-05-25 17:27:17.032032280 +0200
+++ itkEquivalencyTable.cxx	2005-05-25 17:51:40.222593504 +0200
@@ -30,14 +30,21 @@
     a = b;
     b = temp;
     }
-  result = m_HashMap.insert( ValueType(a, b) );
+  unsigned long b_flattened = this->RecursiveLookup(b);
+  result = m_HashMap.insert( ValueType(a, b_flattened) );
   
   if (result.second == false)
     { // Stop endless loops.
-    if ( (*(result.first)).second  == b ) return false;
-    else return (this->Add((*(result.first)).second, b));
+    if ( (*(result.first)).second  == b_flattened ) return false;
+    else return (this->Add((*(result.first)).second, b_flattened));
+    }
+  else
+    {
+    if (b != b_flattened)
+      // flatten b as well
+      m_HashMap.find(b)->second = b_flattened;
+    return true;
     }
-  else return true;
 }
   
 //void EquivalencyTable::PrintHashTable()
-------------- next part --------------
--- itkEquivalencyTable.cxx.orig	2005-05-25 17:25:31.879017968 +0200
+++ itkEquivalencyTable.cxx	2005-05-25 17:25:49.128395664 +0200
@@ -55,7 +55,7 @@
   Iterator it = this->Begin();
   while ( it != this->End() )
     {
-    (*it).second = this->RecursiveLookup((*it).first);
+    (*it).second = this->RecursiveLookup((*it).second);
     it++;
     }
 }