还记得在学校里学大O符号（Big O notation） 反复实现各种排序算法的那些日子吗？如果你是像我这样的一个网页开发工程师，那么你很可能永远也不会用到这些算法了。
不要表示反对，我的意思是说，网页开发中99%的工作都是在处理浏览器的各种异常，还有就是在纠结其他人的代码。
然后，算法知识突然就变得非常有用了。
产生想法
从Chromatic项目一开始，我们就想让照片尽可能地大。不要缩略图，不要裁剪，也不要浪费屏幕上宝贵的每寸地方。
相册通常会含有10到100张长宽比各异的照片，我们的目的是要让它们一行一行地平均分布在所有可用空间内。
最后我们决定：让照片看起来都一样高，每一行进行微调从而让照片充满整行空间。
遇到问题
但我们该如何布置这些照片呢？如果不发帖问下“我要怎样才能得到某个库来实现某个功能”的话，在StackOverflow网上就很难找到答案了。
于是我们开始从算法的角度来思考我们遇到的问题：这会不会是一个已知的标准问题？可不可以将它变成一个标准问题？
如果是这样的话，那很可能已经有人设计出一种算法来解决这个问题了。
实际上也确实如此，这属于划分问题。更好的是已经有个Python版的实现了，我们后来把它移植到了Coffeescript中。
解决办法
剩下的就很简单了。
为了找出所需的行数(k)，我们先将照片高度调整到窗口的一半（因为我们发现调整到一半的时候照片看起来和谐），将它们的宽度加起来，然后除以窗口的宽度。结果可能不是整数，因此要将其取整。
照片的高宽比（乘以100以后取整）看做高度的集合(S)。然后我们就用新得的算法工具根据S和k来找出最佳解法。
计算结果告诉我们每行照片的数量。然后要做的就是选用适当大小的照片，进行调整后放入可用的水平空间中。
下面是 Backbone 照片库（gallery）视图的相关代码。实际线性分区算法可以在这里找到。
viewport_width = $(window).width()
ideal_height = parseInt($(window).height() / 2)
summed_width = photos.reduce ((sum, p) -> sum += p.get('aspect_ratio') * ideal_height), 0
rows = Math.round(summed_width / viewport_width)
if rows < 1
# (2a) Fallback to just standard size
photos.each (photo) -> photo.view.resize parseInt(ideal_height * photo.get('aspect_ratio')), ideal_height
else
# (2b) Distribute photos over rows using the aspect ratio as weight
weights = photos.map (p) -> parseInt(p.get('aspect_ratio') * 100)
partition = linear_partition(weights, rows)
# (3) Iterate through partition
index = 0
row_buffer = new Backbone.Collection
_.each partition, (row) ->
row_buffer.reset()
_.each row, -> row_buffer.add(photos.at(index++))
summed_ratios = row_buffer.reduce ((sum, p) -> sum += p.get('aspect_ratio')), 0
row_buffer.each (photo) -> photo.view.resize parseInt(viewport_width / / summed_ratios * photo.get('aspect_ratio')), parseInt(viewport_width / summed_ratios)
|
做这个花了不少工夫，但是，哈哈，来看看效果吧！
原文链接： Johannes Treitz | 
