Mercurial was accidentally quadratic:https://accidentallyquadratic.tumblr.com/post/161243900944/mercurial-changegroup-application …
-
-
Replying to @nelhage
"consistency of API" is in tension with "asymptotics clear from the call site", right?
1 reply 0 retweets 0 likes -
Replying to @avibryant @nelhage
you can't swap list for set in 5 chars if their "contains" methods have different signatures.
1 reply 0 retweets 0 likes -
Replying to @avibryant
Yeah, that's why I hedged with “My first point notwithstanding”; I think there's fundamental tension here and I don't have a general answer
1 reply 0 retweets 0 likes -
Replying to @nelhage
Fwiw I'm in favor of sacrificing consistency. Lots of methods that are O(n) across data structures that can still form an API.
1 reply 0 retweets 0 likes -
Replying to @avibryant @nelhage
but eg for Array I'd almost prefer an explicit "any?{|x| x == y}" to "include?"
1 reply 0 retweets 1 like -
Replying to @avibryant
Yeah, in this case I agree. O(n) vs O(1) in a general-purpose data structure shouldn't be glossed over.
1 reply 0 retweets 0 likes -
Replying to @nelhage @avibryant
But in specialized data structures where n is known to be small, maybe it's fine. And (e.g.) O(lg n) and O(1) are often interchangeable.
2 replies 0 retweets 0 likes
yeah it's a judgement call, but there should be some vague commitment that a method is "fast" one way or another. Also for len/size
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.