Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>How many images?</p> <p>If you limit the maximum page size, and have a value for the minimum picture height, you can calculate the maximum number of images per page. You would need this when evaluating any solution.</p> <p>I think there were 27 pictures on the link you gave.</p> <p>The following uses the first_fit algorithm mentioned by Robin Green earlier but then improves on this by greedy swapping.</p> <p>The swapping routine finds the column that is furthest away from the average column height then systematically looks for a swap between one of its pictures and the first picture in another column that minimizes the maximum deviation from the average.</p> <p>I used a random sample of 30 pictures with heights in the range five to 50 'units'. The convergenge was swift in my case and improved significantly on the first_fit algorithm.</p> <p>The code (Python 3.2: </p> <pre><code>def first_fit(items, bincount=3): items = sorted(items, reverse=1) # New - improves first fit. bins = [[] for c in range(bincount)] binsizes = [0] * bincount for item in items: minbinindex = binsizes.index(min(binsizes)) bins[minbinindex].append(item) binsizes[minbinindex] += item average = sum(binsizes) / float(bincount) maxdeviation = max(abs(average - bs) for bs in binsizes) return bins, binsizes, average, maxdeviation def swap1(columns, colsize, average, margin=0): 'See if you can do a swap to smooth the heights' colcount = len(columns) maxdeviation, i_a = max((abs(average - cs), i) for i,cs in enumerate(colsize)) col_a = columns[i_a] for pic_a in set(col_a): # use set as if same height then only do once for i_b, col_b in enumerate(columns): if i_a != i_b: # Not same column for pic_b in set(col_b): if (abs(pic_a - pic_b) &gt; margin): # Not same heights # new heights if swapped new_a = colsize[i_a] - pic_a + pic_b new_b = colsize[i_b] - pic_b + pic_a if all(abs(average - new) &lt; maxdeviation for new in (new_a, new_b)): # Better to swap (in-place) colsize[i_a] = new_a colsize[i_b] = new_b columns[i_a].remove(pic_a) columns[i_a].append(pic_b) columns[i_b].remove(pic_b) columns[i_b].append(pic_a) maxdeviation = max(abs(average - cs) for cs in colsize) return True, maxdeviation return False, maxdeviation def printit(columns, colsize, average, maxdeviation): print('columns') pp(columns) print('colsize:', colsize) print('average, maxdeviation:', average, maxdeviation) print('deviations:', [abs(average - cs) for cs in colsize]) print() if __name__ == '__main__': ## Some data #import random #heights = [random.randint(5, 50) for i in range(30)] ## Here's some from the above, but 'fixed'. from pprint import pprint as pp heights = [45, 7, 46, 34, 12, 12, 34, 19, 17, 41, 28, 9, 37, 32, 30, 44, 17, 16, 44, 7, 23, 30, 36, 5, 40, 20, 28, 42, 8, 38] columns, colsize, average, maxdeviation = first_fit(heights) printit(columns, colsize, average, maxdeviation) while 1: swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation) printit(columns, colsize, average, maxdeviation) if not swapped: break #input('Paused: ') </code></pre> <p>The output:</p> <pre><code>columns [[45, 12, 17, 28, 32, 17, 44, 5, 40, 8, 38], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 34, 9, 37, 44, 30, 20, 28]] colsize: [286, 267, 248] average, maxdeviation: 267.0 19.0 deviations: [19.0, 0.0, 19.0] columns [[45, 12, 17, 28, 17, 44, 5, 40, 8, 38, 9], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 34, 37, 44, 30, 20, 28, 32]] colsize: [263, 267, 271] average, maxdeviation: 267.0 4.0 deviations: [4.0, 0.0, 4.0] columns [[45, 12, 17, 17, 44, 5, 40, 8, 38, 9, 34], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 37, 44, 30, 20, 28, 32, 28]] colsize: [269, 267, 265] average, maxdeviation: 267.0 2.0 deviations: [2.0, 0.0, 2.0] columns [[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 44, 30, 20, 28, 32, 28, 40]] colsize: [266, 267, 268] average, maxdeviation: 267.0 1.0 deviations: [1.0, 0.0, 1.0] columns [[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 44, 30, 20, 28, 32, 28, 40]] colsize: [266, 267, 268] average, maxdeviation: 267.0 1.0 deviations: [1.0, 0.0, 1.0] </code></pre> <p>Nice problem.</p> <hr> <p>Heres the info on reverse-sorting mentioned in my separate comment below.</p> <pre><code>&gt;&gt;&gt; h = sorted(heights, reverse=1) &gt;&gt;&gt; h [46, 45, 44, 44, 42, 41, 40, 38, 37, 36, 34, 34, 32, 30, 30, 28, 28, 23, 20, 19, 17, 17, 16, 12, 12, 9, 8, 7, 7, 5] &gt;&gt;&gt; columns, colsize, average, maxdeviation = first_fit(h) &gt;&gt;&gt; printit(columns, colsize, average, maxdeviation) columns [[46, 41, 40, 34, 30, 28, 19, 12, 12, 5], [45, 42, 38, 36, 30, 28, 17, 16, 8, 7], [44, 44, 37, 34, 32, 23, 20, 17, 9, 7]] colsize: [267, 267, 267] average, maxdeviation: 267.0 0.0 deviations: [0.0, 0.0, 0.0] </code></pre> <hr> <p>If you have the reverse-sorting, this extra code appended to the bottom of the above code (in the 'if <strong>name</strong> == ...), will do extra trials on random data:</p> <pre><code>for trial in range(2,11): print('\n## Trial %i' % trial) heights = [random.randint(5, 50) for i in range(random.randint(5, 50))] print('Pictures:',len(heights)) columns, colsize, average, maxdeviation = first_fit(heights) print('average %7.3f' % average, '\nmaxdeviation:') print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation)) swapcount = 0 while maxdeviation: swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation) if not swapped: break print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation)) swapcount += 1 print('swaps:', swapcount) </code></pre> <p>The extra output shows the effect of the swaps:</p> <pre><code>## Trial 2 Pictures: 11 average 72.000 maxdeviation: 9.72% = 7.000 swaps: 0 ## Trial 3 Pictures: 14 average 118.667 maxdeviation: 6.46% = 7.667 4.78% = 5.667 3.09% = 3.667 0.56% = 0.667 swaps: 3 ## Trial 4 Pictures: 46 average 470.333 maxdeviation: 0.57% = 2.667 0.35% = 1.667 0.14% = 0.667 swaps: 2 ## Trial 5 Pictures: 40 average 388.667 maxdeviation: 0.43% = 1.667 0.17% = 0.667 swaps: 1 ## Trial 6 Pictures: 5 average 44.000 maxdeviation: 4.55% = 2.000 swaps: 0 ## Trial 7 Pictures: 30 average 295.000 maxdeviation: 0.34% = 1.000 swaps: 0 ## Trial 8 Pictures: 43 average 413.000 maxdeviation: 0.97% = 4.000 0.73% = 3.000 0.48% = 2.000 swaps: 2 ## Trial 9 Pictures: 33 average 342.000 maxdeviation: 0.29% = 1.000 swaps: 0 ## Trial 10 Pictures: 26 average 233.333 maxdeviation: 2.29% = 5.333 1.86% = 4.333 1.43% = 3.333 1.00% = 2.333 0.57% = 1.333 swaps: 4 </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POfitting n variable height images into 3 (similar length) column layout
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USPaddy3118
    1. USPaddy3118
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POfitting n variable height images into 3 (similar length) column layout
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTBountyClose
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COYou could improve on the above swap1 function by also allowing a picture to be moved from one column to another as well as swapping. As it stands, there will always be the same number of pictures in a column as found by the first-fit algorithm. If there was one exceptionally tall picture then this could skew things.
      singulars
      1. PO
      1. USPaddy3118
    2. COI just found that you get a perfect distribution with this data if you use first_fit on the reverse-sorted heights. I doubt this will always be the case though. Maybe we should always reverse-sort the picture heights?
      singulars
      1. PO
      1. USPaddy3118
    3. COJust looked beyond the crappy wikipedia article to http://www.developerfusion.com/article/5540/bin-packing where I think what I have called first_fit might be better called worst_fit from their examples.
      singulars
      1. PO
      1. USPaddy3118
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload