You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
As I've noticed, now the average time complexity for DomainModel.classes_sorted_by_inheritance() is O(|classes|^2), as there are two nested loops which iterates over classes' set. It can be improved with implementation of Topological Sorting algorithm with asymptotic of O(|classes| + |generalizations|), so it can be assumed as linear time, if the number of generalizations is proportional to the number of classes. I haven't tried yet to debug it, but here is how it approximately should look like:
defclasses_sorted_by_inheritance(classes):
# Set up a dependency graphchild_map= {cl: set() forclinclasses}
# Populating the child_map based on generalizations (edges in top-sort graph)forclinclasses:
forgeneralizationincl.generalizations:
child_map[generalization.general].add(cl)
# Helper function for DFSdefdfs(cl, visited, sorted_list):
visited.add(cl)
forchildinchild_map[cl]:
ifchildnotinvisited:
dfs(child, visited, sorted_list)
sorted_list.append(cl)
# Perform DFS from each node that hasn't been visited yetvisited=set()
sorted_list= []
forclinclasses:
ifclnotinvisited:
dfs(cl, visited, sorted_list)
# The classes are sorted from most derived to least derived, so reverse the listsorted_list.reverse()
returnsorted_list
As I told Ivan, I can contribute on this matter as well.
The text was updated successfully, but these errors were encountered:
As I've noticed, now the average time complexity for
DomainModel.classes_sorted_by_inheritance()
isO(|classes|^2)
, as there are two nested loops which iterates over classes' set. It can be improved with implementation of Topological Sorting algorithm with asymptotic ofO(|classes| + |generalizations|)
, so it can be assumed as linear time, if the number of generalizations is proportional to the number of classes. I haven't tried yet to debug it, but here is how it approximately should look like:As I told Ivan, I can contribute on this matter as well.
The text was updated successfully, but these errors were encountered: