Memory Management algorithms

mm_algos.py

# =======================================================================
# =======================================================================
# =======================================================================
# =============================================================== Info ==

# This is also known as Bin Packing Problem
# http://en.wikipedia.org/wiki/Bin_packing_problem
# inspiration: http://www.developerfusion.com/article/5540/bin-packing/

# or maybe Knapsack Problem?
# http://en.wikipedia.org/wiki/Knapsack_problem

# if applicable it's better to sort in descending order before inserting
# els.sort(reverse=True)
# sorted(els,reverse=True)

# example use: python mm_algos.py 80 26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 35 12 43 36 72 14 28 3 11 46 27 42 59 26 41 15 41 68

# =======================================================================
# =======================================================================
# =======================================================================
# =============================================================== Init ==

import sys

if len(sys.argv) < 3:
  sys.exit("error, need at least 2 arguments (bin height and elements)")

maxHeight = int(sys.argv[1])
els = [int(x) for x in sys.argv[2:]]

# =======================================================================
# =======================================================================
# =======================================================================
# ====================================== Use Function (pretty print ;) ==

def useFunction (function, string):

  bins        = function(maxHeight,els)
  bins_sorted = function(maxHeight,sorted(els,reverse=True))

  print ""
  print string, "(unsorted):\t", len(bins),        "bins"#,"-", bins
  print string, "(sorted):  \t", len(bins_sorted), "bins"#,"-", bins_sorted
  
# =======================================================================
# =======================================================================
# =======================================================================
# =========================================================== Next Fit ==

def nextFit (maxHeight, els):

  # Never go back. Append all that fits, then make a new bin.

  bins = [[]]
  curBin = 0

  for el in els: 
    if el + sum(bins[curBin]) > maxHeight:
      bins.append([])
      curBin += 1
    bins[curBin].append(el)

  return bins

# ========================================================== First Fit ==

def firstFit (maxHeight, els):

  # Traverse from the start and append to the first possible place.

  bins = [[]]

  for el in els: 
    found = False
    for bin in bins:
      if el + sum(bin) <= maxHeight:
        bin.append(el)
        found = True
        break
    if not found:
      bins.append([el])

  return bins

# =========================================================== Last Fit ==

def lastFit (maxHeight, els):

  # Traverse from the end and append to the first possible place.

  bins = [[]]

  for el in els: 
    found = False
    for bin in bins[::-1]:
      if el + sum(bin) <= maxHeight:
        bin.append(el)
        found = True
        break
    if not found:
      bins.append([el])

  return bins

# ========================================================== Worst Fit ==

def worstFit (maxHeight, els):

  # Traverse all the bins and find the biggest possible place.

  bins = [[]]

  for el in els:
    sums = map(sum,bins)
    worstIndex = sums.index(min(sums))
    if el + sums[worstIndex] > maxHeight:
      bins.append([el])
    else:
      bins[worstIndex].append(el)

  return bins

# =========================================================== Best Fit ==

def bestFit (maxHeight, els):

  # Traverse all the bins and find the smallest possible place.

  bins = [[]]

  for el in els:
    sums = map(sum,bins)
    overflow = map(lambda x:(0 if x+el > maxHeight else x+el),sums)
    bestIndex = overflow.index(max(overflow))
    if el + sums[bestIndex] > maxHeight:
      bins.append([el])
    else:
      bins[bestIndex].append(el)

  return bins

# =======================================================================
# =======================================================================
# =======================================================================
# =============================================================== Main == 

useFunction(nextFit, "Next Fit")
useFunction(firstFit,"First Fit")
useFunction(lastFit, "Last Fit")
useFunction(worstFit,"Worst Fit")
useFunction(bestFit, "Best Fit")