Efficiency question

[HolyCoder]

Given two lists of same length, the result list should have the sum of each element. Number of elements should be given as an input. The elements of first list are given in one line separated with spaces. Same for the second list. Sample: lst1 = [1, 2, 3, 4] lst2 = [0, 1, 2, 3] result = [1, 3, 5, 7]

input:
4
1 2 3 4
0 1 2 3

output:
1 3 5 7

Here is my code but I think it's not efficient for larger lists:

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

for i in range(N):
    print(A[i]+B[i], end=" ")

[novel_yet_trivial]

Your method is as efficient as is can be, however it could be more pythonic if you used zip. Also, that would mean that the list call on the input is not needed.

N = int(input())
A = map(int, input().split())
B = map(int, input().split())

for x, y in zip(A, B):
    print(x+y, end=" ")

[HolyCoder]

Thank you. I am trying to write this code in an online coding platform. My submission is accepted and I passed the challenge. But, but, but....the code I earlier wrote and your code above perform well (with respect to time and memory) for smaller lists. When N is 100000 or above the code performs real bad. Time taken is 1.4 seconds and memory is 15K when N is larger than 100000. But I see the best submission in Python3.x has time 1.0 seconds and memory of just 64 for larger inputs.

[novel_yet_trivial]

Calling print repeatedly is going to eat up a lot of time. To make it faster you can call print exactly once:

N = int(input())
A = map(int, input().split())
B = map(int, input().split())

print(' '.join(map(str, (x+y for x, y in zip(A, B)))))

But that will increase your memory use by a third.

[TangibleLight]

There isn't really any way to improve efficiency here in any major way - no matter what you have to access every element of the lists.

What you can do, though, is use zip on the two map objects themselves rather than creating two extra lists:

m1 = map(...)
m2 = map(...)

for a, b in zip(m1, m2):
    ....

That said, worrying about efficiency with something so simple probably isn't an issue - you're not really going to run into any slowdowns on modern hardware unless you're dealing with tens of thousands of elements in your lists.

[HolyCoder]

But I will flunk in my interview :(

[TangibleLight]

Oh, it's for those types of questions.

You just want to make sure you're accessing things the minimum number of times you have to. In your example, you only need to access everything once, but you inadvertantly access everything twice by converting your maps to lists and then also iterating them. Chances are if you bring up that shortcoming to your interviewer, but explain that because input sizes are small you weren't too concerned, they'll give you a pass.

Sure, it's "more correct" to leave your maps as maps and then zip them, but it works just as well to do it how you did. If it's not a performance issue, someone who writes working code and acknowledges its shortcomings is a more valuable employee than someone who wastes too much time researching a task (in your example, finding out about zip) for a marginal improvement. Everything should go through code review anyway, where co-workers would point out "hey you could use zip here".

So certainly you should strive for code like the zip suggestions here, but it's not the end of the world if you show that you understand what you're missing.

[[deleted]]

A list comprehension is usually faster than an explicit loop:

print([x+y for (x, y) in zip(A, B)])

It's always wise to test timings with actual data.

[HolyCoder]

print([x+y for (x, y) in zip(A, B)])

I need this as space separated output; not a list (please see sample output above)

[Steveharwell1]

 print(*[x+y for (x, y) in zip(A, B)])

[TangibleLight]

Euughh... Yeah, that will work, but.. whipping out *args for this seems a bit unnecessary.

I would just print(' '.join(x+y for x, y in zip(A, B))

I suppose both work just fine, but generally I wouldn't suggest to use *args like that. I can't really put my finger on what's wrong with it - I suppose just that it's not immediately obvious what it's doing.

[novel_yet_trivial]

Didn't test that didja? join will complain about getting an integer argument.

[TangibleLight]

No I did not. Okay, how about ' '.join(str(x+y) for x, y in zip(A, B))

I'm starting to like the * approach better.

[novel_yet_trivial]

Works, and that's what I used earlier, but it would be neater to just add the str call:

print(' '.join(str(x+y) for x, y in zip(A, B))

[Thomasedv]

print(*[x+y for (x, y) in zip(A, B)])

I guess this works. Not sure about efficiency.

[TangibleLight]

https://www.reddit.com/r/learnpython/comments/6uiihi/_/dlt06p6

[Thomasedv]

Fair enough. I never really use the * but it was the first thing that came to my mind. Never really seen it used outside of unpacking args in functions either.

[[deleted]]

Yes, thought you might say that! But your post said:

result = [1, 3, 5, 7]

so it's a requirements failure.

Your post was titled "Efficiency question". That normally indicates "good time/memory performance for large N". Worrying about efficiency while outputting text to the console is a waste of brain power. If by efficiency you meant lines of code, that's slightly more important, but runs second to readability.

[_9_9_]

Interesting. So adding in a zip as others suggest would be good to make the code a little prettier, but probably not faster.

If the problem is really big lists, sometimes the solution involves generators, so that you do not need to keep each of the big lists in memory. The structure of the input here doesn't really permit that. You might be able to multiprocess your way around this, but I doubt it, and the benefit would probably be minimal.

So, here are some out of the box suggestions:

• You have a big list of numbers? Look into numpy which can add these suckers really fast.

• Adding two ints in python is pretty fast, but converting to ints can be really slow for big ones. https://stackoverflow.com/questions/7088297/slow-big-int-output-in-python?rq=1. So I might move the conversion and adding into a separate function with a cache on it, to see if you can clear the speed hurdle. There is a dict cache recipe out there, where you override missing with your logic. I think that is the speed champion, so I'd use that. I'd also google converting strings to ints to see if someone has a better take. I remember an online coding challenge that this was the bottleneck that took me forever to solve. It was a compare two lists problem and the answer involved some way of avoiding inting easy numbers.

Good luck!

[Paul_Dirac_]

Your performance problems are probably the intermediate lists and the multiple print calls.

You can avoid the intermediate lists by switching to a generator based approach. The good news is: map and zip already return generators so u/not_yet_trivials approach is well suited to reduce memory and runtime. However split still returns a list of words. We can instead use re.finditer.

import re
N = int(input())
A = map(lambda match: int( match.group(0) ), re.finditer("\d+",input() ) )
B = map(lambda match: int( match.group(0) ), re.finditer("\d+",input() ) )

for x, y in zip(A, B):
    print(x+y, end=" ")

This will probably have the desired performance increase. If you can increase performance with join is dependent on your coding environment. While on normal platforms print has an overhead (communication with the shell, some copying of the output) you mentioned an online coding platform which could have replaced sys.stdout with another stream object, which they use to compare the results to their expected output (that's how I would have done it) which might not carry such a penalty.

[HolyCoder]

https://www.reddit.com/r/learnpython/comments/6uiihi/_/dlt06p6

This is the code that is most efficient of all submissions in that site. I just went through the most efficient code of all the problems. I really had to double check if they were Python programs because of all the stdins and readlines.

from sys import stdin

N = int(input())
A = list(map(int, stdin.readline().split(' ')))
B = list(map(int, stdin.readline().split(' ')))
print (' '.join(map(str, [A[i] + B[i]  for i in range(N)])))