Python, why is it faster to do a replace and turn to upper first than to just iterate once through?


  • 1
    D

    Why is this algorithm

        S = S.replace('-','').upper()
        
        i = len(S)%K if len(S)%K else K
        ans = S[:i]
        while i <= len(S)-K:
            ans += '-' + S[i:i+K]
            i += K
        
        return ans
    

    faster than

        rev = ''
        curr = ''
        S = S.strip('-')
        for i in xrange(len(S)):
            if S[~i] != '-':
                curr += char.upper()
            if len(curr) == K:
                rev += curr
                if i != len(S)-1:
                    rev += '-'
                curr = ''
        if curr: rev += curr
        
        return rev[::-1]
    

    The first one does two operations to the entire string at the very beginning and then iterates through it again. I would think that this would be slower than the second algorithm, which really only iterates through the string once (granted I'm not sure what the time complexity of reversing a string for the return would be). Why is the first one so much faster (about 1/3 the running time)? Is it because replace and upper are written in native C?


  • 1
    X

    Yes you are right, replace are upper are so much faster because they are written in C. Condition statements and compare operators are much slower in Python.
    Also, you might notice that your second algorithm also go through the whole string one extra time when reversing it in the end.


  • 0
    D

    @xueguang
    Yes I thought that the [::-1] might also be O(n) but that it would at least be a very fast iteration as it did nothing to each element. In any case, the key is that replace and upper are written in C. Thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.