1
\$\begingroup\$

I've written what I think is a constant time implementation of a uniqueness check. I've seen many algorithms online, which run in linear time, but was wondering whether my conclusion that this runs in constant time was correct.

I've seen many linear versions of this algorithm, but I haven't seen any that run in O(1).

Any feedback on style, flaws in the code, or how to improve the algorithm would be greatly appreciated.

from string import printable 


def is_unique(string):
    """Checks whether a string is unique or not.

    Big O:

      O(S * C) - Constant Time

      Where:

        `S` is the characters of the string being checked for uniqueness
        `C` is a set of all ASCII characters (not including the extended set)

    """
    if len(string) == 1:
        # A single character is always going to be unique
        return True

    if len(string) > len(printable):
        # If there are more characters than the ASCII character set, 
        # then we know there are duplicates
        return False

    found_character = bytearray(len(printable))

    for character in string:
        for index, ascii_value in enumerate(printable):
            if character == ascii_value:
                if found_character[index] == True:
                    return False

                # Set the index of the ASCII value in our bytearray to True
                found_character[index] = 1
                break

    return True


is_unique(string='abc')
\$\endgroup\$
  • 3
    \$\begingroup\$ your code is definitely not in \$O(1)\$. for character in string is a linear operation \$\endgroup\$ – Vogel612 Jul 20 at 13:21
  • \$\begingroup\$ string has a maximum length of 100, since I return False if the length of the string exceeds 100. We know it cannot unique, since there are only 100 distinct ASCII characters. The notation, strictly speaking is \$O(100 * 100)\$. This isn't strictly true, however, since the worst case for this algorithm is passing in a reversed version of printable from the string module. Even then, it will only do 5,500 operations and not the full 10,000. \$\endgroup\$ – Tom Cusack-Huang Jul 20 at 13:39
  • 1
    \$\begingroup\$ just because the problem statement allows you to define an upper limit, that doesn't mean the algorithm's complexity suddenly changes... \$\endgroup\$ – Vogel612 Jul 20 at 13:43
  • \$\begingroup\$ So you're suggesting the runtime is \$O(M * 100)\$? Where M has a length between 1 and 100 inclusive? \$\endgroup\$ – Tom Cusack-Huang Jul 20 at 14:06
  • \$\begingroup\$ With a for in a for, it's probably worse. Might be quadratic. Besides, you're looking to eliminate N, not M. \$\endgroup\$ – Mast Jul 21 at 14:37
2
\$\begingroup\$

Critique

You have to describe something for which your input scale, which in this would be the length of your string, so in this regard your implementation is still linear. The part where you try every single possible index for storing a specific character is overkill, since it is often possible to directly calculate it through some kind of hashing. It would therefore be much faster to use a dictionary or the equivalent.

Alternative

We can solve this problem very simply for a more general case (any sequence of items is unique) by turning it into a set:

is_unique = lambda xs: len(xs) == len(set(xs))

Note that you might want to do some extra work if you want to only have printable characters, such as by applying a filter first.

\$\endgroup\$
  • \$\begingroup\$ Thanks for this Ninetails. This was my initial brute force. I'm trying to optimise from this. Casting a string to a set() is a linear operation, as you have to go over the whole string. There are only 100 characters in the ASCII character set, so it's arguably a pointless optimisation, but imagine the input string is aa, this would take 2 operations. \$\endgroup\$ – Tom Cusack-Huang Jul 20 at 11:04
  • \$\begingroup\$ I did a quick benchmark. Using set() is an order of magnitude faster than using a Boolean array to keep track of seen characters, which surprises me, considering I was trying to improve upon the set() method. 267 µs - Above function 2.21 µs - Using set() \$\endgroup\$ – Tom Cusack-Huang Jul 20 at 11:13
  • \$\begingroup\$ It should be possible to do it faster than a full cast to sets in theory, since you can end early if you find subluxated, the problem is that sets are part of the core of the language, and it is therefore heavily optimized and likely written in a faster language, so even if you use strictly less operations a full cast to a set might still be faster for most cases. \$\endgroup\$ – Ninetails Jul 20 at 11:42
0
\$\begingroup\$

I like the way your function is documented by a doc string and comments.

Why use the inner loop?
If you want another "early out" compared to "the set approach", use a map and "index" that with the characters.

You compare found_character[index] to True, but set it to 1, which is all the more irritating as it is commented Set […] to True

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.