3
\$\begingroup\$

I have this algorithm that counts the frequency of character occurrence in a string, and outputs a new string based on that.

For example,

input = 'aabbcccaaa'
output = 'a5b2c2'

Here is my implementation in python

def compression(string):
    string = string.lower()
    freq_count = {}

    for index, char in enumerate(string):
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1

    return_string = ''
    for key in freq_count:
        return_string += key + str(freq_count[key])
    print(return_string)

    return return_string

compression('aabccccaaa')

My question is, am I making this algorithm less efficient by using dict to memoize values.

Also, I know that creating a new string takes up memory allocation, so is there a way to improve on that?

\$\endgroup\$
  • \$\begingroup\$ No. Your algorithm is efficient. The time complexity is O(n) where n is the length of the input string. More precisely, the time complexity of your algorithm is BigTheta(n). \$\endgroup\$ – ljeabmreosn Jun 14 '17 at 1:44
  • \$\begingroup\$ Your "compression" function is not deterministic (the order in which the characters are output is arbitrary), nor is it reversible (you cannot reconstruct the input from the output). Are these characteristics intentional? \$\endgroup\$ – 200_success Jun 14 '17 at 4:12
  • \$\begingroup\$ @200_success - Is it non-deterministic because the for in loop iterates randomly over dict key value pairs, and not in a sequential order? That is not by design. I need it to be deterministic. The reconstruction is not very important. \$\endgroup\$ – Zaid Humayun Jun 14 '17 at 4:34
  • 2
    \$\begingroup\$ If you want to preserve the insertion order, then you need an OrderedDict. \$\endgroup\$ – 200_success Jun 14 '17 at 4:56
1
\$\begingroup\$
def compression(string):

Naming can be hard, but it is important to get right. If I were to call compression('abcd'), I would expect the result length to be at-most the length of the input string. "compression" doesn't really describe what is happening within the function. So what exactly is your function doing? From your description:

I have this algorithm that counts the frequency of character occurrence in a string, and outputs a new string based on that.

A lot of nice verbs in that description you can use for a function name (serialize_frequencies?).


string = string.lower()

Does case-sensitivity have anything to do with your stated goals of calculating and serializing the frequency of characters? It depends on the context in which this function is used. Case-sensitivity isn't always required. If you really want to provide a mechanism for case-insensitive frequency generation, consider a toggle parameter or another function that transforms the input then calls this function.

serialize_frequencies(string, case_insensitive = False):
    if case_insensitive:
        string = string.lower()

    freq_count = {}

    for index, char in enumerate(string):
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1

A function that performs a single operation is simpler to understand, test, and reuse. Don't be afraid to break functions up into suitable logical parts and parameterize.

enumerate is a nice utility when you need to iterate through a sequence but also want to know the index. Since you don't need the index, you can just iterate through the string itself.

    for char in string:
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1

With that said, Python's collections includes a dictionary sub-class to count frequencies (Counter).

    freq_count = Counter(string)

    return_string = ''
    for key in freq_count:
        return_string += key + str(freq_count[key])

If you want to iterate a dictionary by its key-value pair, Python's built-in dictionary includes the method items().

    return_string = ''
    for key, value in freq_count.items():
        return_string += key + str(value)

You can write the loop that appends each pair using the string method join.

    return_string = ''.join(k+str(v) for k,v in freq_count.items())

    print(return_string)

Debugging artifact?


My question is, am I making this algorithm less efficient by using dict to memoize values.

No. But as 200_success has noted, calling compression('abcd') might result in 'a1b1c1d1' or 'c1d1b1a1' depending on the implementation. Ordering for the built-in dictionary is arbitrary and could change between implementations, versions, or possibly application executions. If ordering matters, then you should use a sorted container (OrderedDict, SortedDict) or manually sort the resulting dictionary before serializing.

|improve this answer|||||
\$\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.