Saturday, 18 January 2020

Python string rotation - a post on optimising loop and runtime


Need for optimising code with respect to iterations or loops can be demonstrated with a below example :-

Taking an example below :-


string="abcd"
leftshift_count = 40000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


case_1 = leftshift_count % len(string)
case_2 = leftshift_count

#BLOCK 1
print ("Case1")
for i in xrange(case_1):
  temp = string[0]
  string = string[1:len(string)]+temp

print("Shifted string {str}".format(str=string))



#BLOCK 2
print ("Case2")
for i in xrange(case_2):
  temp = string[0]
  string = string[1:len(string)]+temp

print("Shifted string {str}".format(str=string))



Here  Block 1 and Block 2 performs the same operation , but when executing ,

Case1
Shifted string abcd
Case2
Traceback (most recent call last):
  File "leftshift.py", line 20, in <module>
    for i in xrange(case_2):

OverflowError: Python int too large to convert to C long


Case 2 throws an error .

from the above program , which left shifts a string , abcd if left shifted 4 time gives abcd itself , so any multiples of the number of shifts rotates the string to itself so we just need to simplify that to see how many times we do the shift. 


So what i wanted to bring out of this is , every bigger problem has a solution in itself , there is a path for optimisation. Try to divide the problem into smaller parts and solve the smaller problem , the solution that you bring out of that will be optimal. 


No comments:

Post a Comment