Have you considered counting the items first? I found it's a lot faster to execute.
Here's the basic idea in Python:
from collections import Counter
import random
asum = random.randrange(200) + 100
# A Counter is a key:value mapping
# a = { i: ocurrence(i) for i in alist}
a = Counter (random.randrange(100) for _ in range(int(1e7)))
def two_sum_gen(counts, total):
for i in (c for c in counts if c <= total/2):
if total-i in counts:
yield (i, total-i)
def three_sum_gen(counts, total):
for i in (c for c in counts if c <= total/2):
for a, b in two_sum_gen(counts, total-i):
yield (i, a, b)
This code is simplified for the sake of clarity. For instance, it only returns the set of valid groups, and purposefully omits the count of each occurrence of the grouping. It also consider that each element occurs an infinite amount of time. So for instance:
list = [1, 5, 3]
total = 9
answer: ((3, 3, 3), (1, 5, 3)) # first one is wrong.
The goal is really to show what I have in mind and not clobber it with stupid details. (I have previously worked on these issues in the
original exercise).
Quick explanation
- Counter is a hashmap that holds each element of a collection as keys and the number of occurrence of each. 2sum becomes easy to implement: for each element n in the collection, retrieve how many times (total-n) has occurred. Since dictionary access is constant in time O(1), the whole function executes in O(n). (Actually, you can easily divide that by 2, by iterating on elements lesser than (or equal to) total/2).
- 3sum is not very hard to calculate either: For each element n in the collection, retrieve all the pairs in the collections whose sum equals total. (just like @arithma suggests).
The complete answer is a little more complicated. Not included in the code:
- Each time n looks for (total-n) in the dictionary, it should decrease its own count by 1, to avoid infinite count bug.
- Each time a match is found, we should count the number of times it occurs by multiplying the count of each element
But for now this should do.
Profiling
I am going to test against this stupid bruteforce test:
asum = random.randrange(200) + 100
a = [random.randrange(300) for _ in range(1e2)]
result = [(i, j, k) for i,j,k in three_sum_gen(a, asum)]
This one clearly executes in O(n3). For an initial list of 300 elements, it takes approximately 3 seconds on my PC (recent i5) to execute. Here's the profiling of the execution:
156946 function calls in 3.328 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
156943 3.296 0.000 3.296 0.000 <string>:1(<genexpr>)
1 0.032 0.032 3.328 3.328 <string>:1(<module>)
1 0.000 0.000 3.328 3.328 {built-in method exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Here's the execution time of my method using Counters (emphasis mine):
7494 function calls in 0.004 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1873 0.001 0.000 0.002 0.000 3sum.py:12(two_sum_gen)
1917 0.001 0.000 0.001 0.000 3sum.py:14(<genexpr>)
1824 0.001 0.000 0.003 0.000 3sum.py:18(three_sum_gen)
51 0.000 0.000 0.000 0.000 3sum.py:20(<genexpr>)
1824 0.001 0.000 0.003 0.000 <string>:1(<genexpr>)
1 0.001 0.001 0.004 0.004 <string>:1(<module>)
1 0.000 0.000 0.004 0.004 {built-in method exec}
1 0.000 0.000 0.000 0.000 {built-in method len}
1 0.000 0.000 0.000 0.000 {built-in method print}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
I tried going to higher values: For 1000 elements, the Counter-based approach takes a split second as well, while the slow approach doesn't finish (at least after a few minutes).
The highest I could get the Counter-based approach was to run it on a 10,000,000 (1e7) element Counter in 13.2 seconds. After that I got bored.
The point is: it can operate on fairly large arrays. If you need more, than probably some optimizations have to be done.
What next
I will try to generalize to groups of n elements whose sum is
total.