• From: David A Benjamin <davidben MIT EDU>
• To: Tristan Van Berkom <tristanvb openismus com>
• Cc: gtk-devel-list gnome org
• Date: Thu, 7 Oct 2010 00:42:24 -0400 (EDT)

```On Thu, 7 Oct 2010, Tristan Van Berkom wrote:

```
```Some technical caveats:
- When there are over ~12 columns the whole thing slows down
significantly.

The reason for this being, the algorithm in place starts
by lining up all the widgets in the first column and
then evening them out column by column... by the time
we hit the 3rd column; columns 1 & 2 need to be recalculated
for every widget we pull into the 3rd column, and so on
as the columns grow.

By the time we hit 12 columns things are getting exponentially
heavier to calculate (I've tried simpler algorithms that were
much further from perfect results than this one though).

```
```
```
So, am I understanding your setup and code correctly? You have a number of columns of equal width that you wish to arrange some widgets into. The first few widgets get laid out vertically into the first column, the next into the next column, etc. And your goal is to minimize the height of the tallest column, computed as the sum of the heights of each widget (plus some padding between them). Is this correct?
```
```
In that case, just binary search for the optimum height; bounds are the average and the total of the boxes. For a given candidate height, a greedy algorithm is sufficient to determine whether or not the height is viable. Just go through column-by-column and stuff widgets into the next column until you can't fit the next widget and move on to the next column. If you manage to fit them all, you have a valid height and valid assignment; try going smaller if you can. If you go through all the columns with widgets to spare, your height was too big; go larger. Running time is O(num_widgets * log(total_height)) with a very nice constant.
```
```
In fact, I think this should work for variable-width columns, although you won't be able to cache the heights.
```
```
(You can also do a DP, but I've only been able to get that down to O(num_widgets * num_columns * log(num_widgets)) thus far.)
```
```
I can give the implementation a go sometime this weekend if no one else beats me to it. :-)
```
David
```

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]