Geek Answers Handbook

Why is a large integer division faster than string (numeric) strings to access individual digits?

I fulfill a (typical) prime search assignment. I thought I would be smart and, for large numbers, skip the division process with this trick:

def div5(candidate):
    return str(candidate)[-1] == "5"

Adding 5 to yourself a few thousand times seems like a waste (I only need the last item), but I wanted to be sure.

unutbu credit for measuring time elapsed in python?

%>python -mtimeit -s"import intDiv" "intDiv.div5(2147483645)"
1000000 loops, best of 3: 0.272 usec per loop

%>python -mtimeit -s"import strDiv" "strDiv.str5(2147483645)"
1000000 loops, best of 3: 0.582 usec per loop

For clarification, here are two methods that I have defined.

def div5(maxi): return not (maxi%5)

def str5(maxi): return str(maxi)[-1] == '5'

It is too slow. How can I parse the last member of str (maxi) without converting the whole number (unnecessarily)?

Thanks to @Claudiu for helping me clean my eyes.

+5
source share
3
% python -mtimeit "str(2147483645)"
1000000 loops, best of 3: 0.321 usec per loop

% python -mtimeit "2147483645 % 5"
10000000 loops, best of 3: 0.0351 usec per loop

% python -mtimeit "'2147483645'[-1]"
10000000 loops, best of 3: 0.0349 usec per loop

, .

+10

. , . , Python,

def tostring(value):
    result = ""
    while True:
        digit = value % 10
        value = value / 10
        result = chr(digit + ord('0')) + result
        if value == 0: break

    return result

value.

+5

Converting a number to a string will look something like this:

digits = []
while x:
    digits.append(x % 10)
    x //= 10

You can see that this will do a lot of% operations (except for building a list of numbers or a string).

Besides this optimization problem, your function is incorrect. For example, 10 does not end with 5, but divides by 5.

0
source

More articles:


All Articles