Am 10.01.2014 19:19, schrieb Ciaran McCreesh: > On Fri, 10 Jan 2014 14:18:24 +0100 > René Neumann <li...@necoro.eu> wrote: >> And again: What is needed is streamlining the algorithms (discussion >> on that already started as far as I could notice). An algorithm in >> O(n³) is always¹ worse than O(n). The constant factor added by the > > Full dependency resolution is NP-hard...
Though NP-hard does not necessarily mean 'unfeasible in practice'. > If you really wanted to > streamline the algorithms, you'd change the inputs slightly. Most of > the complexity of doing a decent job of dependency resolution comes from > dealing with crap input. My intention really was not to tell anybody how the depres algorithms should be improved. I just wanted to make a point against the 'Python is the root of all the bad performance'. >> ¹ For a large enough n. > > ...which could be larger than the number of atoms in the universe. > There are real world cases where an algorithm has an O(n^3) step that > takes a day, and a O(2^n) step that takes a second for most inputs. You > shouldn't be using O() to make performance comparisons. > Point taken. I should've use 'in general' instead of 'always'. What I had in mind when writing this were more smaller problems, where a good algorithm exists but people use their own naïve implementation/data structure. - René
