一个完美平衡照片库的算法

【感谢@AvisBlume 的热心翻译。如果其他朋友也有不错的原创或译文,可以尝试提交到伯乐在线。】

还记得在学校里学大O符号(Big O notation) 反复实现各种排序算法的那些日子吗?如果你是像我这样的一个网页开发工程师,那么你很可能永远也不会用到这些算法了。

不要表示反对,我的意思是说,网页开发中99%的工作都是在处理浏览器的各种异常,还有就是在纠结其他人的代码。

然后,算法知识突然就变得非常有用了。

 

产生想法

从Chromatic项目一开始,我们就想让照片尽可能地大。不要缩略图,不要裁剪,也不要浪费屏幕上宝贵的每寸地方。

相册通常会含有10到100张长宽比各异的照片,我们的目的是要让它们一行一行地平均分布在所有可用空间内。

最后我们决定:让照片看起来都一样高,每一行进行微调从而让照片充满整行空间。

 

遇到问题

但我们该如何布置这些照片呢?如果不发帖问下“我要怎样才能得到某个库来实现某个功能”的话,在StackOverflow网上就很难找到答案了。

于是我们开始从算法的角度来思考我们遇到的问题:这会不会是一个已知的标准问题?可不可以将它变成一个标准问题?

如果是这样的话,那很可能已经有人设计出一种算法来解决这个问题了。

实际上也确实如此,这属于划分问题。更好的是已经有个Python版的实现了,我们后来把它移植到了Coffeescript中

 

解决办法

剩下的就很简单了。

为了找出所需的行数(k),我们先将照片高度调整到窗口的一半(因为我们发现调整到一半的时候照片看起来和谐),将它们的宽度加起来,然后除以窗口的宽度。结果可能不是整数,因此要将其取整。

照片的高宽比(乘以100以后取整)看做高度的集合(S)。然后我们就用新得的算法工具根据S和k来找出最佳解法。

计算结果告诉我们每行照片的数量。然后要做的就是选用适当大小的照片,进行调整后放入可用的水平空间中。

下面是 Backbone 照片库(gallery)视图的相关代码。实际线性分区算法可以在这里找到。

做这个花了不少工夫,但是,哈哈,来看看效果吧!

收藏 1 评论

关于作者:伯乐在线读者

① 本账号用于发布那些在伯乐在线无账号的读者的投稿,包括译文和原创文章。② 欢迎加入伯乐在线专栏作者:http://blog.jobbole.com/99322/ 个人主页 · 我的文章 · 32

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部