Author tim.peters
Recipients Zahari.Dim, belopolsky, christian.heimes, eric.smith, gaborjbernat, gdr@garethrees.org, lukasz.langa, martin.panter, orsenthil, pablogsal, remi.lapeyre, rhettinger, terry.reedy, tim.peters, tshepang, wim.glenn
Date 2020-04-02.19:32:55
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1585855976.15.0.459138434166.issue17005@roundup.psfhosted.org>
In-reply-to
Content
Raymond, what application do you have that wouldn't be completely addressed by sticking to just .add() (to record dependencies) and .static_order() (to retrieve a linear order)?

Larry Hastings and I originally worked out the fancier bits of the interface to deal with problems he actually had, and for which no existing Python topsort implementation we could find was of any use:  extract maximal parallelism.  If you don't want that, fine, stick to the two simple bits.

The bits to support parallelism are very easy to use to write correct parallelized code, but of course can seem baffling if you don't give a rip about parallelism.  But in that case you have no need to learn about them either.

If your alternative isn't equally easy to use in a parallelized context, I'll be at best +0.

About "fast", this is linear time, in the sum of the number of items and dependencies.  Including the part checking for a cycle, which is by far the "hardest" part.  So it's asymptotically optimal, although I've never seen a real context in which topsort speed made a lick of difference.

In the real world, in a parallelized context it can be important to check for a cycle _before_ running a topsort:  actions are performed ASAP based on order-deduced-so-far, and it can be no good to find out "oh! I can't finish this" at the end.  There's actually nothing gratuitous here.  If it seems "over-engineered", that's because it's addressing problems you haven't had yet ;-)
History
Date User Action Args
2020-04-02 19:32:56tim.peterssetrecipients: + tim.peters, rhettinger, terry.reedy, belopolsky, orsenthil, eric.smith, christian.heimes, lukasz.langa, tshepang, gdr@garethrees.org, martin.panter, wim.glenn, Zahari.Dim, pablogsal, remi.lapeyre, gaborjbernat
2020-04-02 19:32:56tim.peterssetmessageid: <1585855976.15.0.459138434166.issue17005@roundup.psfhosted.org>
2020-04-02 19:32:56tim.peterslinkissue17005 messages
2020-04-02 19:32:55tim.peterscreate