CODEWITHSUNDEEP
python
ZouJS
ZouJS

Reputation: 5

Why WHILE is more efficient than FOR in this python function

SUBJECT: Given a string, find the length of the longest substring without repeating characters. CODE:

import time
import string
import random

class Solution:


    def getRandomStr(self,length):
        s = ""
        for x in range(0,length):
            s += random.choice(string.ascii_letters+string.digits)
        return s

    # O(n)
    def hasValue(self,s,v,p,r):
        for k in range(p,r+1):
            if s[k] == v:
                return True
        return False

    # O(n^3)
    # if s[j] is found in prestr , 
    def lengthOfLongestSubstringWhile(self,s):
        
        maxlen = 0
        i = 0
        j = 0
        exitsign = False
        t0 = time.clock()
        while i < len(s):
            j = i+1
            while j < len(s):
                if self.hasValue(s,s[j],i,j-1):
                    maxlen = max(maxlen,j-i)
                    break
                elif j == len(s)-1:
                    maxlen = max(maxlen,j-i+1)
                    exitsign = True
                    break
                j+=1
            if exitsign:
                break
            i+=1
        # print maxlen

    def lengthOfLongestSubstringFor(self,s):
        maxlen = 0
        exitsign = False
        for i in range(0,len(s)):
            for j in range(i+1,len(s)):
                if self.hasValue(s,s[j],i,j-1):
                    maxlen = max(maxlen,j-i)
                    break
                elif j == len(s)-1:
                    maxlen = max(maxlen,j-i+1)
                    exitsign = True
                    break 
            if exitsign:
                break
        # print maxlen

    
S = Solution()
s = S.getRandomStr(10000)

t0 = time.clock()
S.lengthOfLongestSubstringWhile(s)

t1 = time.clock()
S.lengthOfLongestSubstringFor(s)
t2 = time.clock()

print t1-t0,t2-t1

This is the result:

0.187118

0.868182

Finished in 1.2s

Why the function with while is more quick than the one with for?

Upvotes: 0

Views: 71

Answers (1)

Bill Gribble
Bill Gribble

Reputation: 1797

For one thing, range is generating and throwing away a ton of arrays of numbers as loop indexes in the "for" version. Like, 10000 arrays averaging 5000 items each. Try replacing range with xrange (the generator version) and you won't do that as much.

Upvotes: 2

Related Questions