A string separator that doesn't separate if in quotes

Question

The sep function separates string by the characters of seps, but it escapes the separates that are in quotes, like:

>>> sep("a b c d 'e f' g h", ' ')

['a', 'b', 'c', "'e f'", 'g', 'h']

def sep(string: str, *seps: str):
    res = []
    cur = ""
    s = False
    for c in string:
        if c == "'": s = not s  # Q
        if not s and c in seps:
            res.append(cur); cur = ""
        else: cur += c
    res.append(cur)
    return res

I'm using this function for a while and it works great, but it gets really slow on long strings. Of course, because it loops through the whole string. I've trying to make it fast but I failed. So I want to know how the performance of my code can be improved.

Answer 1

There are a couple of different ways you might want to explore if you're looking for optimization opportunities here.

To start off, consider that if you have "a b c d 'e f' g h" as an input string, you can save yourself a potentially hefty amount of effort simply skipping over the entire quoted substring. In other words, if you start with text = "a b c d 'e f' g h" and you split it using the single quote as the separator, you immediately break off all of the pieces you don't need to process.

>>> text = "a b c d 'e f' g h"
>>> text.split("'")
['a b c d ', 'e f', ' g h']

From this point, all you really need to do is keep track of whether you're dealing with a quoted substring or not. If you are, just add it to the list of substrings (I added the single quotes around them like you did, although I'm not really sure what the purpose of that is). If you're not, go ahead and split the string using the separators like you normally would.

This is what I came up with. I actually started out with a super-complicated solution when I thought of the quoted-substring shortcut.

from string import whitespace
from typing import List, Text


def separate_substrings(input_string: Text, *separators: Text) -> List[Text]:
    """Split an input string based on the specified separators.
    
    The `separate_substrings` function correctly handles quoted substrings
    within the input string, returning the entire contents of a quote as a
    single quoted lexeme.

    Parameters
    ----------
    input_string : Text
        The `input_string` parameter contains the entire contents which are to
        be lexed.
    
    separators : text
        The `separators` argument is a list of delimiters which mark the end of
        one lexeme and the start of another.
    
    """
    # If the user forgets to specify the separators, the separators object will
    # be empty, and this will trigger a ValueException. To save everyone trouble
    # and heartache, if the separators object is empty, we will simply return
    # the input string as is.
    if not len(separators):
        # Just go ahead and return the input string as is without doing anything
        # to the input string first.
        return [input_string]

    # Initialize the partitions sequence container object.
    partitions: List[Text] = []

    # Determine whether the first non-separator character in the input string
    # is a quote character. This will determine how we alternate between
    # subgroups within the input string.
    for character in input_string:
        # Since the first thing we did was trim the input string, there should
        # be no need to skip whitespace. We're always looking out for trouble,
        # though, so you never know.
        if character in whitespace:
            # Move on to the next character in the input string until we hit
            # a non-whitespace character.
            continue
        
        # Make a note of wether the first character we hit is a quote.
        in_quote = True if character == "'" else False

        # Now that we've settled that, we can break out of this loop.
        break

    # You already know that the quote character is the
    # delimiter demarcating substrings, so simply split the
    # input string using the same quote character.
    substrings: List[Text] = input_string.split("'")

    # Iterate over the substrings of the input string and process all of the
    # input string partitions that are not quoted substrings.
    for substring in substrings:
        # Trim each substring before processing so we don't get stuck with zero-
        # length strings in-between elements here and there.
        substring = substring.strip()

        # Check whether we actually need to do anything for this substring. If
        # we're in a quoted substring, we can skip this step.
        if not in_quote:
            # First, split the substring using whitespace as the delimiter.
            for element in substring.split(*separators):
                # Add each individual element within the substring to the
                # input string partitions container.
                partitions.append(element)
        # If we are in a quoted substring, all we need to do is add it to the
        # input string partitions sequence container object.
        else:
            # Add the substring to the input string partitions container. I'm
            # not really sure why the quotes are necessary in and of themselves
            # (haven't they done their job by the mere fact that we didn't split
            # that substring?), but the question specifically included quotes
            # in the output, so here we go.
            partitions.append(f"'{substring}'")
        
        # Flip the sentinel value to make sure we do/don't process the next
        # substring, as necessary.
        in_quote = not in_quote

    # Now simply return the sequence container containing
    # the substring partitions.
    return partitions

With that initial heuristic out of the way, I think the next obvious step is to refactor the function as a generator. The resulting list could be absolutely massive depending on the size of your input string, and processing the entire thing to build a list means you basically need everything in memory at the same time.

This is a reworked version of my implementation from above, except I refactored it as a generator function.

from string import whitespace
from typing import Generator, List, Text


