alexpreynolds/first_fit.py

## first_fit.py
#!/usr/bin/env python

''' Using first-fit bin packing algorithm implementation from: https://bitbucket.org/kent37/python-tutor-samples/src/f657aeba5328/BinPacking.py '''

class Bin(object):
    def __init__(self):
        self.elements = []
        self.size = 0
        self.index = 0

    def append(self, element_key, element_value):
        self.elements.append(element_key)
        self.size += int(element_value)

    def __len__(self):
        len(self.elements)

    def __str__(self):
        return 'Bin(size=%d\n\tnumber_of_elements=%d\n\telements=%s)' % (self.size, int(len(self.elements)), self.elements)

def pack(elements, maximum_bin_size):
    bins = []
    bin_count = 0

    for element in elements:
        elem_range = element[0]
        elem_size = element[1]
        for bin in bins:
            if bin.size + elem_size <= maximum_bin_size:
                bin.append(elem_range, elem_size)
                break
        else:
            bin = Bin()
            bin.append(elem_range, elem_size)
            bin.index = bin_count
            bins.append(bin)
            bin_count += 1

    return bins

if __name__ == '__main__':
    import sys
    import numpy
    import random

    elements = {}
    bins = int(sys.argv[2])
    fudge = float(sys.argv[3])

    with open(sys.argv[1]) as f:
        for line in f:
            (chr, start, stop, size) = line.split()
            key = chr + ":" + start + "-" + stop
            value = int(size)
            elements[key] = value

    sorted_elements = sorted(elements.items(), key=lambda x: x[1], reverse=True)
    largest_element_size = sorted_elements[0][1]
    maximum_per_bin_size = int(numpy.ceil(largest_element_size / bins / fudge) * fudge)

    print '---------------------------------------------------'

    packed_bins = pack(sorted_elements, maximum_per_bin_size)
    print 'Via sorted elements -- using', len(packed_bins), 'of', bins, 'bins ( max_size:', maximum_per_bin_size,'):'
    bin_sizes = numpy.arange(len(packed_bins))
    for bin in packed_bins:
        print bin
        bin_sizes[bin.index] = bin.size
    print 'Size std dev --', numpy.std(bin_sizes)

    print '---------------------------------------------------'

    random_elements = sorted(elements.items(), key=lambda x: random.random())
    packed_bins = pack(random_elements, maximum_per_bin_size)
    print 'Via randomly shuffled elements -- using', len(packed_bins), 'of', bins, 'bins ( max_size:', maximum_per_bin_size,'):'
    bin_sizes = numpy.arange(len(packed_bins))
    for bin in packed_bins:
        print bin
        bin_sizes[bin.index] = bin.size
    print 'Size std dev --', numpy.std(bin_sizes)
	#!/usr/bin/env python

	''' Using first-fit bin packing algorithm implementation from: https://bitbucket.org/kent37/python-tutor-samples/src/f657aeba5328/BinPacking.py '''

	class Bin(object):
	def __init__(self):
	self.elements = []
	self.size = 0
	self.index = 0

	def append(self, element_key, element_value):
	self.elements.append(element_key)
	self.size += int(element_value)

	def __len__(self):
	len(self.elements)

	def __str__(self):
	return 'Bin(size=%d\n\tnumber_of_elements=%d\n\telements=%s)' % (self.size, int(len(self.elements)), self.elements)

	def pack(elements, maximum_bin_size):
	bins = []
	bin_count = 0

	for element in elements:
	elem_range = element[0]
	elem_size = element[1]
	for bin in bins:
	if bin.size + elem_size <= maximum_bin_size:
	bin.append(elem_range, elem_size)
	break
	else:
	bin = Bin()
	bin.append(elem_range, elem_size)
	bin.index = bin_count
	bins.append(bin)
	bin_count += 1

	return bins

	if __name__ == '__main__':
	import sys
	import numpy
	import random

	elements = {}
	bins = int(sys.argv[2])
	fudge = float(sys.argv[3])

	with open(sys.argv[1]) as f:
	for line in f:
	(chr, start, stop, size) = line.split()
	key = chr + ":" + start + "-" + stop
	value = int(size)
	elements[key] = value

	sorted_elements = sorted(elements.items(), key=lambda x: x[1], reverse=True)
	largest_element_size = sorted_elements[0][1]
	maximum_per_bin_size = int(numpy.ceil(largest_element_size / bins / fudge) * fudge)

	print '---------------------------------------------------'

	packed_bins = pack(sorted_elements, maximum_per_bin_size)
	print 'Via sorted elements -- using', len(packed_bins), 'of', bins, 'bins ( max_size:', maximum_per_bin_size,'):'
	bin_sizes = numpy.arange(len(packed_bins))
	for bin in packed_bins:
	print bin
	bin_sizes[bin.index] = bin.size
	print 'Size std dev --', numpy.std(bin_sizes)

	print '---------------------------------------------------'

	random_elements = sorted(elements.items(), key=lambda x: random.random())
	packed_bins = pack(random_elements, maximum_per_bin_size)
	print 'Via randomly shuffled elements -- using', len(packed_bins), 'of', bins, 'bins ( max_size:', maximum_per_bin_size,'):'
	bin_sizes = numpy.arange(len(packed_bins))
	for bin in packed_bins:
	print bin
	bin_sizes[bin.index] = bin.size
	print 'Size std dev --', numpy.std(bin_sizes)