S
Steven D'Aprano
Where's the fun in that?
Where's the fun in that?
O
Oscar Benjamin
Would you say, then, that dict insertion is O(N)?
I find this idea of separating into the comparison of equal strings versus the
comparison of unequal strings rather odd. If the strings you compare come from
a distribution where they are guaranteed to be equal (or unequal) then you can
just use the O(0) comparison method.
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).
I'm not sure where the extra N comes from --------^ but otherwise good.
I would have written that as:
(1 - p) * sum(i * p**(i-1) for i in range(1, N+1))
where p is the probability of a match (1/M for M equally likely characters) or
in closed form:
⎛ N ⎞
âŽ1 - p â‹…(1 + N â‹…(1 - p))âŽ
─────────────────────────
1 - p
It approaches 1 / (1 - p) or, if you prefer: M / (M - 1)
Oscar
O
Oscar Benjamin
Ok, I see it's for the case where they're equal.
Oscar
S
Steven D'Aprano
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."
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.
If you know that they're (un)equal, you don't need to call == at all.
If you know that "most" strings will be unequal, then you might be
justified in treating comparisons as O(1) "most of the time" and not
stress about the occasional slow call. But of course most of the time you
don't know this, which is why it is appropriate to treat string
comparisons as O(N) rather than O(1), since that's the upper bound.
But that is not an upper bound, and Big Oh analysis is strictly defined
in terms of upper bounds.
The extra N comes from the case where you compare string S with itself,
which takes exactly N comparisons.
O
Oscar Benjamin
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).
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.
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.
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
G
Gelonida N
Yeah I think you mixed it up with searching an entry in an unsorted list
of length N
That's one of the most common N/2 cases, that one hits daily with many
straight forward implementations
G
Gelonida N
The worst case is O(N) or N characters
the average case is O(1) or two characters.
For denial of service attacks or systems, that are NEVER allowed to fail
the worst case is important.
For most other cases the average complexity counts.
However I still wonder for how many applications the complexity of
string comparisons would be the limiting factor.
S
Steven D'Aprano
There are other good reasons for interning strings, but speeding up
"astring == bstring" is not one of them.
[steve@ando ~]$ python -m timeit -s "s = 'abc'*100000" -s \
1000 loops, best of 3: 910 usec per loop
[steve@ando ~]$ python -m timeit -s "s = 'abc'*100000" -s \
1000 loops, best of 3: 914 usec per loop
No significant difference.
To state the bleedin' obvious, the computational effort required to
*compare two strings* pre-supposes that those strings already exist, and
is *completely independent* of the complexity of creating the strings.
Not necessarily.
Look, it's really hard to come up with a realistic, non-contrived example
where string comparisons are a significant bottleneck in a non-toy
application. So let me first off say that *nearly always* you're not
going to care whether "s == t" looks at all N characters or just the
first 2 (or 20, or 100). This argument is rather academic (the best sort
of argument!). Until you start getting up into truly huge strings, we're
arguing about how many angels can dance on a CPU cache.
But for the record, in principle string comparisons *could* be the
bottleneck. Example: you have 10000 strings, which are each created once
and stored in a list. Then you iterate over the list, comparing every
string against every other string. And due to some weird vagary of the
data, the strings are nearly all equal.
(Why would you do this? I don't know, maybe it's a programmers' challenge
found on the Internet, make up your own scenario...)
Total number of strings created: 10000.
Total number of strings compared: 100000000.
The overhead of creating the strings is trivial compared to the overhead
of comparing them, and since each string is only created once anyway,
interning them is just a waste of time.
What interning buys you is that "s == t" is an O(1) pointer compare if
they are equal. But if s and t differ in the last character, __eq__ will
still inspect every character. There is no way to tell Python "all
strings are interned, if s is not t then s != t as well".
O
Oscar Benjamin
I thought that if *both* strings were interned then a pointer comparison could
decide if they were unequal without needing to check the characters.
Have I misunderstood how intern() works?
Oscar
C
Chris Angelico
In a language where _all_ strings are guaranteed to be interned (such
as Lua, I think), you do indeed gain this. Pointer inequality implies
string inequality. But when interning is optional (as in Python), you
cannot depend on that, unless there's some way of recognizing interned
strings. Of course, that may indeed be the case; a simple bit flag
"this string has been interned" would suffice, and if both strings are
interned AND their pointers differ, THEN you can be sure the strings
differ.
I have no idea whether or not CPython version X.Y.Z does this. The
value of such an optimization really depends on how likely strings are
to be interned; for instance, if the compiler automatically interns
all the names of builtins, this could be quite beneficial. Otherwise,
probably not; most Python scripts don't bother interning anything.
ChrisA
O
Oscar Benjamin
I haven't looked at the source but my understanding was precisely that there
is an intern() bit and that not only the builtins module but all the literals
in any byte-compiled module are interned.
Oscar
O
Oscar Benjamin
s/literals/identifiers/
You can see the interned flag in the PyUnicodeObject struct here:
http://hg.python.org/cpython/file/3ffd6ad93fe4/Include/unicodeobject.h#l303
Oscar
C
Chris Angelico
Ah, yep, so that's there. In that case, it's possible to have that
optimization. However, I may be misreading this, but it seems the only
Unicode comparison function is a rich compare, which is unable to take
advantage of a known difference:
http://hg.python.org/cpython/file/b48ef168d8c5/Objects/unicodeobject.c#l6114
Different pointers prove the strings differ, but don't tell you which
is to be sorted earlier. You could use this if you roll your own
comparison in C; or, if you already know the strings are interned, you
can use 'is' / 'is not'. But that seems to be the extent of it.
ChrisA
D
Dan Goodman
From the rest of the thread, it looks like in most situations it won't
make much difference as typically very few characters need to be
compared if they are unequal.
However, if you were in a situation with many strings which were almost
equal, the most general way to improve the situation might be store a
hash of the string along with the string, i.e. store (hash(x), x) and
then compare equality of this tuple. Almost all of the time, if the
strings are unequal the hash will be unequal. Or, as someone else
suggested, use interned versions of the strings. This is basically the
same solution but even better. In this case, your startup costs will be
higher (creating the strings) but your comparisons will always be instant.
Dan
O
Oscar Benjamin
Computing the hash always requires iterating over all characters in the string
so is best case O(N) where string comparison is best case (and often average
case) O(1).
Also, so far as I know the hash value once computed is stored on the string
object itself [1] and used for subsequent string comparisons so there's no
need for you to do that in your code.
Oscar
[1] http://hg.python.org/cpython/file/71d94e79b0c3/Include/unicodeobject.h#l293
D
Dan Goodman
Yep, but you already have O(N) costs just creating the strings in the
first place, so it's absorbed into that. It's only worth doing if you do
many comparisons.
Cool, Python is very clever as always!
Dan
D
Dan Goodman
Just had another thought about this. Although it's unlikely to be
necessary in practice since (a) it's rarely necessary at all, and (b)
when it is, hashing and optionally interning seems like the better
approach, I had another idea that would be more general. Rather than
starting from the beginning or the end, why not do something like: check
the first and last character, then the len/2 character, then the len/4,
then 3*len/4, then len/8, 3*len/8, etc. You'd need to be a bit clever
about making sure you hit every character but I'm sure someone's already
got an efficient algorithm for this. You could probably even make this
cache efficient by working on cache line length blocks. Almost certainly
entirely unnecessary, but I like the original question and it's a nice
theoretical problem.
Dan
O
Oscar Benjamin
It's not totally theoretical in the sense that the reasoning applies to all
sequence comparisons. If you needed to compare lists of objects where the
comparison of each pair of elements was an expensive operation then you would
want to think carefully about what order you used. Also in general you can't
hash/intern all sequences.
If I was going to change the order of comparisons for all strings then I would
use a random order. This is essentially how dict gets away with claiming to
have O(1) lookup. There are sequences of inputs that can cause every possible
hash collision to occur but because the hash function acts as a kind of
randomisation filter the pathological sequences are very unlikely to occur
unless someone is going out of their way. The clever way that Python 3.3
prevents someone from even doing this on purpose is just to introduce
additional per-process randomisation.
The difference between dict lookup and string comparison is that string
comparison always compares the characters in the same order and it corresponds
to the natural ordering of the data. This means that some pefectly natural use
cases like comparing file-paths can have close to worst case behaviour. If
string/sequence comparison occurs in a random order then there can be no use
case where the likely strings would induce close to worst case behaviour
unless you really are just comparing lots of almost identical sequences.
Oscar
T
Terry Reedy
I believe the internal use of interning and hash comparison has varied
from release to release. However, the main use of string comparison is
for dict keys, especially the internal dicts for namespaces and
attributes. Since the dict lookup code needs hash values anyway, to find
slots with possible conflicts, I am sure it does not use the generic
comparison operators but starts with hash comparisons.
Terry Jan Reedy
P
Prasad, Ramit
Dwight said:
What? Without context I have no idea what this means.
Ramit
--
This email is confidential and subject to important disclaimers and
conditionsincluding on offers for the purchase or sale of
securities, accuracy and completeness of information, viruses,
confidentiality, legal privilege, and legal entity disclaimers,
available at http://www.jpmorgan.com/pages/disclosures/email.