Why WHILE is more efficient than FOR in this python function

Question

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?

This is not very idiomatic Python, I guess your first language is C-like. For example, instead of for i in range(0, len(s)) we write for i, char in enumerate(s) — Paulo Scardine
– Paulo Scardine, Commented Nov 9, 2016 at 11:21

Bill Gribble · Accepted Answer · 2016-11-09 11:15:31Z

2

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.

answered Nov 9, 2016 at 11:15

Bill Gribble

1,79712 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ZouJS Over a year ago

I did it as you say, and it's fixed up.Thank you very much!

Bill Gribble Over a year ago

If you could "accept" my answer that would be great :)

ZouJS Over a year ago

it's my first time to use stackoverflow.so how can I accept it?

Collectives™ on Stack Overflow

Why WHILE is more efficient than FOR in this python function

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related