Sorting a long string with a composite of strings and integers + symbols

Question

The code below is to sort a file containing the following info (eg. input.txt):

rango burrito apri%cot 1 -10 3.5 8 5 tesla 10 hyphen -4.7 2 bus 20 cat vul$ture m0nkey -9999999

The output should have the symbols removed and then strings and integers sorted in ascending order, but the order retaining the type of the original list. for example, the first item is a string in both input and output and the final item for example is an int.

When the script is run the output looks as follows:

$ ./sort_input.py input.txt
apricot burrito bus -9999999 -47 -10 1 2 cat 5 hyphen 8 10 m0nkey 20 rango tesla vulture 35

I've written code that looks as follows and I'm sure this can be improved a lot:

Reading the file first, then splitting on white space into an array of strings: \$O(n)\$ complexity where \$n\$ is the length of the original string

def listify(input_file):
    with open(input_file) as f:
        for line in f:
            list_of_strings = line.strip().split()

    return list_of_strings

Using the list of strings and converting it into a typed list, but removing any symbols first using the method below: \$O(n)\$ complexity for the typed list, then \$O(k)\$ for each string in that list to remove symbols - so total complexity is \$O(n)*O(k)\$.

def typed_list(untyped_list):
    """ converts an untyped list to a typed list of strings and integers """
    typed_list = []
    for item in untyped_list:
        item_without_symbol = remove_any_symbols(item)
        try:
            typed_list.append(int(item_without_symbol))
        except ValueError:
            typed_list.append(item_without_symbol)

    return typed_list

Method to remove any symbols, which I use in the function above. \$O(k)\$ complexity where \$k\$ is the length of the string:

def remove_any_symbols(s_string):
    """We take a string and remove any symbols from it. """
    acceptable_characters = string.ascii_letters + string.digits
    no_s_string_list = [c for c in s_string if c in acceptable_characters]
    if s_string.startswith("-"):
        return "-"+''.join(no_s_string_list)
    else:
        return ''.join(no_s_string_list)

I then use the typed list that's generated above to sort integers and strings separately. Then using the original list to generate a list with the same type items in their original order. \$O(n log n)\$ complexity for both sorting functions and then \$O(n)\$ for adding to the final output list.

def sort_em_up(no_symbol_list=None):
    """we take a list here, note the type, sort and then return a sorted
    list"""
    sorted_int = sorted([int(i) for i in no_symbol_list if isinstance(i, int)])
    sorted_str = sorted([s for s in no_symbol_list if isinstance(s, str)])
    final_sorted_list = []
    i = j = 0
    for item in no_symbol_list:
        if isinstance(item, int):
            final_sorted_list.append(str(sorted_int[i]))
            i += 1
        else:
            final_sorted_list.append(sorted_str[j])
            j += 1

    return ' '.join(final_sorted_list)

if __name__=="__main__":
    input_file = sys.argv[1]

    list_of_strings = listify(input_file)

    print(sort_em_up(typed_list(list_of_strings)))

Answer 1

listify function

Since, as you mentioned in the comments, the function is meant to read a single first line from a file only - you can use the next() built-in function:

def listify(filename):
    """Reads the first line from a file and splits it into words."""
    with open(filename) as input_file:
        return next(input_file).strip().split()

remove_any_symbols function

You can actually pre-define the allowed characters as a constant - no need to re-define them for every function call. You can also make it a set for faster lookups:

ACCEPTABLE_CHARACTERS = set(string.ascii_letters + string.digits)

def remove_any_symbols(input_string):
    """Removes any symbols from a string leaving the leading dashes."""
    filtered_characters = [c for c in input_string if c in ACCEPTABLE_CHARACTERS]
    prefix = "-" if input_string.startswith("-") else ""
    return prefix + ''.join(filtered_characters)

Or, a regex-based version (less understandable overall, but see if it is going to be faster):

PATTERN = re.compile(r"""
    (
        (?<!^)-  # dash not at the beginning of a string
        |  # or
        [^A-Za-z0-9\-]  # not letters, digits and dashes
    )+
""", flags=re.VERBOSE)
def remove_any_symbols(input_string):
    """Removes any symbols from a string leaving the leading dashes."""
    return PATTERN.sub("", input_string)

Pre-process the complete string

With regexes, it would also be possible to pre-process the input string as a whole, checking for the dashes at the beginning of words. This may lead to applying remove_any_symbols() on the complete input string read from a file:

PATTERN = re.compile(r"""
    (
        (?<!(?:^| ))-  # dash not at the beginning of a word
        |  # or
        [^A-Za-z0-9\- ]  # not letters, digits, dashes and spaces
    )+
""", flags=re.VERBOSE)
def remove_any_symbols(input_string):
    """Removes any symbols from a string leaving the leading dashes for each word."""
    return PATTERN.sub("", input_string)


if __name__=="__main__":
    input_file = sys.argv[1]

    with open(input_file) as f:
        data = next(f).strip()

    list_of_words = remove_any_symbols(data).split()

    print(sort_em_up(typed_list(list_of_words)))