Investigating the efficiency of counting and reversing a string

Overview

An analysis of the running time and run time of the assorted reverse_count functions implemented by team members.

Code

# Will's Implementation

def will_reverse_count(data: str):
    """Reverse the content of the provided string and return it in a mapping."""
    string = ""
    count = 0
    output = {}
    for letter in data:
        string = letter + string
        count = len(string)
    output[data] = count
    output["reversed_string"] = string
    return output

# Mordred's implementation of the function reverse_count

def reverse_str(data: str) -> str:
    """Reverse the content of the provided string."""
    reverse = ""
    for i in range(len(data)):
        reverse += data[-(i + 1)]
    return reverse

def mordred_reverse_count(data: str) -> dict:
    """Reverse the content of the provided string and return it in a mapping."""
    return {data: {"count": str(len(data)), "reversed": reverse_str(data)}}

# Chloe's implementation of the function reverse_count

### Function Implementation
def chloe_reverse_count(data: str) -> dict:
    """Reverse the content of the provided string and return it in a mapping."""
    reverse = data[::-1]
    return {data: {"count": str(len(data)), "reversed": reverse}}

# David's implementation of the function reverse_count

def david_reverse_count(data: str) -> dict[str, dict[str, str]]:
    """Reverse the content of the provided string and return it in a mapping."""
    count = str(len(data))
    reversed = data[::-1]
    result = {data: {"count": count, "reversed": reversed}}
    return result

# Luke's implementation of the function reverse_count

def luke_reverse_count(data: str) -> dict[str, dict[str]]:
    """Reverse the content of the provided string and return it in a mapping."""
    count = str(len(data))
    reversed_data = str(data[::-1])
    result = {data: {"count": count, "reversed": reversed_data}}
    return result

# Benedek's implementation of the function reverse_count

def benedek_reverse_count(data: str) -> dict:
    """Reverse the content of the provided string and return it in a mapping."""
    return {data: {"count": str(len(data)), "reversed": data[::-1]}}

# Completes the performance analysis
import timeit
import functools

performance_list = []
for i in timeit.repeat(
  stmt=functools.partial(will_reverse_count, "checking!"),
    number=10,
  ):
    performance_list.append(i)
print(
  f"Performance time in seconds for Will's implementation:\n {performance_list}"
)

performance_list = []
for i in timeit.repeat(
  stmt=functools.partial(mordred_reverse_count, "checking!"),
    number=10,
  ):
    performance_list.append(i)
print(
  f"Performance time in seconds for Mordred's implementation:\n {performance_list}"
)

performance_list = []
for i in timeit.repeat(
  stmt=functools.partial(chloe_reverse_count, "checking!"),
    number=10,
  ):
    performance_list.append(i)
print(
  f"Performance time in seconds for Chloe's implementation:\n {performance_list}"
)

performance_list = []
for i in timeit.repeat(
  stmt=functools.partial(david_reverse_count, "checking!"),
    number=10,
  ):
    performance_list.append(i)
print(
  f"Performance time in seconds for David's implementation:\n {performance_list}"
)

performance_list = []
for i in timeit.repeat(
  stmt=functools.partial(luke_reverse_count, "checking!"),
    number=10,
  ):
    performance_list.append(i)
print(
  f"Performance time in seconds for Luke's implementation:\n {performance_list}"
)

performance_list = []
for i in timeit.repeat(
  stmt=functools.partial(benedek_reverse_count, "checking!"),
    number=10,
  ):
    performance_list.append(i)
print(
  f"Performance time in seconds for Benedek's implementation:\n {performance_list}"
)

Performance time in seconds for Will's implementation:
 [1.1030999985450762e-05, 7.041999992907222e-06, 6.912999992891855e-06, 6.482000003416033e-06, 6.562000010035263e-06]
Performance time in seconds for Mordred's implementation:
 [1.4367000005677255e-05, 9.238000018285675e-06, 9.207000005062582e-06, 8.745999991788267e-06, 8.876999970652832e-06]
Performance time in seconds for Chloe's implementation:
 [6.2209999782680825e-06, 3.3870000493152475e-06, 3.3960000109800603e-06, 3.1350000426755287e-06, 3.1860000149208645e-06]
Performance time in seconds for David's implementation:
 [6.1210000126266095e-06, 3.6760000057256548e-06, 3.595999999106425e-06, 3.2369999871662003e-06, 3.31699999378543e-06]
Performance time in seconds for Luke's implementation:
 [6.792999954541301e-06, 3.797000033500808e-06, 3.475999960755871e-06, 3.4959999766215333e-06, 3.335999963383074e-06]
Performance time in seconds for Benedek's implementation:
 [5.900999951791164e-06, 3.4059999620694725e-06, 3.217000028143957e-06, 3.106000008301635e-06, 3.1459999831895402e-06]

Data Output

Will’s implementation

Performance time in seconds:
[7.916998583823442e-06, 5.457986844703555e-06, 5.333000444807112e-06, 5.207999492995441e-06, 5.250010872259736e-06]

Mordred’s implementation

Performance time in seconds:
 [3.950000018448918e-05, 2.3999999939405825e-05, 2.390000008745119e-05, 2.3800000235496555e-05, 2.3799999780749204e-05]

Chloe’s implementation

Performance time in seconds:[6.667338311672211e-06, 2.2919848561286926e-06, 2.1248124539852142e-06, 2.125278115272522e-06, 2.00001522898674e-06]

Benedek’s Implementation

