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.
O(n)
wheren
is the length of the input string. More precisely, the time complexity of your algorithm isBigTheta(n)
. \$\endgroup\$OrderedDict
. \$\endgroup\$dict
in Python 3.7 is guaranteed to preserve the key insertion order. In practice, this is also true of CPython 3.6. \$\endgroup\$