Klaas van Schelven avatar Klaas van Schelven committed 15a4ead

Performance fix of dependency analysis by pushing SortedSets down

Given that each call to _dfs may return a list, and the elements
of those lists may occur multiple times, concatenating the various
lists without removing double elements may lead to very quickly
growing return values.

I've pushed the call to SortedSets()guaranteeing uniqueness of the
elements, down into the method _dfs.

This puts an upper bound to the lenght of the returned value from
_dfs, namely the total amount of available migrations.

This commit is a direct follow-up to #afaeac96a1fb
Again, no tests to demonstrate the existing problem were created,
but the old tests still run (and more quickly so).

Comments (0)

Files changed (1)

south/migration/utils.py

 
     path.pop()
 
+    results = list(SortedSet(results))
     dependency_cache[(start, get_children)] = results
     return results
 
     return _dfs(start, get_children, [])
 
 def depends(start, get_children):
-    result = SortedSet(reversed(list(dfs(start, get_children))))
-    return list(result)
+    return reversed(dfs(start, get_children))
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.