def separate_substrings(input_string: Text, *separators: Text) -> Generator:
    """Split an input string based on the specified separators.
    
    The `separate_substrings` function correctly handles quoted substrings
    within the input string, returning the entire contents of a quote as a
    single quoted lexeme.

    Parameters
    ----------
    input_string : Text
        The `input_string` parameter contains the entire contents which are to
        be lexed.
    
    separators : text
        The `separators` argument is a list of delimiters which mark the end of
        one lexeme and the start of another.
    
    """
    # If the user forgets to specify the separators, the separators object will
    # be empty, and this will trigger a ValueException. To save everyone trouble
    # and heartache, if the separators object is empty, we will simply return
    # the input string as is.
    if not len(separators):
        # Just go ahead and yield the input string as is without actually doing
        # anything to it.
        yield input_string

    # Determine whether the first non-separator character in the input string
    # is a quote character. This will determine how we alternate between
    # subgroups within the input string.
    for character in input_string:
        # Since the first thing we did was trim the input string, there should
        # be no need to skip whitespace. We're always looking out for trouble,
        # though, so you never know.
        if character in whitespace:
            # Move on to the next character in the input string until we hit
            # a non-whitespace character.
            continue
        
        # Make a note of wether the first character we hit is a quote.
        in_quote = True if character == "'" else False

        # Now that we've settled that, we can break out of this loop.
        break

    # You already know that the quote character is the
    # delimiter demarcating substrings, so simply split the
    # input string using the same quote character.
    substrings: List[Text] = input_string.split("'")

    # Iterate over the substrings of the input string and process all of the
    # input string partitions that are not quoted substrings.
    for substring in substrings:
        # Trim each substring before processing so we don't get stuck with zero-
        # length strings in-between elements here and there.
        substring = substring.strip()

        # Check whether we actually need to do anything for this substring. If
        # we're in a quoted substring, we can skip this step.
        if not in_quote:
            # First, split the substring using whitespace as the delimiter.
            for element in substring.split(*separators):
                # Return each individual element within the substring.
                yield element

        # If we are in a quoted substring, all we need to do is add it to the
        # input string partitions sequence container object.
        else:
            # Return the entire quoted substring. I'm not really sure why the
            # quotes are necessary in and of themselves (haven't they done their
            # job by the mere fact that we didn't split that substring?), but
            # the question specifically included quotes in the output, so here
            # we go.
            yield f"'{substring}'"
        
        # Flip the sentinel value to make sure we do/don't process the next
        # substring, as necessary.
        in_quote = not in_quote

The interface is a little less intuitive this way, but now that you don't need the entire input string or the list of lexemes in memory, the pros massively outweigh the cons, I think.

# Here's our trusty ol' sample input string.
text = "a b c d 'e f' g h"

# The return value of the function is now an iterator, not a list.    
separator_iterator = separate_substrings(text, " ")

# We don't even need to build the list of results, though, we can
# still iterate over the substrings, no problem.
for substring in separator_iterator:
    print(substring)

# Still, you could build a list if you wanted to.
separator_iterator = separate_substrings(text, " ")
lexemes = list(separator_iterator)

As expected, lexemes would contain ['a', 'b', 'c', 'd', "'e f'", 'g', 'h'].

From here, I think it's hard to say without knowing more about your specific environment, use case, and experience. My first thought was to go for an asynchronous generator implementation, but in all honesty I don't have enough experience with Python's async and asyncio tooling to pull it off in a reasonable amount of time. Still, I found a lot of really interesting avenues for exploration there.

Something you might do, for instance, is use an async iterator to split the input string and push the substrings onto a multiprocessing Queue, from which a Pool of independent processes gets their next substring and begins to process it.

Since the quoted substrings won't need to be split further, it might be a waste to pass them to the process pool, so you might forward them to the next point in the pipeline.

Another thing you might consider is using threads rather than processes. The ThreadPoolExecutor class is a subclass of the same Executor class from which ProcessPoolExecutor inherits, so making the switch is actually not horrible. I honestly don't know if there would be a benefit one way or the other, to be totally honest with you, but it's what I was going to try and compare when I realized I just didn't have time.

I think the biggest takeaway from the original version though is that you're forcing the interpreter to use a ton of RAM it really doesn't need, and you're not really taking advantage of your computer's ability to run multiple threads on multiple processors at the same time.

I'm really not sure how much more efficient the quoted substring heuristic is, really, but I think it's safe to say that at the very least, it is extremely dependent on the particular input string you're working with (specifically how many quoted substrings it contains, and how long they are), and thus it's probably not a game changer, but hey, you never know, I suppose.

Answer 2

Review

Structure

Placing multiple statements on one line using the semicolon ; or putting statements after the colon : in flow-control statements is to be eschewed. Don't do it.

Type hints

If you are going to use typehints, and you should, you should use the typehints for both parameters and return values. sep() has no return type. By inspection, it returns a list of strings, so the return type should be list[str] (or prior to Python 3.9, from typing import List and use List[str])

Naming

Your names cur, and res are very terse, but are acceptable (barely).

The variable s however is unacceptable. What is s? What does it mean? Lets examine the one and only comment where it is used: # Q. Well, that was completely and utterly unhelpful.

A much better name for s would be within_quote.

Resulting code

def sep(string: str, *seps: str) -> list[str]:

    result = []
    current = ""
    within_quote = False

    for ch in string:
        if ch == "'":
            within_quote = not within_quote
        if not within_quote and ch in seps:
            result.append(current)
            current = ""
        else:
            current += ch

    result.append(current)
    return result

This is immediately more readable.

Alternate implementation

The following regular-expression solution is close to the same behaviour as your code. It deviates when multiple spaces occur, or quoted terms are not surrounded by spaces. For you example case, however, it returns identical results.

import re

def sep(subject: str, *seps: str) -> list[str]:
    separators = re.escape("".join(seps))
    pattern = f"(?:'[^']+')|(?:[^{separators}]+)"
    return re.findall(pattern, subject)

if __name__ == '__main__':
    result = sep("a b c d 'e f' g h", ' ')
    print(repr(result))

Depending on your actual input requirements, it may or may not be sufficient for your needs.

Time comparisons

On strings with between 1 and one million terms, where a term is either a random "word" or a quoted string of 2-4 random words, and a random word is 1 to 7 random lowercase letters, I get the following time comparisons:

Once above strings of 10 words, my solution and Fernandez's solution are both faster than the original. While mine beats Fernandez's in conciseness, their solution is clearly faster.