Please use the Apache issue tracking system for new NetBeans issues (https://issues.apache.org/jira/projects/NETBEANS0/issues) !!
Bug 27286 - Optimize Utilities.partialSort
Optimize Utilities.partialSort
Status: RESOLVED FIXED
Product: platform
Classification: Unclassified
Component: -- Other --
3.x
PC Linux
: P3 (vote)
: 3.x
Assigned To: Jaroslav Tulach
issues@platform
: PERFORMANCE
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2002-09-12 23:06 UTC by Jesse Glick
Modified: 2008-12-22 19:36 UTC (History)
0 users

See Also:
Issue Type: TASK
:


Attachments
Description of the algorithm to detect "strongly connected components" in the graph (czech) (138.44 KB, patch)
2003-01-09 08:49 UTC, Jaroslav Tulach
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jesse Glick 2002-09-12 23:06:29 UTC
With a proper algorithm to get correct asymptotic
behavior. The overhead of this method becomes
noticeable (though not terribly large) with a lot
of modules: mainly due to dependency sorting.
Comment 1 Jesse Glick 2002-09-12 23:07:20 UTC
Also take a look at times for
org.netbeans.core.modules.Util.DependencyComparator.compare.
Comment 2 Jesse Glick 2002-12-17 20:02:02 UTC
May be more than I thought before; OptIt says that this line

Object elt2 = it2.next ();

is a hot spot.
Comment 3 Jesse Glick 2002-12-18 23:25:59 UTC
committed   * Up-To-Date  1.11        core/manifest.mf
committed   * Up-To-Date  1.11       
core/src/org/netbeans/beaninfo/DataLoaderBeanInfo.java
committed   * Up-To-Date  1.64       
core/src/org/netbeans/core/LoaderPoolNode.java
committed   * Up-To-Date  1.49       
core/src/org/netbeans/core/modules/ModuleManager.java
committed   * Up-To-Date  1.17       
core/src/org/netbeans/core/modules/Util.java
committed   * Up-To-Date  1.25       
core/test/unit/src/org/netbeans/core/modules/ModuleManagerTest.java
committed   * Up-To-Date  1.90        openide/openide-spec-vers.properties
committed   * Up-To-Date  1.121      
openide/api/doc/changes/apichanges.xml
committed   * Up-To-Date  1.42       
openide/src/org/openide/loaders/DataLoader.java
committed   * Up-To-Date  1.60       
openide/src/org/openide/loaders/FolderList.java
committed   * Up-To-Date  1.9        
openide/src/org/openide/loaders/FolderOrder.java
committed   * Up-To-Date  1.112      
openide/src/org/openide/util/Utilities.java
added       * Up-To-Date  1.1        
openide/test/unit/src/org/openide/util/UtilitiesTopologicalSortTest.java
Comment 4 Jaroslav Tulach 2003-01-07 10:38:29 UTC
In topological_sort_27286 branch (branch point is BLD200301070100)
there is a bit improved version of Utilities.topologicalSort that does
cycle detection and removes the necessity for topologicalSortError
method. On the other hand it introduces new exception that is thrown
in case a cycle is detected.

Reopened to let Jesse evaluate the new version and decide whether it
is better than the original.
Comment 5 Jaroslav Tulach 2003-01-09 08:47:19 UTC
Does the silence means that the branch should be integrated? Ok, I'll
do that tomorrow.
Comment 6 Jaroslav Tulach 2003-01-09 08:49:06 UTC
Created attachment 8487 [details]
Description of the algorithm to detect "strongly connected components" in the graph (czech)
Comment 7 Jesse Glick 2003-01-09 12:26:33 UTC
Sorry, I saw your work but did not get a chance to pay more attention.
I guess it is good - briefly looked at the branch. Did not try to
understand all of TopologicalSortException in detail, but will assume
it is right - tests look good.

Missing @since on TSE.

Also need to update all core + openide clients (incl. FolderList.main
which still uses old partialSort due to richer error reporting - can
now be replaced).
Comment 8 Jaroslav Tulach 2003-01-09 16:24:46 UTC
Thanks for comments, I'll integrate it.
Comment 9 Jaroslav Tulach 2003-01-10 10:47:33 UTC
/cvs/openide/openide-spec-vers.properties,v  
new revision: 1.95
/cvs/openide/api/doc/changes/apichanges.xml,v
new revision: 1.127;
/cvs/openide/src/org/openide/loaders/FolderList.java,v  
new revision: 1.63
/cvs/openide/src/org/openide/util/TopologicalSortException.java
new revision: 1.2
/cvs/openide/src/org/openide/util/Utilities.java,v
new revision: 1.119; 
cvs diff: TopologicalSortException.java is a new entry, no
/cvs/openide/test/unit/src/org/openide/util/UtilitiesTopologicalSortTest.java
new revision: 1.5
/cvs/core/src/org/netbeans/core/LoaderPoolNode.java
new revision: 1.68
/cvs/core/src/org/netbeans/core/modules/ModuleManager.java
new revision: 1.53


By use of this website, you agree to the NetBeans Policies and Terms of Use. © 2014, Oracle Corporation and/or its affiliates. Sponsored by Oracle logo