Hacking Pairsums
By Christian Herlein, EDRANS Software Engineer.
Disclaimer: this post could be very long. Sorry about that.
Note: code referenced available in GitHub
Background
Since I realized development is still a discipline of the computers science, no matter at what level your programming skills are, I was looking for a small project that allows me to study programming itself, its relationship with maths, and the developer behaviour itself.
Couple of days ago, my colleague (and friend), Zeph proposed to me an exercise. It was born as a job interview exercise, but I realized that it was complex enough to be interesting, tricky and funny at the same time.
Goal / Target
What I will try to do over the next lines is to explain the exercise itself, then create a simple first solution. With that solution, I will explore its issues and iterate over the code to make improvements giving math arguments, in order to find the best solution I am able to. In the process, what I will try to focus, is also my interaction with the code.
Scenario
Let’s suppose we have to implement a class with two methods: add(n), and check(n) bool, where:
add(n) -> sets Availables = {a1, a2, … an} ∪ N={n}.
check(n) = true ↔ a1 + a2 = n / a1, a2 € Availables ∧ a1 != a2.
Restrictions:
It’s not possible to store results of a1 + a2 as add(n) is called. Negative numbers should be supported, in both add and check.
Development:
First approach:
The basic logic of this exercise is quite simple: on add, all we have to do is push n to an internal array. Then, for check, we iterate over that array and check on every number if there is another one that sums n.
Above code will work. It’s actually a correct first approach. Also, It has two optimizations: start j loop on j = i + 1 and ending the function prematurely if the sum is found. But It has a lot of performance issues.
- Unnecessary same available sum: As we may have the same number twice (or more) on our list, we came to the need to check if numbers to be summed aren’t equals. Doing this on every loop is too much extra work.
- Nested loops: Having to loop over complete availables array to check if every number plus another one (that we have to look with a loop) blows up for completely our function’s BigO. With this implementation of check, BigO will respond to the form x2 (operations tends to be square inputs -availableslength).
Second approach:
Let’s try to attack FA issues. For the first one, the easiest fix is to avoid storing duplicated values at add time:
And, what about second issue (loop’s one)? Well, It’s still not possible to avoid loop nesting. But, we can change inline I loop for native .find() method, and take advantage of V8 engine’s optimization systems. As long as we already have a possible a1, we can clear our needed value of a2 and look if that value exists in our array.
Still bad. Our BigO is still in parabolic shape. But looks better than FA.
Making improvements:
Let’s try to speed our check func up. Two factors are involved in function performance: inputs length and search algorithm.
Inputs length:
Inside our availables array, we have unnecessary possibilities. For example: if we take the bigger value, it could be possible bigger than our n check’s input. The only way this bigger value to be a possible solution is if we have negative numbers as the lowers. To be fair, having all non negative numbers, the thinking is the same: the maximum possible number to be used for checking is n plus lower value available.
∄ a1 < a2 € Availables / a1 + a2 = n ∧ a2 > n — MIN(Availables)
Then, we can create a subgroup Availables2 (A2) with elements in Availables except all those who are greater than (n — MIN(A)).
After A2 creation, we can look for a lower level:
∄ a1 < a2 € A2 / a1 + a2 = n ∧ a2 < n — MAX(A2)
Well, that looks good in math style. But let’s translate that to code. In order to handle availables array nicely, keeping it ordered is a good idea. So, lets implement a new method sorting for available inputs:
Disclaimer: array’s sort method order items as string by default. Custom function with returns -1, 0, 1 is needed.
Then, we need to add a flag sorted to class properties and mark as false in add(n)
Finally, we must ensure inputs are sorted, and find limits for actual valid inputs:
Finally! We have a subgroup A2={a[lower], …, a[upper]}, with a lower length to iterate.
Nested loop issue:
Now, let’s put hands on the biggest issue. It’s ok to have nested loops for small taks. Sometimes, you can’t avoid them. But in our case, do we have a pattern to apply to avoid that overhead? Maths can give us a hint:
n/2 + n/2 = n
Nothing strange with that equality, right? Lets try affecting both n/2 terms in a related way that still keeps the equality:
F(x)·n/2 + x·n/2 = n
F(x) = 2 — x
There we have a clue: change F(x)n/2 by a1 and xn/2 by a2. If the final function is plotted, we’ll see that if a1 is bigger than n/2, a2 is lower than n/2 (since it pass for point (1, 1) in a descendent way). Then, we don’t need to sum all values of A2, but take n/2 and sum lowers against greaters.
The trick should be done by tracking indexes for left (li) and right (ri) of the index of a ≥ floor(n/2), and moving them according to the result of (availables[li] + availables[ri]) — n.
And that’s all. We have found an optimal solution!
No… not that fast
Before we finish our work, we have to measure (or calculate) how much we have improved our code. In terms of processing time. Note: times are based on the worst scenario of inputs and checks: not found.
First approach:
Operations needed for add:
- Array.push: inputs.length times.
Operations needed for check:
- First loop, inputs.length times.
- Nested loop, inputs.length each First loop’s time.
- Two compares each Nested loop times.
Then, we can consider push and compares are linear. But, nesting loops gave us a square inputs length bigO.
Improved approach:
Operations needed for add:
- Array.push: inputs.length times.
- Array.sort: inputs.length times.
Operations needed for check (with no availables reduction possible and same length of availables lowers and greaters than n/2):
- Sort: once if inputs were modified, none otherwise.
- Array.findIndex: exactly twice.
- Array.slice: once.
- While loop: input.length times.
Considering this ops, bigO will respond to a linear progression.
That said, it is still worth thinking about the average execution time of both approaches. While in FA we have no smart control on numbers tested, and we haven’t discarded any inputs before testing, we can estimate the average execution time will be around (inputs.length2) / 2. But, in IA, our control A2 group can reduce inputs to the half, and also iterations can be reduced to half of testings. Then, Avg(IA) should be like [(inputs.length) / 2] / 2.
Theoretically, we have improved our class 4X times. Let’s check it!
Testing
I will propose three test cases:
- T1: Like unit test, to pass inputs and then check a fixed amount of numbers knowing the expected result (test1.js).
- T2: This one will look for a non existing n, with X inputs and X times executing check(n) (test2.js).
- T3: This one will look for X numbers, mixing of existing and non-existing n, with X inputs (test3.js).
Execution times tables:
Disclaimer: Tests run on Dell Latitude i7, single core processing. Default time magnitude is milliseconds (ms).
T2:
T3:
After more than six hours, I thought keep doing this test was pointless.
I was really surprised about the results. To make an approximate fairly comparison, we can create a couple of relations:
● Avg(FP) / Avg(IA): to measure a general performance.
● FP(n) / FP(n-1), IA(n) / IA(n-1), n / n-1: to measure how performance change based on how inputs change.
What I was expecting -to be honest- was similar numbers in relations between t2 and t3. But, we can see two very different growing times. Main diff between tests is the number check is looking for. In t2, It is constant (38)… and the growing on the time is quite linear, and it tends to be T(fa) = 2(ia). And still, t2’s fa has to check for every single sum before returning false.
Shocking is to move to t3: times are no longer lineals. And they are substantially bigger, in the same range of inputs.
What would make sense to me, is that V8 engine is doing some magic here. Engine has it’s own improvements on repeated tasks. I don’t know them all by detail, must say. That opens a new question: what would happen if we write our code in a compiled language (C++, for example).
Summing up: with this evidence, we can ensure our improvements have made a lot of effects. Just taking t3 as the most challenging test, fa was not even possible to handle 100k checks on same amount of inputs. In the other hand, ia was able to handle them in 44.72s. Our times are fasters than our theory 4x.
Conclusion
We were able to get a problem, give it a first try and then iterate over our development process to achieve a better solution than our first one. This is a big part of our work as software engineers: wonder every time we do something if we can make it better. Four times faster is not quite impressive, but it is. And it’s even more when we check against real benchmarks. But keep 4X in mind, and consider that our client can pay just the 25% of the original processing price.
But not only for paid projects this approach is useful to us. This is part of who we are: we are scientists at the end. To watch, to ask, to investigate, to test. This process makes ourselves be who we are.
Future
As long as questions are the basics of our work, other questions appear here.
- What if we want to calculate more than two inputs?
- What if we don’t care about how many inputs we sum but the result itself?
- What if we allow to sum the same number as many times as needed?
- Is it possible to don’t store all add(n) numbers given, but a smaller group with the same characteristics?
- How will other developers face the same exercise if they don’t know the work I’m doing here?
- What if we write our code in a compiled language?
This is subject for future investigations.
Greetings
Thanks for reading. Any comments, suggestions or error pointers are welcome.
Also, if you want to investigate over open questions, let me know. We can exchange some ideas, perhaps.