CODEWITHSUNDEEP
python
Anders
Anders

Reputation: 115

Improving the time and space efficiency of my XOR program

This is quite a well known problem and the overall solution has been provided elsewhere but I'm trying to make my own way to my own solution if I can. The below code brings me the solution back in 10 seconds, which is slow but at very large parameters - I'm creating a numpy array and using the reduce function, so I'd be interested to hear other ideas for making it faster.

I think I've got the bigger problem that my length parameter can't get much bigger than this without hitting memory issues - I've tried it at 10,000 and crashed out - so I suspect I might have to do away with the arrays anyway?

import numpy as np
import timeit

def solution(start, length):
  checkArray = []
  for j in range(length):
    checkArray += [i for i in range(start, start+length)]
    start = start + length + j
    length -= 1
  checkArray = np.array(checkArray)
  checksum = np.bitwise_xor.reduce(checkArray)
  return checksum


start = timeit.default_timer()
solution(1500000000,9500)
stop = timeit.default_timer()

Upvotes: 3

Views: 148

Answers (2)

Anders
Anders

Reputation: 115

For completeness, I did find two for loops faster than creating the numpy array and calling reduce on it, however I did eventually have to swot up on XOR in order to hit the speeds necessary for the challenge. Rather than loop through and XOR every element individually, I wrote a function to calculate the XOR of each group of elements in one go, which obviously stripped out many operations at large scales.

Upvotes: 0

amdex
amdex

Reputation: 781

You don't need to build the array in its entirety to calculate the XOR. This is what leads to the memory issue. The solution below gives the same result without building any intermediate array (range is not an array or list, but defines a Generator), and (on my machine) is faster (~2.5 versus 5.33 seconds for your example input).

This also should not have any memory issues for any input, and does not require any external libraries.

def new_solution(start, length):
    a = 0
    for j in range(length):
        for x in range(start, start + length - j):
            a ^= x
        start += length
    return a

Upvotes: 2

Related Questions