On 2012-09-08, Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> wrote: > On Fri, 07 Sep 2012 19:10:16 +0000, Oscar Benjamin wrote: > >> On 2012-09-07, Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> >> wrote: >> <snip> >> >> Would you say, then, that dict insertion is O(N)? > > Pedantically, yes. > > But since we're allowed to state (or even imply *wink*) whatever > assumptions we like, we're allowed to assume "in the absence of > significant numbers of hash collisions" and come up with amortized O(1) > for dict insertions and lookups. > > (Provided, of course, that your computer has an infinite amount of > unfragmented memory and the OS never starts paging your dict to disk. > Another unstated assumption that gets glossed over when we talk about > complexity analysis -- on real world computers, for big enough N, > *everything* is O(2**N) or worse.) > > Big Oh analysis, despite the formal mathematics used, is not an exact > science. Essentially, it is a way of bringing some vague order to hand- > wavy estimates of complexity, and the apparent mathematical rigour is > built on some awfully shaky foundations. But despite that, it actually is > useful. > > Coming back to strings... given that in any real-world application, you > are likely to have some string comparisons on equal strings and some on > unequal strings, and more importantly you don't know which are which > ahead of time, which attitude is less likely to give you a nasty surprise > when you run your code? > > "I have many millions of 100K strings to compare against other 100K > strings, and string comparisons are O(1) so that will be fast." > > "I have many millions of 100K strings to compare against other 100K > strings, and string comparisons are O(N) so that will be slow, better > find another algorithm."
True. I can't think of a situation where I've used string comparisons directly in any text heavy code. Rather, I would use a dict or a set (or a regex) and hash(str) is always O(N). > > > Remember too that "for small enough N, everything is O(1)". Getting hung > up on Big Oh is just as much a mistake as ignoring it completely. > > I can't think of a situation in my own work where O(N) vs O(1) string comparisons would cause a significant problem (except perhaps in libraries that I use but didn't write). However, I can find a number of cases where I compare numpy.ndarrays for equality. For example, I found if np.all(a == b): in some code that I recently wrote. Although np.all() short-circuits, a==b does not so that line forces O(N) behaviour onto a situation where the average case can be better. Unfortunately numpy doesn't seem to provide a short-circuit equals() function. array_equal() is what I want but it does the same as the above. In future, I'll consider using something like def cmparray(a, b): return a.shape == b.shape and a.dtype == b.dtype and buffer(a) == buffer(b) to take advantage of (what I assume are) short-circuit buffer comparisons. >> Since string comparison is only useful if the strings can be equal or >> unequal, the average case depends on how often they are equal/unequal as >> well as the average complexity of both. For random strings the frequency >> of equal strings decreases very fast as N increases so that the >> comparison of random strings is O(1). > > But that is not an upper bound, and Big Oh analysis is strictly defined > in terms of upper bounds. It is an upper bound, but it is an upper bound on the *expectation value* assuming a particular distribution of inputs, rather than an upper bound on all possible inputs. >>> (I'm talking about the average here -- the actual number of comparisons >>> can range all the way up to N, but the average is <= 2.) The average is actually bounded by 1 / (1 - p) where p is the probability that two characters match. This bound can be arbitrarily large as p approaches 1 as would be the case if, say, one character was much more likely than others. The particular assumption that you have made p = 1/M where M is the number of characters is actually the *smallest* possible value of p. For non-uniform real data (English words for example) p is significantly greater than 1/M but in a strict bounds sense we should say that 1/M <= p <= 1. Oscar -- http://mail.python.org/mailman/listinfo/python-list