benrg <benrud...@gmail.com> added the comment:
Anything that produces output of O(m+n) size in O(m+n) time. Ordered merging operations. Mergesort is a binary ordered merge with log-depth tree reduction, and insertion sort is the same binary operation with linear-depth tree reduction. Say you're merging sorted lists of intervals, and overlapping intervals need special treatment. It's easier to write a manifestly correct binary merge than an n-way merge, or a filter after heapq.merge that needs to deal with complex interval clusters. I've written that sort of code. Any situation that resembles a fast path but doesn't qualify for the fast path. For example, there's an optimized factorial function in math, but you need double factorial. Or math.prod is optimized for ints as you suggested, but you have a class that uses ints internally but doesn't pass the CheckExact test. Usually when you miss out on a fast path, you just take a (sometimes large) constant-factor penalty, but here it pushes you into a different complexity class. Or you have a class that uses floats internally and wants to limit accumulated roundoff errors, but the struture of the computation doesn't fit fsum. >Tree reduction is very popular in the parallel processing world, for obvious >reasons. It's the same reason in every case: the log depth limits the accumulation of some bad thing. In parallel computing it's critical-path length, in factorial and mergesort it's size, in fsum it's roundoff error. Log depth helps in a range of situations. >I've searched in vain for other languages that try to address this "in general" You've got me there. >As Guido will tell you, the only original idea in Python is adding an "else" >clause to loops ;-) I don't think that's really true, except in the sense that there's nothing new under the sun. No one would use Python if it was just like other languages except slower and with for-else. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue46868> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
