CODEWITHSUNDEEP
pythonperformancecomplexity-theoryxor
Rockybilly
Rockybilly

Reputation: 4520

Fastest way to xor all integers in a string

I am trying to find the fastest way of xor'ing all integers(numerals actually) in a string consecutively. The problem makes me feel that there is an simple and a fast answer I just can't think of. But here what I came up with so far.

Setup:

from operator import xor
a = "123"

I expected the second one to be faster but when the string grows, the difference is almost none. Is there a faster way ?

Note1: And I would like to know if it is possible using just the integer as 123 instead of the string "123". That would be unlogical because I need a list of integers, however sometimes interesting answers appear from places you never expect.

Edit: Here is the results from the methods suggested so far.

import timeit

setup = """
from operator import xor

a = "124"
b = 124
"""

p1 = """
val = 0
for i in a:
    val = val ^ int(i)
val
"""

p2 = """
reduce(xor, map(int, list(a)))
"""

p3 = """
val = 0
for i in xrange(3):
    val = val ^ (b % 10)
    b /= 10
val
"""

p4 = """
15 & reduce(xor, map(ord, a))
"""
print 1, timeit.timeit(p1, setup=setup, number = 100000)
print 2, timeit.timeit(p2, setup=setup, number = 100000)
print 3, timeit.timeit(p3, setup=setup, number = 100000)
print 4, timeit.timeit(p4, setup=setup, number = 100000)

# Gives
1 0.251768243842
2 0.377706036384
3 0.0885620849347
4 0.140079894386

Please also note that using int(a) instead of b in process 3 makes it slower than 4.

Upvotes: 0

Views: 1621

Answers (1)

cdlane
cdlane

Reputation: 41905

On my (Python 3) system, this rework of the solution runs measureably faster than those shown:

from operator import xor
from functools import reduce

print(15 & reduce(xor, map(ord, a)))

If we know they are all digits, 15 & ord('5') pulls out the bits we need with less overhead than int('5'). And we can delay the logical "and", doing it just once at the end.

To use a number instead of a string, you can do:

b = 31415926535897932384626433832795028841971693993751058209749445923078164

val = 0

while b:
    b, modulo = divmod(b, 10)
    val ^= modulo

print(val)

Upvotes: 1

Related Questions