Package CedarBackup2 :: Module knapsack
[hide private]
[frames] | no frames]

Source Code for Module CedarBackup2.knapsack

  1  # -*- coding: iso-8859-1 -*- 
  2  # vim: set ft=python ts=3 sw=3 expandtab: 
  3  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
  4  # 
  5  #              C E D A R 
  6  #          S O L U T I O N S       "Software done right." 
  7  #           S O F T W A R E 
  8  # 
  9  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
 10  # 
 11  # Copyright (c) 2004-2005,2010 Kenneth J. Pronovici. 
 12  # All rights reserved. 
 13  # 
 14  # This program is free software; you can redistribute it and/or 
 15  # modify it under the terms of the GNU General Public License, 
 16  # Version 2, as published by the Free Software Foundation. 
 17  # 
 18  # This program is distributed in the hope that it will be useful, 
 19  # but WITHOUT ANY WARRANTY; without even the implied warranty of 
 20  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
 21  # 
 22  # Copies of the GNU General Public License are available from 
 23  # the Free Software Foundation website, http://www.gnu.org/. 
 24  # 
 25  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
 26  # 
 27  # Author   : Kenneth J. Pronovici <pronovic@ieee.org> 
 28  # Language : Python 2 (>= 2.7) 
 29  # Project  : Cedar Backup, release 2 
 30  # Purpose  : Provides knapsack algorithms used for "fit" decisions 
 31  # 
 32  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
 33   
 34  ######## 
 35  # Notes 
 36  ######## 
 37   
 38  """ 
 39  Provides the implementation for various knapsack algorithms. 
 40   
 41  Knapsack algorithms are "fit" algorithms, used to take a set of "things" and 
 42  decide on the optimal way to fit them into some container.  The focus of this 
 43  code is to fit files onto a disc, although the interface (in terms of item, 
 44  item size and capacity size, with no units) is generic enough that it can 
 45  be applied to items other than files. 
 46   
 47  All of the algorithms implemented below assume that "optimal" means "use up as 
 48  much of the disc's capacity as possible", but each produces slightly different 
 49  results.  For instance, the best fit and first fit algorithms tend to include 
 50  fewer files than the worst fit and alternate fit algorithms, even if they use 
 51  the disc space more efficiently. 
 52   
 53  Usually, for a given set of circumstances, it will be obvious to a human which 
 54  algorithm is the right one to use, based on trade-offs between number of files 
 55  included and ideal space utilization.  It's a little more difficult to do this 
 56  programmatically.  For Cedar Backup's purposes (i.e. trying to fit a small 
 57  number of collect-directory tarfiles onto a disc), worst-fit is probably the 
 58  best choice if the goal is to include as many of the collect directories as 
 59  possible. 
 60   
 61  @sort: firstFit, bestFit, worstFit, alternateFit 
 62   
 63  @author: Kenneth J. Pronovici <pronovic@ieee.org> 
 64  """ 
 65   
 66  ####################################################################### 
 67  # Public functions 
 68  ####################################################################### 
 69   
 70  ###################### 
 71  # firstFit() function 
 72  ###################### 
 73   
