In Search of the Perfect Image Gallery Part 2
Just two days after the release of perfect-layout, I have to say that I’m really glad and impressed by the interested it seems to have created.
By the way I was not really happy with the result so far: in a lot of situations chromatic.io galleries seems to be way more balanced and with a 7/8-approximation I’d have to get similar results instead. Reading your feedbacks and staring a bit more to my code I’ve realized that with the greedy approach I can only get a very good partition, but with an unpredictable ordering. If I want every picture to be associated with his relative weight (ratio) I had two possibilities: changing the order of my original gallery, or search for another algorithm.
Obviously I opted for the second solution. The resources on linear partitioning are quite limited and the very slow dynamic programming approach seems to be the most diffused. However it is in fact a bruteforce that cache his intermediate results with a complexity of O(kn^2) and I cannot believe that there aren’t faster approaches.
I’ve never been a math guy… however my guessing/heuristic way of being suggested me that usually when we struggle with some O(n^2) beasts there is probably a smart guy in Russia that know how to do the same thing in O(n log n) or similar.
So I’ve started googling about linear partition with keywords such as “recursive” and “binary search” And finally I’ve found what I was looking for:
- http://articles.leetcode.com/2011/04/the-painters-partition-problem.html
- http://articles.leetcode.com/2011/04/the-painters-partition-problem-part-ii.html
I strongly advice you to give it a look because it is really well written.
Basically they suggest to use a classical BST like approach, where we look for the right threshold for the sum of the weights on every row, by subsequently evaluate how good performs the middle point between the maximum possible threshold and the minimum one. Then at every step repeat the process on the halved range that must contains the solution.
All that just assuming that we are never going to need a threshold smaller than the maximum of the weights and we’ll never push it higher than the sum of all the weights.
So I’ve scratched out my own implementation:
And guess what… not only it perfectly dispose my images as chromatic.io would do, but it outperform the greedy algorithm as well in terms of speed.
Here it is an updated jsperf
It is almost 7 times faster than the already very fast greedy algorithm, and it is incredibly fast also on a set with 1000 images to be distributed on 200 rows.
Just update to the the new 1.1.1 version and let me know what you think.
thanks for all the interest and the suggestions.
N.B as clearly stated on the README the jQuery plugin is only an example on how to use the perfectLayout function and I do not recommend to use it on production as it is. There are no guarantees about cross browser behavior and the DOM operations are not optimized.
perfect-layout on github
