diff options
author | A. Unique TensorFlower <gardener@tensorflow.org> | 2017-04-12 13:19:56 -0800 |
---|---|---|
committer | TensorFlower Gardener <gardener@tensorflow.org> | 2017-04-12 14:33:29 -0700 |
commit | 4714207c80e79a3d3e23fa3976c30fdd610ec326 (patch) | |
tree | 404abc40be29e1cf9e884d159c6df2c584cd9047 | |
parent | f2f9cdcadd3ba96c75ea7da4ef67de2a54e373cf (diff) |
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
-rw-r--r-- | tensorflow/contrib/graph_editor/util.py | 15 |
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 |