Pipenv is hopelessly slow. It's a shame. Remember when git first came out and it changed the way we worked because it was so quick to commit now? (I fully expect that most git users here don't remember that, actually). There is no going back. I will not use slow tools. My tools need to be at the very least as fast as me.
my current project is at 16 dependencies atm and ... its really not as bad as you make it sound.
pipenv lock 5.65s user 0.29s system 77% cpu 7.639 total
i think 7.6 seconds is fine for an operation that you'd rarely do
it would probably take ages at work though. just opening a WSL terminal takes several seconds there, which is predictably instantaneous (<100ms) on fedora linux at home
B-trees are really beautiful. I also like the Aho-Corasick algorithm as used by fgrep. I actually started to reinvent this algorithm myself before finding out it was already done. It's essentially a way to add links to a trie such that you can find all occurrences of multiple substrings within a larger string with one pass through the larger string.
It is absolutely an algorithm in the sense of "a set of rules to be followed". I think you mean that it doesn't guarantee an optimal solution. That just means it's a heuristic algorithm, same as simulated annealing is a heuristic algorithm for solving optimisation problems.
Nope. An algorithm has to be effective. You can find pathological cases for k-means such that it will never converge on anything useful. So if you set your termination case to be convergence it will never terminate and if you don't then it will never be effective.
Knuth defines effectiveness as: "... all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil."
K-means and other heuristic algorithms fit that description.
As far as I can tell you're only arguing against poor implementations of K-means. If you demand that the score strictly improves at each iteration then the algorithm must terminate.
K-means implementations generally terminate once there's an iteration where the score doesn't improve. This happens when there is convergence to a local minimum or - less likely - the state hops between two nearby local minima with the same score. But it will terminate on something, and most of the time that something will be pretty good.
I saw your mention of Knuth elsewhere, I looked it up and he demanded that
> An algorithm must always terminate after a finite number of steps ... a very finite number, a reasonable number
This is a pretty niche characterization and almost certainly not what the original post was asking for. However, I concur that there is no guarantee on how quickly K-means terminates or on how good the output will be,. But... if you're going to be that strict about it you would even have to rule out the Simplex Algorithm, which everyone I've ever spoken to thinks of as an algorithm.
This isn't a classroom, and your pedantry isn't adding anything useful to the conversation. We all understand these pedantic quibbles you're arguing about... and what the community is more or less collectively saying is "in this context, we don't care about the distinction between an 'algorithm' in the textbook sense, and a 'heuristic' in the textbook sense".
To be fair, you haven't explained at all clearly why you don't think k-means adheres to Knuth's notion of an algorithm.
Your objection seems to be
> You can find pathological cases for k-means such that it will never converge on anything useful
As has been pointed out more than once, a good implementation of k-means is guaranteed to terminate in a finite time. And whatever you mean by "useful" doesn't seem to appear in Knuth's definition of an algorithm.
It's only OK to parse something with regex if it was defined with regex. Far too often I see people wanting to match postcodes and things which are not defined by regex and your heuristic could break at any time.
Copyright is supposed to protect creative works. There is such a thing as a threshold of originality. There are database rights, but that is separate from copyright.
