String Comparison in Python: Is Vs. ==

Super fast way to compare if two strings are equal

(EDITED: to improve overall quality).

Considering how str == str is implemented in Python, this first gets an id() check, length check and then goes on element by element.
This is quite fast and understandably so, since a lot of Python code relies on this.
In the average case, there is no need for further optimization as arbitrary strings will be different quite early.

However, there are two use cases where there is some room for optimization:

• you have some partial information on how the two inputs are going to be different.
• you perform multiple comparisons among a certain set of elements (see @wim comments).

An example of the first situation is: if you know that when two inputs of the same size are different, they are likely different for at least m contiguous elements, then performing a comparison every k elements with k < m will be a reasonable bet, e.g.:

def is_k_equal(a, b, k=4096):
    if k in {0, 1}:
        return a == b
    else:
        return a[::k] == b[::k]


def is_equal_partial(a, b, partial_match=is_k_equal):
    return len(a) == len(b) and partial_match(a, b) and a == b

An example of the second situation is: if you want to know which p inputs out of q are pairwise equal, it may be beneficial to compute a hash (for example using hash(), but other options may be equally valid) of your inputs and only perform a full comparison when the hashes match.
It goes without saying that if your hash has high collision rating, it may just introduce additional overhead (see Wikipedia for information on hashing).
The hashes of the input could be either manually managed, or you could guard your full comparison with a hash comparison in a is_equal() function, e.g.:

def is_equal_hashing(a, b, hashing=hash):
    return len(a) == len(b) and hashing(a) == hashing(b) and a == b

provided that your hashing function is memoized. For hash() you do not need to do anything else, as this is already memoized for these inputs.
If you were to use a fancier hashing (e.g. crc32, md5, etc.), you may need to add memoization yourself, e.g with @functools.lru_cache.
The condition for this use-case seeing benefits from this approach (ignoring the time required to compare hashes which is usually much faster then the other operations to be considered) is:

t_h * n_h < t_c * n_c

with t_h the initial hash computation time, n_h the number of unique hashes to compute, t_c the comparison time, and n_c the number of full comparisons which fail near the end of the inputs.

When in doubt on how things will perform on your input, it is typically a good idea to measure / profile your code.

Care must be taken when timing memoized functions (like hash()), because, if you are interested in the performance of the non-memoized path, you cannot rely on timings of multiple repeated calls of the same input as it is typically done, for example with IPython's %timeit using default parameters. Instead, you may use %timeit -n1 -r1 for un-cached timings. The results would only be useful for order of magnitude estimates.

To give you some ideas on how fast the possible ingredients of your approach are, here are some micro-benchmarks:

import hashlib
import functools


def md5(data):
    return hashlib.md5(data).digest()


@funtools.lru_cache(maxsize=16384)
def sha1(data):
    return hashlib.sha1(data).digest()


def sha256(data):
    return hashlib.sha1(data).digest()


def sha512(data):
    return hashlib.sha1(data).digest()

import numpy as np
import numba as nb


@nb.jit(fastmath=True)
def hash_sum_nb(data, init=0):
    dtype = np.uint64
    nbytes = 8
    n = len(data)
    offset = n % nbytes
    result = init
    if offset:
        body = np.frombuffer(data[:-offset], dtype=dtype)
        tail = np.frombuffer(data[-offset:], dtype=np.uint8)
        for x in tail:
            result += x
    else:
        body = np.frombuffer(data, dtype=dtype)
    for x in body:
        result += x
    return result + n

import zlib
import string
import random


n = 1_000_000
s = b''.join(string.printable[random.randrange(len(string.printable))].encode() for _ in range(n))
funcs = hash, hash, zlib.crc32, zlib.adler32, md5, sha1, sha1, sha256, sha512, hash_sum_nb
for func in funcs:
    result = %timeit -n1 -r1 -q -o func(s)
    print(f'{func.__name__:>12s}  {result.best * 1e6:.3f} µs')
#         hash  586.401 µs
#         hash  0.853 µs
#        crc32  976.128 µs
#      adler32  468.452 µs
#          md5  1790.659 µs
#         sha1  1362.948 µs
#         sha1  1.423 µs
#       sha256  1347.432 µs
#       sha512  1321.981 µs
#  hash_sum_nb  64.768 µs


cases = {
    'worst case': (s[:-1] + b'x', s[:-1] + b'y'),
    'best case*': (s[:-1], s[:-2]),
    'best case': (b'x' + s[:-1], b'y' + s[:-1]),
}
for name, (a, b) in cases.items(): 
    result = %timeit -n1 -r1 -q -o a == b
    print(f'str == str ({name:10s})  {result.best * 1e6:.3f} µs')
# str == str (worst case)  142.466 µs
# str == str (best case*)  0.856 µs
# str == str (best case )  1.012 µs


a, b = (s[:-1] + b'x', s[:-1] + b'y')
result = %timeit -n1 -r1 -q -o is_k_equal(a, b)
print(f'{is_k_equal.__name__:>12s}  {result.best * 1e6:.3f} µs')
# is_k_equal  10.037 µs

Note that both hash() and sha1() are called twice on the same input to show the effects of memoization.

With this data (or similar numbers that you could produce on your input / system), it may be possible to craft a more performant string equality comparison.
Note that throughout the answer I used bytes instead.
The timings for str would generally be worse for most hashing, because of the additional overhead required to handle the encoding, with the notable exception of hash().

Differences among string comparisons in python, c++, c# and java

Since Java does not allow operator overloading, they had to resort to creating a function (Equals) to compare for 'true' objects equality - and leave operator == to perform pointer comparison. This choice can not be really justified by any other reason, as it warrants for illogical code, more typing in generalized case (people usually compare for true equality, not pointer equality) and steeper learning curve.

C++ with a clear distinction between pointer and an object is not constraint by Java limitations, and thus allows proper value-semantics for classes and intuitive forms of comparison.

How are strings compared?

From the docs:

The comparison uses lexicographical
ordering: first the first two items
are compared, and if they differ this
determines the outcome of the
comparison; if they are equal, the
next two items are compared, and so
on, until either sequence is
exhausted.

Also:

Lexicographical ordering for strings uses the Unicode code point number to order individual characters.

or on Python 2:

Lexicographical ordering for strings uses the ASCII ordering for individual characters.

As an example:

>>> 'abc' > 'bac'
False
>>> ord('a'), ord('b')
(97, 98)

The result False is returned as soon as a is found to be less than b. The further items are not compared (as you can see for the second items: b > a is True).

Be aware of lower and uppercase:

>>> [(x, ord(x)) for x in abc]
[('a', 97), ('b', 98), ('c', 99), ('d', 100), ('e', 101), ('f', 102), ('g', 103), ('h', 104), ('i', 105), ('j', 106), ('k', 107), ('l', 108), ('m', 109), ('n', 110), ('o', 111), ('p', 112), ('q', 113), ('r', 114), ('s', 115), ('t', 116), ('u', 117), ('v', 118), ('w', 119), ('x', 120), ('y', 121), ('z', 122)]
>>> [(x, ord(x)) for x in abc.upper()]
[('A', 65), ('B', 66), ('C', 67), ('D', 68), ('E', 69), ('F', 70), ('G', 71), ('H', 72), ('I', 73), ('J', 74), ('K', 75), ('L', 76), ('M', 77), ('N', 78), ('O', 79), ('P', 80), ('Q', 81), ('R', 82), ('S', 83), ('T', 84), ('U', 85), ('V', 86), ('W', 87), ('X', 88), ('Y', 89), ('Z', 90)]

Related Topics