functions
split the work you want to do in logical functions. I try to limit the work that is done in the general script (and thus the global namespace) as much as possible. Lookups of local variable are supposed to be faster, but it make the code easier to read and test as well, so win-win.
hashing
Why device your own hashing? just dumping all the numbers in a set will eliminate all the duplicates, and 1M integers is a limited amount of memory. Certainly a lot less that the defaultdict
you use
global variable ans
Instead of passing the global variable ans
, the easiest way would be to use the fact that in a numeric context (like sum
), True
equals 1 and False
equals 0, so you can just return True or False in two_sum_present
my take on this:
read the file
Using the fact that a file is an iterator, I would do something like this
def read_file(filename):
with open(filename, 'r') as file:
return set(map(int, file))
find the target
About the same as your two_sum_present
with my remarks incorporated
def find_target(numbers, target):
for i in numbers:
if target - i in numbers and 2 * i != target:
return True
return False
iterate over the interval
def find_sums(numbers, start=-10000, end=10000):
for target in range(start, end + 1):
# print(target)
yield find_target(numbers, target)
putting it together
def main(filename, start=-10000, end=10000):
numbers = read_file(filename)
# print(f'numbers found: {len(numbers)}')
return sum(find_sums(numbers, start, end))
if __name__ == '__main__':
filename = 'data/_6ec67df2804ff4b58ab21c12edcb21f8_algo1-programming_prob-2sum.txt'
print(main(filename, -100, 100))
All in all, it took 43 seconds to scan those 201 numbers on my system, to find 5 matches. Reading the file took about .6s of that time
This solution is essentially the same as sum(any(n-x in numbers and 2*x != n for x in numbers) for n in range(-100, 101))
, but that one took 59s
Multithreading
If you want to, you can divide out all the call to find_target
to different workers/cores/... In this case, a frozenset
instead of a set
might be more appropriate since it's immutable, and will give less problems with concurrency
distinct
As noted by Gareth Rees, the original question is ambiguous on what is mean with distinct numbers x,y
. To cover the second interpretation, You can change the set
to a collections.Counter
, and change the test criterium slightly
from collections import Counter
def read_file_distinct(filename):
with open(filename, 'r') as file:
return Counter(map(int, file))
def find_sums_distinct(numbers, start=-10000, end=10000):
for target in range(start, end + 1):
# print(target)
yield find_target_distinct(numbers, target)
def find_target_distinct(numbers, target):
for i in numbers:
if target - i in numbers and (2 * i != target or numbers[i] > 1):
return True
return False
def main_distinct(filename, start=-10000, end=10000):
numbers = read_file_distinct(filename)
# print(f'numbers found: {len(numbers)}')
return sum(find_sums_distinct(numbers, start, end))
This has an effect on speed, though
%timeit main(filename, -10, 10)
4.51 s ± 32.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit main_distinct(filename, -10, 10)
6.42 s ± 48.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
distinct 2
A slightly different, faster approach can be used to tackle the 2nd interpretation
def find_sums_distinct2(numbers, repetitions,start=-10000, end=10000):
for target in range(start, end + 1):
# print(target)
yield find_target_distinct2(numbers, repetitions, target)
def find_target_distinct2(numbers, repetitions, target):
for i in numbers:
if target - i in numbers and (2 * i != target or i in repetitions):
return True
return False
def main_distinct2(filename, start=-10000, end=10000):
numbers = read_file_distinct(filename)
repetitions = {k for k, v in numbers.items() if ((v > 1) and (start < k < end))}
# print(repetitions)
numbers = set(numbers)
# print(f'{len(numbers)} numbers found, {len(repetitions)} repetitions')
return sum(find_sums_distinct2(numbers, repetitions, start, end))
%timeit main_distinct2(filename, -10, 10)
4.92 s ± 160 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
hash_fn
is misaligned for eg. \$\endgroup\$ – hjpotter92 Apr 5 '18 at 23:04