Optimization.

The original code had a O(n^2) run time. This became a problem when dealing
with graphs of 100-1000+ nodes.

The new code has a run time of O(n).
Change: 152986359

1 files changed, 13 insertions, 2 deletions

diff --git a/tensorflow/contrib/graph_editor/util.py b/tensorflow/contrib/graph_editor/util.py
index 01c31ffc18..ec32beda5a 100644
--- a/tensorflow/contrib/graph_editor/util.py
+++ b/tensorflow/contrib/graph_editor/util.py
@@ -39,10 +39,21 @@ __all__ = [
 
 
 def concatenate_unique(la, lb):
-  """Add all the elements of lb in la if they are not there already."""
+  """Add all the elements of `lb` to `la` if they are not there already.
+
+  The elements added to `la` maintain ordering with respect to `lb`.
+
+  Args:
+    la: List of Python objects.
+    lb: List of Python objects.
+  Returns:
+    `la`: The list `la` with missing elements from `lb`.
+  """
+  la_set = set(la)
   for l in lb:
-    if l not in la:
+    if l not in la_set:
       la.append(l)
+      la_set.add(l)
   return la