first output:

Performance time in seconds:
 [5.699926987290382e-06, 2.900022082030773e-06, 2.7999049052596092e-06, 2.700020559132099e-06, 2.700020559132099e-06]

second output:

Performance time in seconds:
 [5.599926225841045e-06, 2.900022082030773e-06, 2.800021320581436e-06, 2.900022082030773e-06, 2.6999041438102722e-06]

third output:

Performance time in seconds:
 [7.4999406933784485e-06, 4.00003045797348e-06, 4.699919372797012e-06, 4.400033503770828e-06, 4.200031980872154e-06]

fourth output:

Performance time in seconds:
[7.79994297772646e-06, 3.100023604929447e-06, 2.900022082030773e-06, 2.700020559132099e-06, 2.7999049052596092e-06]

fifth output:

Performance time in seconds:
[6.299931555986404e-06, 3.00002284348011e-06, 2.800021320581436e-06, 2.800021320581436e-06, 2.6999041438102722e-06]

The code for getting the average of the outputs

class AverageOutput:
    def __init__(self):
        self.output = []

    def storing_output(self):
        first_output = [5.699926987290382e-06, 2.900022082030773e-06, 2.7999049052596092e-06, 2.700020559132099e-06, 2.700020559132099e-06]
        second_output = [5.599926225841045e-06, 2.900022082030773e-06, 2.800021320581436e-06, 2.900022082030773e-06, 2.6999041438102722e-06]
        third_output = [7.4999406933784485e-06, 4.00003045797348e-06, 4.699919372797012e-06, 4.400033503770828e-06, 4.200031980872154e-06]
        fourth_output = [7.79994297772646e-06, 3.100023604929447e-06, 2.900022082030773e-06, 2.700020559132099e-06, 2.7999049052596092e-06]
        fifth_output = [6.299931555986404e-06, 3.00002284348011e-06, 2.800021320581436e-06, 2.800021320581436e-06, 2.6999041438102722e-06]

        self.outputs = first_output + second_output + third_output + fourth_output + fifth_output
        return sum(self.outputs)
    
    def get_average(self):
        return sum(self.outputs) / len(self.outputs) if self.outputs else 0

The output of the function including the average performance time

Total: 9.539956226944923e-05
Average: 3.8159824907779695e-06

David’s Implementation

Performance time in seconds:
First Run: [1.09350003185682e-05, 8.03500006441027e-06, 7.890994311310351e-06, 7.889997505117208e-06, 7.848000677768141e-06]
Second Run: [1.1811032891273499e-05, 8.044764399528503e-06, 7.875263690948486e-06, 7.834285497665405e-06, 7.856637239456177e-06]
Third Run: [1.1026859283447266e-05, 8.003786206245422e-06, 7.811933755874634e-06, 7.797032594680786e-06, 7.810071110725403e-06]
Fourth Run: [1.1337921023368835e-05, 8.210539817810059e-06, 8.05780291557312e-06, 8.035451173782349e-06, 8.061528205871582e-06]
Fifth Run: [1.1313000868540257e-05, 8.074996003415436e-06, 7.907001418061554e-06, 7.907998224254698e-06, 7.911003194749355e-06]
Average: [1.1184569075043328e-05, 8.073418497881355e-06, 7.908197097374817e-06, 7.953013119930274e-06, 7.948352562959439e-06]

Luke’s Implementation

Performance time in seconds:
 [9.806000008438787e-06, 6.161999976939114e-06, 5.86999999541149e-06, 8.645999997725085e-06, 5.89299997955095e-06]

Analysis

Luke

The len() function and the str slicing both have a worst-case time complexity of \(O(n)\) so that would make the total worst case time complexity of the function be \(O(n)\). This means that the function grows at a linear rate based on the size of the input and the time it takes to execute the function.

Chloe

Based on the output above, the running time exhibits a worst case time complexity of \(O(n)\), otherwise described as a linear progression. This means that there is a linear relationship between the runtime of the function and the input size. I considered the costs of slicing the str (i.e., reverse = data[::-1]) and creating the dictionary with the len function involved (i.e., data: {"count": str(len(data)), "reversed": reverse}) as \(O(n)\). This suggests the total worst-case time complexity being the same.

The runtime of the function implementation above is displayed in the Output section. The average of the \(5\) output values is \(3.0418857932090757e-06\). Comparing the running time to the runtime results, it is indicated that as the string input data is increased, there will be a linear rate of growth. Graphically, this would be visualized with time on the horizontal axis and input size on the vertical axis; the curve would be a straight line with a positive slope.

Comparing the theoretical running time value and the empirical runtime results, indicate what I would expect. The growth is linear, however, the slope of the curve is rather flat and the values increase in small increments. This could be attributed to the speed of my laptop. Since mine runs rather fast, I would need to increase the input size drastically to see larger increases in runtime. However, I ran the function in a separate script and outputted the results to many decimal places and noticed a linear development is present.

Will

The time complexity of the reverse_count function is \(O(n)\), where \(n\) is the length of the input string. The code above shows that there is a linear growth in relation to the input size and the run time. In relation to that the run time shows that this code is the slowest and not the most efficient.

Conclusion

Despite the variety of implementations used, all had a worst-case time complexity of \(O(n)\). This shows that, in practice, where the differences between the methods were negligible, typically a difference of less than \(-05\) in the scientific notation. As such, the \(O(n)\) assumed from the implementations holds true and thus the methods do not have one being clearly more efficient than the others.