XORing long strings opimization?

[Miika Keskinen]

On Tue, 04 Nov 2003 22:33:52 +0000, Noen wrote:

>>  alist = [chr(x ^ y) for x in ord1 for y in ord2]
>> 
>> This creates a way too big list... Im not familiar with two for loops in 
>> one, so I cant see whats wrong :(
>> 
> Oh, my debugger says that it works like:
> for x in range ord1:
> 	for y in range ord2:
> 		chr(x^y)
> which does it x*y times...
> 
> wonder how the line really should look like...


I've had similar needs and used following code:

reduce(lambda x, y: x+y, map(chr, [ord(x)^ord(y) for x, y in
	zip("string1", "string2")]))

dunno if this is optimal but it is anyways simple quick hack. If one is
going to handle large amounts of data it should be done in parts to avoid
memory issues.

for some analysis 
zip will do O(n) in space and O(n) and O(n) in speed.
ord(x) ^ ord(y) for x, y will do O(n) in space and O(n) in speed
map chr will do O(n) in space and O(n) in speed
lambda x, y: x+y will do O(n) in space and O(n) in speed.

So my conclusion (correct me if I'm wrong) this method will run in O(n)
space and O(n) time.


-- 
Miika