74 -def firstFit(items, capacity):
75 76 """ 77 Implements the first-fit knapsack algorithm. 78 79 The first-fit algorithm proceeds through an unsorted list of items until 80 running out of items or meeting capacity exactly. If capacity is exceeded, 81 the item that caused capacity to be exceeded is thrown away and the next one 82 is tried. This algorithm generally performs more poorly than the other 83 algorithms both in terms of capacity utilization and item utilization, but 84 can be as much as an order of magnitude faster on large lists of items 85 because it doesn't require any sorting. 86 87 The "size" values in the items and capacity arguments must be comparable, 88 but they are unitless from the perspective of this function. Zero-sized 89 items and capacity are considered degenerate cases. If capacity is zero, 90 no items fit, period, even if the items list contains zero-sized items. 91 92 The dictionary is indexed by its key, and then includes its key. This 93 seems kind of strange on first glance. It works this way to facilitate 94 easy sorting of the list on key if needed. 95 96 The function assumes that the list of items may be used destructively, if 97 needed. This avoids the overhead of having the function make a copy of the 98 list, if this is not required. Callers should pass C{items.copy()} if they 99 do not want their version of the list modified. 100 101 The function returns a list of chosen items and the unitless amount of 102 capacity used by the items. 103 104 @param items: Items to operate on 105 @type items: dictionary, keyed on item, of C{(item, size)} tuples, item as string and size as integer 106 107 @param capacity: Capacity of container to fit to 108 @type capacity: integer 109 110 @returns: Tuple C{(items, used)} as described above 111 """ 112 113 # Use dict since insert into dict is faster than list append 114 included = { } 115 116 # Search the list as it stands (arbitrary order) 117 used = 0 118 remaining = capacity 119 for key in items.keys(): 120 if remaining == 0: 121 break 122 if remaining - items[key][1] >= 0: 123 included[key] = None 124 used += items[key][1] 125 remaining -= items[key][1] 126 127 # Return results 128 return (included.keys(), used)
129 130 131 ##################### 132 # bestFit() function 133 ##################### 134
135 -def bestFit(items, capacity):
136 137 """ 138 Implements the best-fit knapsack algorithm. 139 140 The best-fit algorithm proceeds through a sorted list of items (sorted from 141 largest to smallest) until running out of items or meeting capacity exactly. 142 If capacity is exceeded, the item that caused capacity to be exceeded is 143 thrown away and the next one is tried. The algorithm effectively includes 144 the minimum number of items possible in its search for optimal capacity 145 utilization. For large lists of mixed-size items, it's not ususual to see 146 the algorithm achieve 100% capacity utilization by including fewer than 1% 147 of the items. Probably because it often has to look at fewer of the items 148 before completing, it tends to be a little faster than the worst-fit or 149 alternate-fit algorithms. 150 151 The "size" values in the items and capacity arguments must be comparable, 152 but they are unitless from the perspective of this function. Zero-sized 153 items and capacity are considered degenerate cases. If capacity is zero, 154 no items fit, period, even if the items list contains zero-sized items. 155 156 The dictionary is indexed by its key, and then includes its key. This 157 seems kind of strange on first glance. It works this way to facilitate 158 easy sorting of the list on key if needed. 159 160 The function assumes that the list of items may be used destructively, if 161 needed. This avoids the overhead of having the function make a copy of the 162 list, if this is not required. Callers should pass C{items.copy()} if they 163 do not want their version of the list modified. 164 165 The function returns a list of chosen items and the unitless amount of 166 capacity used by the items. 167 168 @param items: Items to operate on 169 @type items: dictionary, keyed on item, of C{(item, size)} tuples, item as string and size as integer 170 171 @param capacity: Capacity of container to fit to 172 @type capacity: integer 173 174 @returns: Tuple C{(items, used)} as described above 175 """ 176 177 # Use dict since insert into dict is faster than list append 178 included = { } 179 180 # Sort the list from largest to smallest 181 itemlist = items.items() 182 itemlist.sort(lambda x, y: cmp(y[1][1], x[1][1])) # sort descending 183 keys = [] 184 for item in itemlist: 185 keys.append(item[0]) 186 187 # Search the list 188 used = 0 189 remaining = capacity 190 for key in keys: 191 if remaining == 0: 192 break 193 if remaining - items[key][1] >= 0: 194 included[key] = None 195 used += items[key][1] 196 remaining -= items[key][1] 197 198 # Return the results 199 return (included.keys(), used)
200 201 202 ###################### 203 # worstFit() function 204 ###################### 205
206 -def worstFit(items, capacity):
207 208 """ 209 Implements the worst-fit knapsack algorithm. 210 211 The worst-fit algorithm proceeds through an a sorted list of items (sorted 212 from smallest to largest) until running out of items or meeting capacity 213 exactly. If capacity is exceeded, the item that caused capacity to be 214 exceeded is thrown away and the next one is tried. The algorithm 215 effectively includes the maximum number of items possible in its search for 216 optimal capacity utilization. It tends to be somewhat slower than either 217 the best-fit or alternate-fit algorithm, probably because on average it has 218 to look at more items before completing. 219 220 The "size" values in the items and capacity arguments must be comparable, 221 but they are unitless from the perspective of this function. Zero-sized 222 items and capacity are considered degenerate cases. If capacity is zero, 223 no items fit, period, even if the items list contains zero-sized items. 224 225 The dictionary is indexed by its key, and then includes its key. This 226 seems kind of strange on first glance. It works this way to facilitate 227 easy sorting of the list on key if needed. 228 229 The function assumes that the list of items may be used destructively, if 230 needed. This avoids the overhead of having the function make a copy of the 231 list, if this is not required. Callers should pass C{items.copy()} if they 232 do not want their version of the list modified. 233 234 The function returns a list of chosen items and the unitless amount of 235 capacity used by the items. 236 237 @param items: Items to operate on 238 @type items: dictionary, keyed on item, of C{(item, size)} tuples, item as string and size as integer 239 240 @param capacity: Capacity of container to fit to 241 @type capacity: integer 242 243 @returns: Tuple C{(items, used)} as described above 244 """ 245 246 # Use dict since insert into dict is faster than list append 247 included = { } 248 249 # Sort the list from smallest to largest 250 itemlist = items.items() 251 itemlist.sort(lambda x, y: cmp(x[1][1], y[1][1])) # sort ascending 252 keys = [] 253 for item in itemlist: 254 keys.append(item[0]) 255 256 # Search the list 257 used = 0 258 remaining = capacity 259 for key in keys: 260 if remaining == 0: 261 break 262 if remaining - items[key][1] >= 0: 263 included[key] = None 264 used += items[key][1] 265 remaining -= items[key][1] 266 267 # Return results 268 return (included.keys(), used)
269 270 271 ########################## 272 # alternateFit() function 273 ########################## 274
275 -def alternateFit(items, capacity):
276 277 """ 278 Implements the alternate-fit knapsack algorithm. 279 280 This algorithm (which I'm calling "alternate-fit" as in "alternate from one 281 to the other") tries to balance small and large items to achieve better 282 end-of-disk performance. Instead of just working one direction through a 283 list, it alternately works from the start and end of a sorted list (sorted 284 from smallest to largest), throwing away any item which causes capacity to 285 be exceeded. The algorithm tends to be slower than the best-fit and 286 first-fit algorithms, and slightly faster than the worst-fit algorithm, 287 probably because of the number of items it considers on average before 288 completing. It often achieves slightly better capacity utilization than the 289 worst-fit algorithm, while including slighly fewer items. 290 291 The "size" values in the items and capacity arguments must be comparable, 292 but they are unitless from the perspective of this function. Zero-sized 293 items and capacity are considered degenerate cases. If capacity is zero, 294 no items fit, period, even if the items list contains zero-sized items. 295 296 The dictionary is indexed by its key, and then includes its key. This 297 seems kind of strange on first glance. It works this way to facilitate 298 easy sorting of the list on key if needed. 299 300 The function assumes that the list of items may be used destructively, if 301 needed. This avoids the overhead of having the function make a copy of the 302 list, if this is not required. Callers should pass C{items.copy()} if they 303 do not want their version of the list modified. 304 305 The function returns a list of chosen items and the unitless amount of 306 capacity used by the items. 307 308 @param items: Items to operate on 309 @type items: dictionary, keyed on item, of C{(item, size)} tuples, item as string and size as integer 310 311 @param capacity: Capacity of container to fit to 312 @type capacity: integer 313 314 @returns: Tuple C{(items, used)} as described above 315 """ 316 317 # Use dict since insert into dict is faster than list append 318 included = { } 319 320 # Sort the list from smallest to largest 321 itemlist = items.items() 322 itemlist.sort(lambda x, y: cmp(x[1][1], y[1][1])) # sort ascending 323 keys = [] 324 for item in itemlist: 325 keys.append(item[0]) 326 327 # Search the list 328 used = 0 329 remaining = capacity 330 331 front = keys[0:len(keys)/2] 332 back = keys[len(keys)/2:len(keys)] 333 back.reverse() 334 335 i = 0 336 j = 0 337 338 while remaining > 0 and (i < len(front) or j < len(back)): 339 if i < len(front): 340 if remaining - items[front[i]][1] >= 0: 341 included[front[i]] = None 342 used += items[front[i]][1] 343 remaining -= items[front[i]][1] 344 i += 1 345 if j < len(back): 346 if remaining - items[back[j]][1] >= 0: 347 included[back[j]] = None 348 used += items[back[j]][1] 349 remaining -= items[back[j]][1] 350 j += 1 351 352 # Return results 353 return (included.keys(), used)
354